Post-order traversal of a tree refers to traversing each subtree in turn and then accessing the root node. When a tree is stored in binary tree representation (also called child brother representation), the unique binary tree corresponding to it can be found. We call this binary tree the binary tree corresponding to this tree. Then according to this rule, the post-order traversal sequence of a tree is equivalent to the middle-order traversal of a binary tree corresponding to the tree.

From the recursive definition of binary tree, a non-empty binary tree consists of three basic parts: root node and left and right subtrees. Therefore, at any given juncture.

(1) the access node itself (n),

(2) traversing the left subtree (L) of the node,

(3) Traverse the right subtree (r) of the node.

There are six execution sequences for the above three operations:

NLR、LNR、LRN、NRL、RNL、RLN。

note:

The first three orders are symmetrical with the last three orders, so only the first three orders from left to right are discussed.

From the recursive definition of binary tree, a non-empty binary tree consists of three basic parts: root node and left and right subtrees. Therefore, at any given juncture.

Extended data:

The order of accessing the binary tree is as follows:

Starting from the root node, I arrived at node A for the first time, so I output a;

Continue to visit to the left, visit node B for the first time, so output B;

According to the same rules, output D and output H;

When it reaches the leaf node H, it returns D, which is the second time to reach D, so it is not output D, and then access the right subtree of D, if the right subtree of D is not empty, access I, and if it reaches I for the first time, it is output I;

If I is a leaf node, return D, if the subtree around D has been visited, return B, then go to the right subtree of B, and reach E for the first time, so output E;

Left subtree to e, so output j;

Continue to output c, f and g according to the same access rules.

The sequential access in the binary tree is as follows:

Starting from the root node, the first time you arrive at node A, you don't output A, and you continue to visit to the left, and the first time you visit node B, you don't output B; Continue to d, h;

When reaching H, if the left subtree of H is empty, H will be returned, and H will be visited for the second time at this time, so H is output;

If the right subtree of H is empty, it returns to D, and then it reaches D for the second time, then it outputs D;

Return from d to b, and arrive at b for the second time, so output b;

Continue to access according to the same rules, and output j, e, a, f, c and g.

Baidu Encyclopedia-Binary Tree

Baidu Encyclopedia-Binary Tree Traversal