The record itself is already resistance

Why is this just a post-order traversal? So post-order traversal is a little more troublesome, and the other five traversal types are understood by default (recursive and non-recursive preorders, middle-order traversal, and hierarchical traversal). There are two cases here,

  1. Hierarchical traversal is a breadth-first search of a tree, implemented with the help of queues. If you want to layer the output, add one more variable to record the number of nodes in the current layer.
  2. The remaining three types of non-recursive traversal are implemented using stacks.

Recursive order traversal

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="")
Copy the code

The following focuses on the analysis of post-order non-recursive traversal

Non-recursive traversal (1)

Idea: Push it to any node. If both the left and right nodes have been accessed, the node is accessed and removed from the stack. Otherwise, the right subtree is pushed and the left subtree is pushed, ensuring that the left subtree is accessed before the right.

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)
    whilelen(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(a)Copy the code

Non-recursive traversal (2)

Way of thinking; It is pushed for any node. Then search the left subtree until it is empty. At this point, the top node cannot exit the stack because it needs to access the right subtree. Do the same for the right subtree of the node. When the right subtree is accessed and removed from the stack, the node appears at the top of the stack again and is removed from the stack and accessed. Therefore, for each node, it appears twice at the top of the stack, and a tag or set is used to determine the number of times the node appears, and the corresponding operation is performed.

def post_order_traversal_tree_three(root):
    if root is None:
        return
    node_list = []
    node_set = set()
    node_set.add(None)
    temp_node = root
    whilelen(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

        iflen(node_list) ! = 0: temp_node = node_list[-1]if temp_node not in node_set :  The first time it appears at the top of the stack, do the same for the right subtree.
                node_set.add(temp_node)
                temp_node = temp_node.right_child
            else:
                print(temp_node.data, end="")
                node_list.pop()
                temp_node = None   Note that temp_node is set to null after it has gone off the stack to prevent it from being pushed again.
    print(a)Copy the code

Non-recursive traversal (3)

This is a neat way, the order is left – right – center. If the pre-order traversal is middle-left-right, then if the middle-right-left traversal can be reversed, the result of post-order traversal is obtained. In fact, it is also a right-first pre-order traversal, the code is as follows:

The root node is pushed. The root node goes off the stack and prints. The left subtree is pushed, the right subtree is pushed. Repeat the preceding steps. Reversing the printed result is the result of post-order traversal.
def post_order_traversal_tree_four(root):
    if root is None:
        return
    node_list = []
    result = []
    node_list.append(root)
    whilelen(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(a)Copy the code

So that’s my understanding of the four ways to do subsequent traversal of a binary tree. For the remaining five implementations of traversal, see the following addresses, all with simple comments. github: https://github.com/yunshuipiao/sw-algorithms/tree/master/python

About this project: Basic algorithms are something that every computer practitioner must have a deep understanding of. So I created this project to learn how to implement basic algorithms in different languages. Basic algorithm: [https://github.com/yunshuipiao/sw-algorithms/blob/master/questions.md] there is language python, kotlin, Java, c + +.

Welcome students who are studying computer and friends who are engaged in IT industry to communicate with each other and learn together. I also hope ACM god can guide the group.