python实现二叉树遍历算法

cnn

　　说起二叉树的遍历，大学里讲的是递归算法，大多数人首先想到也是递归算法。但作为一个有理想有追求的程序员。也应该学学非递归算法实现二叉树遍历。二叉树的非递归算法需要用到辅助栈，算法着实巧妙，令人脑洞大开。
　　以下直入主题：
　　定义一颗二叉树，请看官自行想象其形状，



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
　　后序遍历：
　　后序遍历中，要保证左孩子和右孩子都已被访问才能访问根结点，并且左孩子需在右孩子前访问，这就为流程的控制带来了难题。下面介绍两种思路。
　　思路一，双栈法，这种方式比较容易理解，缺点是需要两个栈。



'''
后序遍历二叉树
'''
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() )
　　思路二，要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。



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 )