[Background]

“Introduction to Data Structure” learned The third stage is about to end. When you do the questions, you will suddenly find out, oh, it turned out to be like this. At that time, I thought I would do it. When I met it again later, I didn’t know the thinking at the time. I could see this kind of learning. It is very superficial, the land is wet after the rain, the effect is very bad from a long-term point of view, it is still necessary to write by hand, sort out this part of the traversal of the binary tree, do you want to try a simple and fast method, with Let me do it!

[Revisit the basics] span>

traversal is one of the most basic operations on a tree. The so-called traversal of a binary tree is to traverse all the nodes of the binary tree according to a certain rule and order, so that each node is visited once and only once. Because the binary tree is a non-linear structure, the traversal of the tree essentially converts each node of the binary tree into a linear sequence to represent it.

Pre-order traversal: If the accessed binary tree is empty, then perform no operation; otherwise , Perform the following operations in sequence: visit the root node → traverse the left subtree first → traverse the right subtree first;

Mid-order traversal: If the visited binary tree is empty, then perform no operation; otherwise, perform the following operations in sequence: Mid-order Traverse the left subtree → visit the root node → traverse the right subtree in the middle order;

Post-order traversal:If the accessed binary tree is empty, execute No operation; otherwise, perform the following operations in sequence: post-order traversal of the left subtree → post-order traversal of the right subtree → visit the root node;

[Practical drill]

As mentioned above, is it very clear? You can understand it by following the example, but I encountered a For new questions, I’m getting messed up as I walked, so if this path doesn’t work, then I’ll take a different approach (ps: share a new method, for reference only)

< div style="line-height:28px; font-size:16px"> Based on page 104 of the textbook “Introduction to Data Structure” Example 4-1 is an example.

< span style="font-family:KaiTi_GB2312"> Preparation before traversal: take a line along the nodes of the binary tree to form an enclosing circle, starting from the left of the root node as the entrance direction, and returning after passing through each node is The direction of the exit, as shown in the figure below:

【Pre-order traversal】< /span>

Pre-order traversal: Mark the number “1” at the entrance direction of all nodes (usually the left side), and after all the nodes in the tree return to the root node in the order of the entrance direction, start from the most The entry point at the beginning (leftmost) walks down the enclosing line of the tree, and writes out all the points labeled “1” in turn, which is the preorder traversal sequence. As shown below:

The node sequence obtained in the pre-order traversal is: ABDEGCF

【Post-order traversal]

Post-order traversal:Mark the number “2” at the exit/return direction of all nodes (usually the right side), and after all the nodes in the tree return to the root node in the order of the entrance direction, start from the very beginning (the leftmost The entry point of) goes down the enclosing line of the tree, and writes out all the points labeled “2” in turn, which is the post-order traversal sequence. As shown below:

Get the node of the sequence traversed by the following CABF

【In-order traversal】

In-order traversal: In all nodes with left and right subtrees and all leaf nodes (degree is The number “0” is marked directly below 0), and other nodes have only left subtree or right subtree. There are two cases: if there is a right subtree, it is on the left side of the nodeMark the number “0”; if there is a left subtree, mark the number “0” on the right side of the node. After going through all the nodes in the tree and returning to the root node in the order of the entry direction, follow the encircling line of the tree from the entry point at the very beginning (leftmost) , Write out all the points labeled “0” in turn, which is the middle-order traversal sequence. As shown below:

The node sequence obtained after order traversal is: DBGEACF

[Summary]

[Summary]

The third stage of learning “Introduction to Data Structure” is almost the same It’s about to end. When doing the question, I will suddenly find out, oh, it turned out to be so. I thought I would do it. When I met it again later, I didn’t know the thinking at that time. I can see that this kind of study is very superficial. After the land is wet, the effect is very bad from a long-term perspective. It is still necessary to write, sort out, and traverse the binary tree. If you want to try a simple and fast method, let me do it!

traversal is a kind of tree The most basic operation, the so-called traversal of the binary tree, is to traverse all the nodes of the binary tree according to certain rules and order, so that each node is visited once and only once. Because the binary tree is a non-linear structure, the traversal of the tree essentially converts each node of the binary tree into a linear sequence to represent it.

Pre-order traversal: If the accessed binary tree is empty, perform no operation; otherwise, perform the following operations in sequence: visit the root node → traverse the left subtree first → traverse the right subtree first; p>

In-order traversal: If the accessed binary tree is empty, then perform a no-op; otherwise, perform one by one The following operations: traverse the left subtree in middle order → visit the root node → traverse the right subtree in middle order;

Post-order traversal:If the accessed binary tree is empty, then perform no operation; otherwise, perform the following operations in sequence: Post-order traversal of the left subtree → Post-order traversal of the right subtree → visit the root node;

As mentioned above, is it very clear? You can understand it by following the example, but when you encounter a new problem, it will be messed up when you walk around. Therefore, this way is not working, so I will find another way (Ps: share a new method for reference only)

Take Example 4-1 on page 104 of the “Introduction to Data Structure” textbook as an example

Preparation before traversal: follow the node of the binary tree along a line to form an enclosing circle, starting from the left of the root node as the entrance direction, when passing through each node The direction of return is the direction of exit, as shown in the following figure:

< span style="font-size:14px">【First order traversal】 /span>

【Post-order traversal]

Post-order traversal:In all knots The exit/return direction of the point (usually the right side) is marked with the number “2”. After going through all the nodes in the tree and returning to the root node in the order of the entrance direction, follow the tree from the first (leftmost) entry point Go down the encircling line of, and write out all the points labeled “2” in turn, which is the post-order traversal sequence. As shown in the figure below:

Pre-order traversal: Mark the number “1” at the entrance direction of all nodes (usually the left side), and go through all the nodes in the tree in the order of the entrance direction. After returning to the root node, go down the enclosing line of the tree from the first (leftmost) entry point, and write out all the points labeled “1” in turn, which is the pre-order traversal sequence. As shown in the figure below:

< span style="font-family:KaiTi_GB2312"> The node sequence obtained in the pre-order traversal is: ABDEGCF

Get the node of the sequence traversed afterwards ：DGEBFCA

< p> In-order traversal: Middle order traversal:All nodes with left and right subtrees and all leaf nodes (degree 0) are marked with the number “0” directly below, and the other nodes are only left subtree or right subtree. There are two cases: If there is a right subtree, mark the number “0” on the left side of the node; if there is a left subtree, mark the number “on the right side of the node 0”. After going through all the nodes in the tree and returning to the root node in the order of the entry direction, follow the encircling line of the tree from the entry point at the very beginning (leftmost) , Write out all the points labeled “0” in turn, which is the middle-order traversal sequence. As shown below:

[Summary]

The node sequence obtained after order traversal is: DBGEACF

I accidentally browsed a method on Baidu. I tried it for myself and it felt good. I sorted it out based on my own understanding. I hope to provide you with a way to solve the problem. Of course, the code interpretation behind the scenes is also very important. . Smart you, what are you waiting for? ? Hurry up and try it! !

It will not be the driving force behind the discovery, come on!