快捷導(dǎo)航

Python數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹(shù)結(jié)構(gòu)定義與遍歷方法詳解

更新時(shí)間：2017年12月12日 12:03:39 作者：hanahimi

這篇文章主要介紹了Python數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹(shù)結(jié)構(gòu)定義與遍歷方法,結(jié)合實(shí)例形式詳細(xì)分析了Python實(shí)現(xiàn)二叉樹(shù)結(jié)構(gòu)的定義、遍歷方法及相關(guān)注意事項(xiàng),需要的朋友可以參考下

本文實(shí)例講述了Python數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹(shù)結(jié)構(gòu)定義與遍歷方法。分享給大家供大家參考，具體如下：

先序遍歷，中序遍歷，后序遍歷，區(qū)別在于三條核心語(yǔ)句的位置

層序遍歷采用隊(duì)列的遍歷操作第一次訪問(wèn)根，在訪問(wèn)根的左孩子，接著訪問(wèn)根的有孩子，然后下一層自左向右一一訪問(wèn)同層的結(jié)點(diǎn)

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

為了方便起見(jiàn)，定義一些打印操作

class BinTree():
  def __init__(self):
    self.root = None  # 創(chuàng)建一個(gè)空的二叉樹(shù)
  def isEmpty(self):   # 判斷二叉樹(shù)是否為空
    if self.root is None: return True
    else: return False
  def makeBT(self,bt,L=None,R=None):    # 從當(dāng)前結(jié)點(diǎn)創(chuàng)建二叉樹(shù)
    bt.lft = L
    bt.rgt = R
  def returnBTdict(self):       # 返回二叉樹(shù)的字典模式
    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):       # 將二叉樹(shù)結(jié)構(gòu)打印為字典結(jié)構(gòu)
    return str(self.returnBTdict())

下面是各種遍歷方法，添加到樹(shù)的類(lèi)中

def printT_VLR(self,bt=None,rec_count = 0):   # 輸出二叉樹(shù)結(jié)構(gòu)（先序遍歷）
    # rec_count 用于計(jì)算遞歸深度 以便輸出最后的換行符
    """
    # 先序遍歷
    # 訪問(wèn)結(jié)點(diǎn)，遍歷左子樹(shù)，如果左子樹(shù)為空，則遍歷右子樹(shù)，
    # 如果右子樹(shù)為空，則向上走到一個(gè)可以向右走的結(jié)點(diǎn)，繼續(xù)該過(guò)程
    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):
    """
    # 中序遍歷
    # 從根開(kāi)始，一直走向左下方，直到無(wú)結(jié)點(diǎn)可以走則停下，訪問(wèn)該節(jié)點(diǎn)
    # 然后走向右下方到結(jié)點(diǎn)，繼續(xù)走向左下方：如果結(jié)點(diǎn)無(wú)右孩子，則向上走回父親結(jié)點(diǎn)
    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):
    """
    層序遍歷 采用隊(duì)列的遍歷操作
    第一次訪問(wèn)根，在訪問(wèn)根的左孩子，接著訪問(wèn)根的有孩子，然后下一層
    自左向右一一訪問(wèn)同層的結(jié)點(diǎn)
    """
    btdict = self.returnBTdict()
    q = []
    q.append(btdict['root'])
    while q:
      tn = q.pop(0)  # 從隊(duì)列中彈出一個(gè)結(jié)點(diǎn)(也是一個(gè)字典)
      print tn["value"],
      if tn["L"]!=None:
        q.append(tn["L"])
      if tn["R"]!=None:
        q.append(tn["R"])

測(cè)試打印效果

def test():
  bt = BinTree()
#   btns = [BTNode(v) for v in "+*E*D/CAB"]   # 層序輸入
#   bt.root = btns[0]
#   bt.makeBT(btns[0], L=btns[1], R=btns[2])
#   bt.makeBT(btns[1], L=btns[3], R=btns[4])
#   bt.makeBT(btns[3], L=btns[5], R=btns[6])
#   bt.makeBT(btns[5], L=btns[7], R=btns[8])
  btns = [BTNode(v) for v in [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]]
  bt.root = btns[0]
  bt.makeBT(btns[0], L=btns[1], R=btns[2])
  bt.makeBT(btns[1], L=btns[3], R=btns[4])
  bt.makeBT(btns[2], L=btns[5], R=btns[6])
  bt.makeBT(btns[3], L=btns[7], R=btns[8])
  bt.makeBT(btns[4], L=btns[9], R=btns[10])
  bt.makeBT(btns[5], L=btns[11], R=btns[12])
  bt.makeBT(btns[6], L=btns[13], R=btns[14])

輸出：

復(fù)制代碼代碼如下:

{'root': {'R': {'R': {'R': {'R': None, 'L': None, 'value': 15}, 'L': {'R': None, 'L': None, 'value': 14}, 'value': 7}, 'L': {'R': {'R': None, 'L': None, 'value': 13}, 'L': {'R': None, 'L': None, 'value': 12}, 'value': 6}, 'value': 3}, 'L': {'R': {'R': {'R': None, 'L': None, 'value': 11}, 'L': {'R': None, 'L': None, 'value': 10}, 'value': 5}, 'L': {'R': {'R': None, 'L': None, 'value': 9}, 'L': {'R': None, 'L': None, 'value': 8}, 'value': 4}, 'value': 2}, 'value': 1}}

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門(mén)與進(jìn)階經(jīng)典教程》

希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: