This is the 16th day of my participation in the August More Text Challenge. For details, see:August is more challenging
6.3 Traversing a binary tree
In the implementation of binary tree operation, it is often necessary to carry out some kind of operation on all its nodes. This operation on all nodes one by one is called traversal.
6.3.1 Recursive implementation of traversing binary trees
Traversing a binary tree means accessing each node in the binary tree in some order so that each node is accessed once and only once. Access refers to computing data information about a node in a binary tree, printing information about that node, and any other operations performed on the node.
Traversing a binary tree is the most basic operation of a binary tree, and it is also the basis of various other operations of a binary tree. Because in practical applications, it is often necessary to access each node in the binary tree one by one in a certain order, or to find the node, and then to process.
Binomial tree is a nonlinear data structure. By traversing the nodes in the binomial tree, the sequential sequence of access nodes can be obtained from the nonlinear sequence. In other words, the traversal operation linearizes the nonlinear structure.
According to the definition of binary tree, binary tree consists of the root node, the left subtree of the root node and the right subtree of the root node. So, as long as you go through these three parts, you can go through the whole binary tree.
If D, L, and R respectively represent accessing the root node, traversing the left subtree of the root node, and traversing the right subtree of the root node, there are six traversal modes of binary tree: DLR, LDR, LRD, DRL, RDL, and RLD. If you restrict left and then right, there are only the first three ways. According to the different order of access to the root, DLR is called the first order (root) traversal, LDR is called the middle order (root) traversal, and LRD is called the second order (root) traversal.
Based on the recursive definition of binary tree, the recursive algorithm definition of traversing binary tree can be obtained.
1. Preorder traversal
If the binary tree is empty, the operation is null, otherwise
(1) Access the root node;
(2) First traverse the left subtree of the root node;
(3) The right subtree of the root node is first traversed.
The recursive algorithm of first order traversal binary tree is as follows.
[Algorithm 6-1] Binary tree first order traversal algorithm
2. In order traversal
If the binary tree is empty, the operation is null, otherwise
(1) in order to traverse the left subtree of the root node;
(2) Access the root node;
(3) in order to traverse the right subtree of the root node.
The recursive algorithm of order traversal binary tree is as follows.
[Algorithm 6-2] Binary tree order traversal algorithm
3. Back-order traversal
If the binary tree is empty, the operation is null, otherwise
(1) The left subtree of the root node is traversed sequentially;
(2) The right subtree of the root node is traversed sequentially;
(3) Access the root node.
After order traversal binary tree recursive algorithm is as follows.
[Algorithm 6-3] Binary tree sequential traversal algorithm
4. Hierarchical traversal
The so-called binary tree hierarchy traversal, is from the first layer of the binary tree (root node), from the top to the bottom layer traversal, in the same layer, according to the left to right order to access nodes one by one.
Figure 6-13 Binary tree
For the binary tree shown in Figure 6-13, the sequence of first order, middle order, last order, and hierarchical traversal is as follows.
A, B, D, F, G, C, E;
B, F, D, G, A, C, E;
F, G, D, B, E, C, A
Level traversal: A, B, C, D, E, F, G.
From the definition of binary tree traversal, it can be seen that the difference between the first order, the middle order and the second order traversal methods lies in the sequential relationship between the root node and the left and right subtree traversal, but they all adopt the recursive method. Recursion, on the other hand, must be implemented on a lifO stack.
6.3.2 Non-recursive implementation of traversal binary trees
For the binary tree shown in Figure 6-13, the first order, middle order and last order traversal all start from the root node A, and the route through the node in the traversal process is the same, but the access time is different. As shown in Figure 6-14, the curve from the outer left side of the root node to the outer right side of the root node traverses the binary tree. Along this route, the first sequence is read according to the node marked by △, the middle sequence is read according to *, and the last sequence is read according to #.
Figure 6-14 Traversing a binary tree
However, this route starts from the root node and searches along the left subtree. When the search reaches the leftmost end and cannot go any further, it returns, and then enters the right subtree of the node encountered in the previous search one by one, and carries out such search and return until it finally returns from the right subtree of the root node to the root node. The first order traversal is to access the node when searching, the second order traversal is to encounter the node when returning from the left subtree, and the second order traversal is to encounter the node when returning from the right subtree.
In this process, the order of returning nodes is opposite to the order of searching nodes, just in line with the last in, first out characteristics of the stack structure, so you can use the stack to rewrite the recursive algorithm into a non-recursive algorithm.
When searching along the left subtree, a node is pushed deep into a node. If it is a preorder traversal, it is accessed before the push. When the left branch can not go down, it returns, that is, from the stack to pop the node pushed in the front; If it is a middle order traversal, then the node is accessed at this time, and then the right subtree of the node continues to go deep; If it is a post-order traversal, the node will be pushed into the stack again, and then continue to go deep from the right subtree of the node, and then go deep into a node and push a node into the stack, and then return when it can’t go deep, until the node is popped out of the stack the second time, that is, when it returns from the right subtree, it will not be visited.
1. Non-recursive implementation of preorder traversal
In the following algorithm, the binary tree is stored in the binary linked list, the one-dimensional array stack[MAXSIZE] is used to implement the stack, and the variable top is used to indicate the position of the top of the current stack.
[Algorithm 6-4] A non-recursive implementation algorithm of preorder traversal
2. Non-recursive implementation of order traversal in
In the non-recursive algorithm of order traversal, just need to first order traversal of the non-recursive algorithm printf(p->data) moved top =stack[top] and p=p->rchild.
[Algorithm 6-5] non-recursive implementation algorithm of order traversal
3. Non-recursive implementation of post-order traversal
The post-order traversal non-recursive algorithm is more complex. The root node is accessed after the left and right subtrees are accessed. Note After a node is removed from the stack for the first time, it needs to be pushed into the stack again. In other words, the node is pushed twice and off the stack twice, and the node is accessed on the second exit. Therefore, to distinguish the two exits of the same node pointer from the stack, a flag flag is set. When the node pointer enters or leaves the stack, its flag flag also enters or leaves the stack at the same time.
Post-order traversal binary tree non-recursive algorithm is as follows.
In the algorithm, the one-dimensional array stack[MAXSIZE] is used to implement the stack structure, the pointer variable p points to the current node to be processed, and top is the top pointer, used to indicate the current top of the stack position.
[Algorithm 6-6] Non-recursive implementation algorithm of sequential traversal
Since each node is accessed only once, the time complexity of a binary tree with n nodes is O(n) no matter which order is traversed. The required auxiliary space is the maximum capacity of the stack during the traversal, i.e., the depth of the tree, which is n in the worst case, i.e., the space complexity is also O(n).