The in-order traversal sequence of a certain binary tree is CBADE, the post-order traversal sequence is CBADE, and the pre-order traversal sequence is EDABC.
First of all, post-order traversal means to first visit the left and right child nodes of the parent node, and finally visit the parent node.
Therefore, the last element of the postorder traversal sequence is the root node of the binary tree, which is E, so CBAD is the descendant node of E. (Recommended learning:web front-end video tutorial)
Now continue to look at in-order traversal. In-order traversal means that the left child of the parent node is visited first, then the parent node is visited, and finally Right child.
So the CBAD on the left side of root node E is its left child, and it has no right child. Then go back to the post-order traversal sequence again, because we already know that E is the root node, so we only need to consider CBAD.
So D is the direct left child of E, that is, D is the root node of the left subtree. Then continue to check the in-order traversal, you can find that D has no right subtree, only the left child CBA.
By analogy, it can be found that all nodes of this binary tree have no right children, and they are EDABC from top to bottom, so the preorder traversal is EDABC.
Characteristics of binary trees:
1. Each node has at most two subtrees, so there is no degree greater than 2 node.
2. The left subtree and the right subtree are in order, and the order cannot be reversed arbitrarily.
3. Even if a node in the tree has only one subtree, it must be distinguished whether it is a left subtree or a right subtree.
The above is the detailed content of The in-order traversal sequence of a certain binary tree is cbade, and the pre-order traversal sequence is. For more information, please follow other related articles on the PHP Chinese website!