溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了Python實現重建二叉樹的三種方法。分享給大家供大家參考，具體如下：
學習算法中，探尋重建二叉樹的方法：
如果懶得去看后面的內容，可以直接點擊此處本站下載完整實例代碼。
思路
學習算法中，python 算法方面的資料相對較少，二叉樹解析重建更少，只能摸著石頭過河。
通過不同方式遍歷二叉樹，可以得出不同節點的排序。那么，在已知節點排序的前提下，通過某種遍歷方式，可以將排序進行解析，從而構建二叉樹。
應用上來將，可以用來解析多項式、可以解析網頁、xml等。
本文采用前序遍歷方式的排列，對已知字符串進行解析，并生成二叉樹。新手，以解題為目的，暫未優化，未能體現 Python 簡潔、優美。請大牛不吝指正。
首先采用 input 輸入
節點類
class treeNode: def __init__(self, rootObj = None, leftChild = None, rightChild = None): self.key = rootObj self.leftChild = None self.rightChild = None
input 方法重建二叉樹
def createTreeByInput(self, root):
tmpKey = raw_input("please input a key, input '#' for Null")
if tmpKey == '#':
root = None
else:
root = treeNode(rootObj=tmpKey)
root.leftChild = self.createTreeByInput(root.leftChild)
root.rightChild = self.createTreeByInput(root.rightChild)
return root
以下兩種方法，使用預先編好的字符串，通過 list 方法轉換為 list 傳入進行解析
myTree 為實例化一個空樹
調用遞歸方法重建二叉樹
treeElementList = '124#8##5##369###7##' myTree = myTree.createTreeByListWithRecursion(list(treeElementList)) printBTree(myTree, 0)
遞歸方法重建二叉樹
def createTreeByListWithRecursion(self, preOrderList): """ 根據前序列表重建二叉樹 :param preOrder: 輸入前序列表 :return: 二叉樹 """ preOrder = preOrderList if preOrder is None or len(preOrder) <= 0: return None currentItem = preOrder.pop(0) # 模擬C語言指針移動 if currentItem is '#': root = None else: root = treeNode(currentItem) root.leftChild = self.createTreeByListWithRecursion(preOrder) root.rightChild = self.createTreeByListWithRecursion(preOrder) return root
調用堆棧方法重建二叉樹
treeElementList = '124#8##5##369###7##' myTree = myTree.createTreeByListWithStack(list(treeElementList)) printBTree(myTree, 0)
使用堆棧重建二叉樹
def createTreeByListWithStack(self, preOrderList):
"""
根據前序列表重建二叉樹
:param preOrder: 輸入前序列表
:return: 二叉樹
"""
preOrder = preOrderList
pStack = SStack()
# check
if preOrder is None or len(preOrder) <= 0 or preOrder[0] is '#':
return None
# get the root
tmpItem = preOrder.pop(0)
root = treeNode(tmpItem)
# push root
pStack.push(root)
currentRoot = root
while preOrder:
# get another item
tmpItem = preOrder.pop(0)
# has child
if tmpItem is not '#':
# does not has left child, insert one
if currentRoot.leftChild is None:
currentRoot = self.insertLeft(currentRoot, tmpItem)
pStack.push(currentRoot.leftChild)
currentRoot = currentRoot.leftChild
# otherwise insert right child
elif currentRoot.rightChild is None:
currentRoot = self.insertRight(currentRoot, tmpItem)
pStack.push(currentRoot.rightChild)
currentRoot = currentRoot.rightChild
# one child is null
else:
# if has no left child
if currentRoot.leftChild is None:
currentRoot.leftChild = None
# get another item fill right child
tmpItem = preOrder.pop(0)
# has right child
if tmpItem is not '#':
currentRoot = self.insertRight(currentRoot, tmpItem)
pStack.push(currentRoot.rightChild)
currentRoot = currentRoot.rightChild
# right child is null
else:
currentRoot.rightChild = None
# pop itself
parent = pStack.pop()
# pos parent
if not pStack.is_empty():
parent = pStack.pop()
# parent become current root
currentRoot = parent
# return from right child, so the parent has right child, go to parent's parent
if currentRoot.rightChild is not None:
if not pStack.is_empty():
parent = pStack.pop()
currentRoot = parent
# there is a leftchild ,fill right child with null and return to parent
else:
currentRoot.rightChild = None
# pop itself
parent = pStack.pop()
if not pStack.is_empty():
parent = pStack.pop()
currentRoot = parent
return root
顯示二叉樹
def printBTree(bt, depth): ''''' 遞歸打印這棵二叉樹，#號表示該節點為NULL ''' ch = bt.key if bt else '#' if depth > 0: print '%s%s%s' % ((depth - 1) * ' ', '--', ch) else: print ch if not bt: return printBTree(bt.leftChild, depth + 1) printBTree(bt.rightChild, depth + 1)
打印二叉樹的代碼，采用某仁兄代碼，在此感謝。
input 輸入及顯示二叉樹結果
解析字符串的結果
完整代碼參見：https://github.com/flyhawksz/study-algorithms/blob/master/Class_BinaryTree2.py
更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數據結構與算法教程》、《Python加密解密算法與技巧總結》、《Python編碼操作技巧總結》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經典教程》
希望本文所述對大家Python程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
