Reference content:
Five minutes will give you a thorough understanding of non-recursive traversal of binary trees
Python implements non-recursive traversal of binary trees
Binary tree traversal – depth first (front, middle and last order) + breadth first (level order traversal)
Construct a binary tree
Define the binary tree structure as follows
struct node
{<!-- -->
int data;
node *left;
node *right;
};
Construct a binary tree of the following shape
node *init_tree()
{<!-- -->
node *node1 = (node *)malloc(sizeof(node));
node *node2 = (node *)malloc(sizeof(node));
node *node3 = (node *)malloc(sizeof(node));
node *node4 = (node *)malloc(sizeof(node));
node *node5 = (node *)malloc(sizeof(node));
node *node6 = (node *)malloc(sizeof(node));
node *node7 = (node *)malloc(sizeof(node));
node *node8 = (node *)malloc(sizeof(node));
node1->data = 1;
node2->data = 2;
node3->data = 3;
node4->data = 4;
node5->data = 5;
node6->data = 6;
node7->data = 7;
node8->data = 8;
node1->left = node2;
node1->right = node3;
node2->left = node4;
node2->right = node5;
node3->right = node6;
node5->left = node7;
node5->right= node8;
return node1;
}
Preorder traversal (recursive)
The preorder traversal order is root left and right. To traverse the entire binary tree, we need to traverse each subtree of the binary tree. For any subtree, the traversal method is sequential traversal from the root to the left. That is, all sub-problems are the same as the parent problem except for the size. Therefore, preorder traversal can be implemented recursively.
// Preorder traversal around the root
void pre_order_traversal(node *root)
{<!-- -->
if(root) {<!-- -->
cout<<root->data<<" ";
pre_order_traversal(root->left);
pre_order_traversal(root->right);
}
}
The traversal result is: 1 2 4 5 7 8 3 6
In-order traversal (recursive)
The in-order traversal order is Left Root Right. It only differs from preorder traversal in order, and the rest are the same.
//In-order traversal left root right
void in_order_traversal(node *root)
{<!-- -->
if(root) {<!-- -->
in_order_traversal(root->left);
cout<<root->data<<" ";
in_order_traversal(root->right);
}
}
The traversal result is: 4 2 7 5 8 1 3 6
Post-order traversal (recursive)
The postorder traversal order is left and right roots. It only differs from preorder and inorder traversals in order, and the rest are the same.
//Post-order traversal left and right roots
void post_order_traversal(node *root)
{<!-- -->
if(root) {<!-- -->
post_order_traversal(root->left);
post_order_traversal(root->right);
cout<<root->data<<" ";
}
}
The traversal result is: 4 7 8 5 2 6 3 1
Preorder traversal method one (non-recursive)
Because recursion is actually pushed onto the stack by the system, in theory all recursive algorithms can be changed to loop + stack implementation, then we first modify it to loop + according to the above Preorder traversal Stack shape. It should be noted that due to the first-in-last-out nature of the stack, in order to ensure that the left child is accessed before the right child, the right child should be pushed onto the stack first, and then the left child.
// Preorder traversal around the root
void pre_order_traversal(node *root)
{<!-- -->
stack<node *> s;
s.push(root);
while(!s.empty()) {<!-- -->
node *cur = s.top();
s.pop();
if(cur) {<!-- -->
cout<<cur->data<<" ";
s.push(cur->right);
s.push(cur->left);
}
}
}
The traversal result is: 1 2 4 5 7 8 3 6
Preorder traversal method 2 (non-recursive)
Now we change the idea to implement pre-order non-recursive traversal and carefully observe the recursive calling process of pre-order traversal.
- First put all left subtrees starting from the root node into the stack;
- Pop the top element of the stack
- If the top element of the stack has a right subtree, then the right subtree is pushed onto the stack
- Repeat the above process until the stack is empty
So we can write the traversal code
// Preorder traversal around the root
void pre_order_traversal(node *root)
{<!-- -->
stack<node *> s;
node *cur = root;
while(cur || !s.empty()) {<!-- -->
// Push all left subtrees onto the stack
while(cur) {<!-- -->
cout<<cur->data<<" ";
s.push(cur);
cur = cur->left;
}
if(!s.empty()) {<!-- -->
cur = s.top();
s.pop();
cur = cur->right;
}
}
}
The traversal result is: 1 2 4 5 7 8 3 6
In-order traversal (non-recursive)
With the previous foundation, let’s consider in-order traversal again, and we will find that in-order traversal and pre-order traversal only have different positions of printed nodes. Pre-order traversal prints when the node is pushed onto the stack, and in-order traversal only needs to be replaced by printing when the node is popped off the stack.
//In-order traversal left root right
void in_order_traversal(node *root)
{<!-- -->
stack<node *> s;
node *cur = root;
while(cur || !s.empty()) {<!-- -->
// Push all left subtrees onto the stack
while(cur) {<!-- -->
s.push(cur);
cur = cur->left;
}
if(!s.empty()) {<!-- -->
cur = s.top();
cout<<cur->data<<" ";
s.pop();
cur = cur->right;
}
}
}
The traversal result is: 4 2 7 5 8 1 3 6
Post-order traversal method one (non-recursive)
Postorder traversal is relatively more complicated. In pre-order and in-order traversal, as long as the left subtree is processed, the top element of the stack can actually be popped off the stack. However, post-order traversal requires both the left subtree and the right subtree to be processed before it can be popped off the stack. Obviously we need something method to record the traversal process.
In fact, we only need to record the previous node traversed to solve the problem, because through the previous node we can make the following judgments:
- If the previous node is the right subtree of the current node, it means that the right subtree has been traversed and can be popped off the stack.
- If the previous node is the left subtree of the current node and the current node has no right subtree, then it means that it can be popped off the stack.
- If the current node has neither a left subtree nor a right subtree, it is a leaf node, which means it can be popped off the stack.
If it does not fall into the above situation, push the right child and the left child of the current node onto the stack in sequence. This ensures that every time the top element of the stack is fetched, the left child is accessed before the right child, and both the left child and the right child are accessed. The parent node was visited previously.
//Post-order traversal left and right roots
void post_order_traversal(node *root)
{<!-- -->
stack<node *> s;
node *pre = NULL;
node *cur = root;
s.push(cur);
while(!s.empty()) {<!-- -->
cur = s.top();
//leaf node
if((!cur->left & amp; & amp; !cur->right) // leaf node
|| pre == cur->right // The previous node is the right subtree of the current node
|| (pre == cur->left & amp; & amp; !cur->right)) {<!-- --> // The previous node is the left subtree of the current node, and there is no right subtree
cout<<cur->data<<" ";
pre = cur;
s.pop();
} else {<!-- -->
if(cur->right)
s.push(cur->right);
if(cur->left)
s.push(cur->left);
}
}
}
The traversal result is: 4 7 8 5 2 6 3 1
Post-order traversal method 2 (non-recursive)
The order of post-order traversal is left and right roots. If this order is reversed, it will be root right and left. Do you find that it is very similar to pre-order traversal? Then I only need to traverse the root, right and left, and then drop the traversal results one by one. The stack has the function of dropping one by one, so I can write the following code.
//Post-order traversal left and right roots
void post_order_traversal(node *root)
{<!-- -->
stack<node *> s;
stack<int> ans;
node *cur = root;
while(cur || !s.empty()) {<!-- -->
// Push all left subtrees onto the stack
while(cur) {<!-- -->
ans.push(cur->data);
s.push(cur);
cur = cur->right;
}
if(!s.empty()) {<!-- -->
cur = s.top();
s.pop();
cur = cur->left;
}
}
while(!ans.empty()) {<!-- -->
cout<<ans.top()<<" ";
ans.pop();
}
}
The traversal result is: 4 7 8 5 2 6 3 1
Level-order traversal
Level-order traversal is breadth-first traversal, which can be achieved using queues.
//Level-order traversal
void breadth_first_order_traversal(node *root)
{<!-- -->
queue<node *> q;
q.push(root);
while(!q.empty()){<!-- -->
node *cur = q.front();
q.pop();
if(cur){<!-- -->
cout<<cur->data<<" ";
q.push(cur->left);
q.push(cur->right);
}
}
}
The traversal result is: 1 2 3 4 5 6 7 8