本文實(shí)例講述了Python二叉樹(shù)的定義及常用遍歷算法。分享給大家供大家參考，具體如下：
說(shuō)起二叉樹(shù)的遍歷，大學(xué)里講的是遞歸算法，大多數(shù)人首先想到也是遞歸算法。但作為一個(gè)有理想有追求的程序員。也應(yīng)該學(xué)學(xué)非遞歸算法實(shí)現(xiàn)二叉樹(shù)遍歷。二叉樹(shù)的非遞歸算法需要用到輔助棧，算法著實(shí)巧妙，令人腦洞大開(kāi)。
以下直入主題：
定義一顆二叉樹(shù)，請(qǐng)看官自行想象其形狀，
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class BinNode( ): def __init__( self, val ): self.lchild = None self.rchild = None self.value = valbinNode1 = BinNode( 1 )binNode2 = BinNode( 2 )binNode3 = BinNode( 3 )binNode4 = BinNode( 4 )binNode5 = BinNode( 5 )binNode6 = BinNode( 6 )binNode1.lchild = binNode2binNode1.rchild = binNode3binNode2.lchild = binNode4binNode2.rchild = binNode5binNode3.lchild = binNode6 |
先序遍歷：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
'''先序遍歷二叉樹(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 ) |
中序遍歷：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
'''中序遍歷二叉樹(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è)棧。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
'''后序遍歷二叉樹(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)。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
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 ) |
層序遍歷：
|
1
2
3
4
5
6
7
8
9
10
|
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 ) |
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
原文鏈接：https://www.cnblogs.com/tudas/p/binary-tree-traverse.html
