本文實例講述了Python數據結構與算法之二叉樹結構定義與遍歷方法。分享給大家供大家參考，具體如下：

先序遍歷，中序遍歷，后序遍歷 ，區別在于三條核心語句的位置

層序遍歷  采用隊列的遍歷操作第一次訪問根，在訪問根的左孩子，接著訪問根的有孩子，然后下一層 自左向右一一訪問同層的結點

# 先序遍歷# 訪問結點，遍歷左子樹，如果左子樹為空，則遍歷右子樹，# 如果右子樹為空，則向上走到一個可以向右走的結點，繼續該過程preorder(t):  if t:    print t.value    preorder t.L    preorder t.R# 中序遍歷# 從根開始，一直走向左下方，直到無結點可以走則停下，訪問該節點# 然后走向右下方到結點，繼續走向左下方：如果結點無右孩子，則向上走回父親結點inorder(t):  inorder(t.L)  print t.value  inorder(t.R)# 后序遍歷inorder(t):  inorder(t.L)  inorder(t.R)  print t.value# 二叉樹結點類型class BTNode:  def __init__(self,value,lft=None,rgt=None):    self.value = value    self.lft = lft     # 結點左分支 BTNode    self.rgt = rgt     # 結點右分支 BTNode

為了方便起見，定義一些打印操作

class BinTree():  def __init__(self):    self.root = None  # 創建一個空的二叉樹  def isEmpty(self):   # 判斷二叉樹是否為空    if self.root is None: return True    else: return False  def makeBT(self,bt,L=None,R=None):    # 從當前結點創建二叉樹    bt.lft = L    bt.rgt = R  def returnBTdict(self):       # 返回二叉樹的字典模式    if self.isEmpty():       return None    def rec(bt=None,R=True):      if R==True:        bt = self.root        return {'root':{'value':bt.value,"L":rec(bt.lft,False),                        "R":rec(bt.rgt,False)} }      else:        if bt==None:          return None        else:          return {"value":bt.value,              "L":rec(bt.lft,False) if bt.lft != None else None,              "R":rec(bt.rgt,False) if bt.rgt != None else None}      return None    return rec()  def __repr__(self):       # 將二叉樹結構打印為字典結構    return str(self.returnBTdict())

下面是各種遍歷方法，添加到樹的類中

def printT_VLR(self,bt=None,rec_count = 0):   # 輸出二叉樹結構（先序遍歷）    # rec_count 用于計算遞歸深度 以便輸出最后的換行符    """    # 先序遍歷    # 訪問結點，遍歷左子樹，如果左子樹為空，則遍歷右子樹，    # 如果右子樹為空，則向上走到一個可以向右走的結點，繼續該過程    preorder(t):      if t:        print t.value        preorder t.L        preorder t.R    """    if bt==None:       bt = self.root      print bt.value,    btL, btR = bt.lft, bt.rgt    if btL != None:      print btL.value,;  rec_count += 1;   self.printT_VLR(btL,rec_count);   rec_count -= 1    if btR != None:      print btR.value,;  rec_count += 1;   self.printT_VLR(btR,rec_count);   rec_count -= 1    if rec_count == 0:      print "/n"def printT_LVR(self,bt=None):    """    # 中序遍歷    # 從根開始，一直走向左下方，直到無結點可以走則停下，訪問該節點    # 然后走向右下方到結點，繼續走向左下方：如果結點無右孩子，則向上走回父親結點    inorder(t):      inorder(t.L)      print t.value      inorder(t.R)    """    if bt==None:      bt = self.root    btL, btR = bt.lft, bt.rgt    if btL != None:      self.printT_LVR(btL)    print bt.value,    if btR != None:      self.printT_LVR(btR)def printT_LRV(self,bt=None):    """    # 后序遍歷    inorder(t):      inorder(t.L)      inorder(t.R)      print t.value    """    if bt==None:      bt = self.root    btL, btR = bt.lft, bt.rgt    if btL != None:      self.printT_LRV(btL)    if btR != None:      self.printT_LRV(btR)    print bt.value,def printT_levelorder(self):    """    層序遍歷 采用隊列的遍歷操作    第一次訪問根，在訪問根的左孩子，接著訪問根的有孩子，然后下一層    自左向右一一訪問同層的結點    """    btdict = self.returnBTdict()    q = []    q.append(btdict['root'])    while q:      tn = q.pop(0)  # 從隊列中彈出一個結點(也是一個字典)      print tn["value"],      if tn["L"]!=None:        q.append(tn["L"])      if tn["R"]!=None:        q.append(tn["R"])