Python二叉樹的定義及常用遍歷算法分析
本文實例講述了Python二叉樹的定義及常用遍歷算法。分享給大家供大家參考，具體如下：
說起二叉樹的遍歷，大學里講的是遞歸算法，大多數(shù)人首先想到也是遞歸算法。但作為一個有理想有追求的程序員。也應該學學非遞歸算法實現(xiàn)二叉樹遍歷。二叉樹的非遞歸算法需要用到輔助棧，算法著實巧妙，令人腦洞大開。
以下直入主題：
定義一顆二叉樹，請看官自行想象其形狀，
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
先序遍歷：
'''
先序遍歷二叉樹
'''
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 )
中序遍歷：
'''
中序遍歷二叉樹
'''
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
后序遍歷：
后序遍歷中，要保證左孩子和右孩子都已被訪問才能訪問根結(jié)點，并且左孩子需在右孩子前訪問，這就為流程的控制帶來了難題。下面介紹兩種思路。
思路一，雙棧法，這種方式比較容易理解，缺點是需要兩個棧。
'''
后序遍歷二叉樹
'''
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é)點在左孩子和右孩子訪問之后才能訪問，因此對于任一結(jié)點P，先將其入棧。如果P不存在左孩子和右孩子，則可以直接訪問它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被訪問過了，則同樣可以直接訪問該結(jié)點。若非上述兩種情況，則將P的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時候，左孩子在右孩子前面被訪問，左孩子和右孩子都在根結(jié)點前面被訪問。
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 )
更多關于Python相關內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進階經(jīng)典教程》
希望本文所述對大家Python程序設計有所幫助。
相關文章
Python如何實現(xiàn)動態(tài)數(shù)組
這篇文章主要介紹了Python如何實現(xiàn)動態(tài)數(shù)組,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-11-11
這篇文章主要介紹了Django如何創(chuàng)作一個簡單的最小程序，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-05-05
Python爬蟲:將headers請求頭字符串轉(zhuǎn)為字典的方法
今天小編就為大家分享一篇Python爬蟲:將headers請求頭字符串轉(zhuǎn)為字典的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-08-08
Python導入txt數(shù)據(jù)到mysql的方法
這篇文章主要介紹了Python導入txt數(shù)據(jù)到mysql的方法,涉及Python操作txt文件及mysql數(shù)據(jù)庫的技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-04-04
python3在同一行內(nèi)輸入n個數(shù)并用列表保存的例子
今天小編就為大家分享一篇python3在同一行內(nèi)輸入n個數(shù)并用列表保存的例子，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-07-07
這篇文章主要介紹了python中棧的原理及實現(xiàn)方法,結(jié)合實例形式分析了Python棧的概念、原理、常見操作方法及相關使用技巧,需要的朋友可以參考下2019-11-11
這篇文章主要為大家詳細介紹了Python標準庫中的sys，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
Python使用pyenv實現(xiàn)多環(huán)境管理
這篇文章主要介紹了Python使用pyenv實現(xiàn)多環(huán)境管理，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-02-02
本文主要介紹了python中xlwt模塊的具體用法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-02-02
linux環(huán)境下的python安裝過程圖解(含setuptools)
這篇文章主要介紹了linux環(huán)境下的python安裝過程圖解(含setuptools),小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-11-11