本文實例講述了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