快捷導(dǎo)航

Python二叉樹(shù)的定義及常用遍歷算法分析

更新時(shí)間：2017年11月24日 12:02:13 作者：caochao

這篇文章主要介紹了Python二叉樹(shù)的定義及常用遍歷算法,結(jié)合實(shí)例形式分析了基于Python的二叉樹(shù)定義與先序、中序、后序、層序等遍歷方法,需要的朋友可以參考下

本文實(shí)例講述了Python二叉樹(shù)的定義及常用遍歷算法。分享給大家供大家參考，具體如下：

說(shuō)起二叉樹(shù)的遍歷，大學(xué)里講的是遞歸算法，大多數(shù)人首先想到也是遞歸算法。但作為一個(gè)有理想有追求的程序員。也應(yīng)該學(xué)學(xué)非遞歸算法實(shí)現(xiàn)二叉樹(shù)遍歷。二叉樹(shù)的非遞歸算法需要用到輔助棧，算法著實(shí)巧妙，令人腦洞大開(kāi)。

以下直入主題：

定義一顆二叉樹(shù)，請(qǐng)看官自行想象其形狀，

class BinNode( ):
  def __init__( self, val ):
    self.lchild = None
    self.rchild = None
    self.value = val
binNode1 = BinNode( 1 )
binNode2 = BinNode( 2 )
binNode3 = BinNode( 3 )
binNode4 = BinNode( 4 )
binNode5 = BinNode( 5 )
binNode6 = BinNode( 6 )
binNode1.lchild = binNode2
binNode1.rchild = binNode3
binNode2.lchild = binNode4
binNode2.rchild = binNode5
binNode3.lchild = binNode6

先序遍歷：

'''
先序遍歷二叉樹(shù)
'''
def bin_tree_pre_order_traverse( root, visit_func ):
  s = Stack()
  s.push( root )
  while not s.is_empty():
    node = s.pop()
    visit_func( node )
    if node.rchild:
      s.push( node.rchild )
    if node.lchild:
      s.push( node.lchild )

中序遍歷：

'''
中序遍歷二叉樹(shù)
'''
def bin_tree_in_order_traverse( root, visit_func ):
  s = Stack()
  node = root
  while node or not s.is_empty():
    if node:
      s.push( node )
      node = node.lchild
    else:
      node = s.pop()
      visit_func( node )
      node = node.rchild

后序遍歷：

后序遍歷中，要保證左孩子和右孩子都已被訪問(wèn)才能訪問(wèn)根結(jié)點(diǎn)，并且左孩子需在右孩子前訪問(wèn)，這就為流程的控制帶來(lái)了難題。下面介紹兩種思路。

思路一，雙棧法，這種方式比較容易理解，缺點(diǎn)是需要兩個(gè)棧。

'''
后序遍歷二叉樹(shù)
'''
def bin_tree_post_order_traverse( root, visit_func ):
  s1 = Stack()
  s2 = Stack()
  s1.push( root )
  while not s1.is_empty():
    node = s1.pop()
    s2.push( node )
    if node.lchild:
      s1.push( node.lchild )
    if node.rchild:
      s1.push( node.rchild )
  while not s2.is_empty():
    visit_func( s2.pop() )

思路二，要保證根結(jié)點(diǎn)在左孩子和右孩子訪問(wèn)之后才能訪問(wèn)，因此對(duì)于任一結(jié)點(diǎn)P，先將其入棧。如果P不存在左孩子和右孩子，則可以直接訪問(wèn)它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被訪問(wèn)過(guò)了，則同樣可以直接訪問(wèn)該結(jié)點(diǎn)。若非上述兩種情況，則將P的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時(shí)候，左孩子在右孩子前面被訪問(wèn)，左孩子和右孩子都在根結(jié)點(diǎn)前面被訪問(wèn)。

def bin_tree_post_order_traverse2( root, visit_func ):
  curr = root
  prev = None
  s = Stack()
  s.push( curr )
  while not s.is_empty():
    curr = s.peek()
    if ( not curr.lchild and not curr.rchild ) or ( prev and ( prev == curr.lchild or prev == curr.rchild ) ):
      visit_func( curr )
      s.pop()
　　　　　　　prev = curr
    else:
      if curr.rchild:
        s.push( curr.rchild )
      if curr.lchild:
        s.push( curr.lchild )

層序遍歷：

def bin_tree_level_traverse( root, visit_func ):
  queue = Queue()
  queue.enqueue( root )
  while not queue.is_empty():
    node = queue.dequeue().value
    visit_func( node )
    if node.lchild:
      queue.enqueue( node.lchild )
    if node.rchild:
      queue.enqueue( node.rchild )

更多關(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ì)有所幫助。

您可能感興趣的文章: