二叉树的遍历之多种后序遍历

[yunshuipiao]

为什么这里仅仅是后序遍历？因此后序遍历稍微要麻烦一点，默认对其他五种遍历已经了解(递归和非递归的前序， 中序遍历，还有层次遍历。 这里有两种情况，

1. 层次遍历是树的广度优先搜索，借助队列实现。如果要分层输出，那么多加一个变量记录当前层的节点个数。
2. 其余三种的非递归遍历都是借助栈实现。

递归后序遍历

def post_order_traversal_tree(root):
    if root is None:
        return
    post_order_traversal_tree(root.left_child)
    post_order_traversal_tree(root.right_child)
    print(root.data, end="   ")

下面着重分析一下后序的非递归遍历

非递归遍历（一）

思路：对于任一节点将其入栈。若左右节点都已访问过，则访问该节点并出栈。否则将右子树入栈，左子树入栈， 保证左子树在右子树之前访问。

def post_order_traversal_tree_two(root):
    if root is None:
        return
    node_list = []
    node_list.append(root)
    node_set = set()
    node_set.add(None)
    while len(node_list) != 0:
        temp_node = node_list[-1]
        if temp_node.left_child in node_set and temp_node.right_child in node_set:
            print(temp_node.data, end="   ")
            node_list.pop()
            node_set.add(temp_node)
        else:
            if temp_node.right_child is not None:
                node_list.append(temp_node.right_child)
            if temp_node.left_child is not None:
                node_list.append(temp_node.left_child)
    print()

非递归遍历（二）

思路；对于任一节点将其入栈。然后一直搜索左子树直到空。此时对于栈顶节点，由于还要访问右子树，所以不能出栈。对于该节点的右子树做相同的操作。当右子树访问并出栈后，该节点又出现在栈顶，此时出栈并访问。因此对于每一个节点，都在栈顶出现两次，用一个标记或者集合来判断该节点是第几次出现，做对应的操作。

def post_order_traversal_tree_three(root):
    if root is None:
        return
    node_list = []
    node_set = set()
    node_set.add(None)
    temp_node = root
    while len(node_list) != 0 or temp_node is not None:
        while temp_node is not None:
            node_list.append(temp_node)
            temp_node = temp_node.left_child

        if len(node_list) != 0:
            temp_node = node_list[-1]
            if temp_node not in node_set :  #第一次出现在栈顶，对右子树做相同操作。
                node_set.add(temp_node)
                temp_node = temp_node.right_child
            else:
                print(temp_node.data, end="   ")
                node_list.pop()
                temp_node = None   #最后注意temp_node 出栈后，置为空，防止再次入栈。
    print()

非递归遍历（三）

这一种方式比较讨巧，后序是 左 -- 右 -- 中。 而前序遍历是 中--左--右 ，那么如果能 中--右--左 遍历，倒转就得到了后序遍历的结果，其实也是一种右在先的前序遍历，代码如下：

#根节点入栈。根节点出栈并打印。左子树入栈，右子树入栈。重复上述操作。将打印结果反转即是后序遍历的结果。
def post_order_traversal_tree_four(root):
    if root is None:
        return
    node_list = []
    result = []
    node_list.append(root)
    while len(node_list) != 0:
        temp_node = node_list.pop()
        result.append(temp_node.data)
        if temp_node.left_child is not None:
            node_list.append(temp_node.left_child)
        if temp_node.right_child is not None:
            node_list.append(temp_node.right_child)
    for i in reversed(result):
        print(i, end="   ")
    print()

以上就是我理解的对于二叉树后续遍历的四种方法。 对于其余五种遍历的实现，请查看下面地址，都有简单注释。 github: https://github.com/yunshuipiao/sw-algorithms/tree/master/python

关于这个项目：最基本的算法是每一个计算机从业者必须深刻理解的内容。 因此新建这个项目来学习并用不同语言来实现最基本的算法。 [基本算法：https://github.com/yunshuipiao/sw-algorithms/blob/master/questions.md] 目前语言有python， kotlin， java， c++。