python實現二叉樹遍歷算法 - tudas－IT工程師數位筆記本

文章出處

說起二叉樹的遍歷，大學里講的是遞歸算法，大多數人首先想到也是遞歸算法。但作為一個有理想有追求的程序員。也應該學學非遞歸算法實現二叉樹遍歷。二叉樹的非遞歸算法需要用到輔助棧，算法著實巧妙，令人腦洞大開。

以下直入主題：

定義一顆二叉樹，請看官自行想象其形狀，

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 )