Understanding the non recursive traversal of binary trees
- 2020-04-02 00:48:16
- OfStack
Binary tree is a very important data structure. Many other data structures are based on binary tree. For binary trees, there are three traversal methods: preorder, middle order and postorder. Because the definition of the tree itself is a recursive definition, it is not only easy to understand but also simple to implement the three traversals of the tree by using the recursive method. If the tree traversal is non-recursive, the stack is used to simulate the implementation. In the three kinds of traversal, the non-recursive algorithm of preorder and middle order traversal is easy to implement, while the non-recursive post-order traversal is relatively difficult to implement.
I. preorder traversal
The preorder traversal is accessed in root - left child - right child order.
1. Recursive implementation
2. Non-recursive implementation
According to the order in which the access is traversed in the preorder, the root node is accessed first, and then the left child and the right child are accessed respectively. That is, for any node, it can be regarded as the root node, so it can be directly accessed, after the visit, if its left child is not empty, according to the same rules to access its left subtree; When its left subtree is accessed, its right subtree is accessed. Therefore, the treatment process is as follows:
For any node P:
1) access node P and push node P;
2) determine whether the left child of node P is empty. If it is empty, then take the top node of the stack and carry out the operation of pushing out, and set the right child of the top node of the stack as the current node P, and loop to 1); If not, set the left child of P to the current node P;
3) until P is NULL and the stack is empty, the traversal ends.
Two. In order traversal
In the order of "left child - root - right child".
1. Recursive implementation
2. Non-recursive implementation
According to the order of traversal in the middle order, for any node, the left child can be accessed first, and the left child can be regarded as a root node, and then continue to visit its left child node, until the node with no left child node to access, and then according to the same rules to access its right subtree. Therefore, the treatment process is as follows:
For any node P,
1) if the left child is not null, then push P and set the left child of P to the current P, and then do the same processing for the current node P;
2) if the left child is empty, take the top element of the stack and carry out the operation of pushing out, access the top node of the stack, and then set the current P as the right child of the top node of the stack;
3) the traversal ends until P is NULL and the stack is empty
Three. After the order traversal
The post-order traversal is accessed in left-child-right-child-root order.
1. Recursive implementation
2. Non-recursive implementation
The non-recursive implementation of sequential traversal is the most difficult of the three traversal methods. Because in the post-order traversal, it is difficult to control the flow by ensuring that both left and right children are accessed and that the left child is accessed before the right child to access the root node. Here are two ideas.
The first way of thinking: for any node P, push it on the stack, and then search along its left subtree until the node with no left child is found. At this time, the node appears at the top of the stack, but it cannot be pushed out and accessed at this time, so its right child is still accessed. Therefore, the right subtree is processed in the same way according to the same rules. When the right child is accessed, the node appears at the top of the stack again, and it can be pushed out and accessed. This ensures the correct access order. As you can see, during this process, each node appears at the top of the stack twice, and can only be accessed when it appears at the top of the stack a second time. Therefore, you need to set an extra variable to identify whether the node appears at the top of the stack for the first time.
Second way of thinking: Make sure that the root is accessed after the left and right children, so push any node P first. If P does not have left and right children, it can be accessed directly; Or P has a left child or a right child, but the left child and the right child have both been accessed, so you can also access this node directly. If not, push P's right child and left child in turn, thus ensuring that each 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 before the root node.
Four. The entire program complete code
I. preorder traversal
The preorder traversal is accessed in root - left child - right child order.
1. Recursive implementation
void preOrder1(BinTree *root) //Recursive preorder traversal
{
if(root!=NULL)
{
cout<<root->data<<" ";
preOrder1(root->lchild);
preOrder1(root->rchild);
}
}
2. Non-recursive implementation
According to the order in which the access is traversed in the preorder, the root node is accessed first, and then the left child and the right child are accessed respectively. That is, for any node, it can be regarded as the root node, so it can be directly accessed, after the visit, if its left child is not empty, according to the same rules to access its left subtree; When its left subtree is accessed, its right subtree is accessed. Therefore, the treatment process is as follows:
For any node P:
1) access node P and push node P;
2) determine whether the left child of node P is empty. If it is empty, then take the top node of the stack and carry out the operation of pushing out, and set the right child of the top node of the stack as the current node P, and loop to 1); If not, set the left child of P to the current node P;
3) until P is NULL and the stack is empty, the traversal ends.
void preOrder2(BinTree *root) //Nonrecursive preorder traversal
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->data<<" ";
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
Two. In order traversal
In the order of "left child - root - right child".
1. Recursive implementation
void inOrder1(BinTree *root) //Order traversal in recursion
{
if(root!=NULL)
{
inOrder1(root->lchild);
cout<<root->data<<" ";
inOrder1(root->rchild);
}
}
2. Non-recursive implementation
According to the order of traversal in the middle order, for any node, the left child can be accessed first, and the left child can be regarded as a root node, and then continue to visit its left child node, until the node with no left child node to access, and then according to the same rules to access its right subtree. Therefore, the treatment process is as follows:
For any node P,
1) if the left child is not null, then push P and set the left child of P to the current P, and then do the same processing for the current node P;
2) if the left child is empty, take the top element of the stack and carry out the operation of pushing out, access the top node of the stack, and then set the current P as the right child of the top node of the stack;
3) the traversal ends until P is NULL and the stack is empty
void inOrder2(BinTree *root) //Nonrecursive order traversal
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
cout<<p->data<<" ";
s.pop();
p=p->rchild;
}
}
}
Three. After the order traversal
The post-order traversal is accessed in left-child-right-child-root order.
1. Recursive implementation
void postOrder1(BinTree *root) //Recursive sequential traversal
{
if(root!=NULL)
{
postOrder1(root->lchild);
postOrder1(root->rchild);
cout<<root->data<<" ";
}
}
2. Non-recursive implementation
The non-recursive implementation of sequential traversal is the most difficult of the three traversal methods. Because in the post-order traversal, it is difficult to control the flow by ensuring that both left and right children are accessed and that the left child is accessed before the right child to access the root node. Here are two ideas.
The first way of thinking: for any node P, push it on the stack, and then search along its left subtree until the node with no left child is found. At this time, the node appears at the top of the stack, but it cannot be pushed out and accessed at this time, so its right child is still accessed. Therefore, the right subtree is processed in the same way according to the same rules. When the right child is accessed, the node appears at the top of the stack again, and it can be pushed out and accessed. This ensures the correct access order. As you can see, during this process, each node appears at the top of the stack twice, and can only be accessed when it appears at the top of the stack a second time. Therefore, you need to set an extra variable to identify whether the node appears at the top of the stack for the first time.
void postOrder2(BinTree *root) //Nonrecursive sequential traversal
{
stack<BTNode*> s;
BinTree *p=root;
BTNode *temp;
while(p!=NULL||!s.empty())
{
while(p!=NULL) //Search down the left subtree until there is no left subtree node
{
BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
btn->btnode=p;
btn->isFirst=true;
s.push(btn);
p=p->lchild;
}
if(!s.empty())
{
temp=s.top();
s.pop();
if(temp->isFirst==true) //The representation appears at the top of the stack for the first time
{
temp->isFirst=false;
s.push(temp);
p=temp->btnode->rchild;
}
else //The second time appears at the top of the stack
{
cout<<temp->btnode->data<<" ";
p=NULL;
}
}
}
}
Second way of thinking: Make sure that the root is accessed after the left and right children, so push any node P first. If P does not have left and right children, it can be accessed directly; Or P has a left child or a right child, but the left child and the right child have both been accessed, so you can also access this node directly. If not, push P's right child and left child in turn, thus ensuring that each 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 before the root node.
void postOrder3(BinTree *root) //Nonrecursive sequential traversal
{
stack<BinTree*> s;
BinTree *cur; //The current node
BinTree *pre=NULL; //The node that was previously accessed
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
cout<<cur->data<<" "; //If the current node does not have children or child nodes are already accessed
s.pop();
pre=cur;
}
else
{
if(cur->rchild!=NULL)
s.push(cur->rchild);
if(cur->lchild!=NULL)
s.push(cur->lchild);
}
}
}
Four. The entire program complete code
#include <iostream>
#include<string.h>
#include<stack>
using namespace std;
typedef struct node
{
char data;
struct node *lchild,*rchild;
}BinTree;
typedef struct node1
{
BinTree *btnode;
bool isFirst;
}BTNode;
void creatBinTree(char *s,BinTree *&root) //Create A binary tree with s as A string in the form of A(B,C(D,E))
{
int i;
bool isRight=false;
stack<BinTree*> s1; //Storage nodes
stack<char> s2; //Store separator
BinTree *p,*temp;
root->data=s[0];
root->lchild=NULL;
root->rchild=NULL;
s1.push(root);
i=1;
while(i<strlen(s))
{
if(s[i]=='(')
{
s2.push(s[i]);
isRight=false;
}
else if(s[i]==',')
{
isRight=true;
}
else if(s[i]==')')
{
s1.pop();
s2.pop();
}
else if(isalpha(s[i]))
{
p=(BinTree *)malloc(sizeof(BinTree));
p->data=s[i];
p->lchild=NULL;
p->rchild=NULL;
temp=s1.top();
if(isRight==true)
{
temp->rchild=p;
cout<<temp->data<<" The right child is "<<s[i]<<endl;
}
else
{
temp->lchild=p;
cout<<temp->data<<" The left child is "<<s[i]<<endl;
}
if(s[i+1]=='(')
s1.push(p);
}
i++;
}
}
void display(BinTree *root) //Displays the tree structure
{
if(root!=NULL)
{
cout<<root->data;
if(root->lchild!=NULL)
{
cout<<'(';
display(root->lchild);
}
if(root->rchild!=NULL)
{
cout<<',';
display(root->rchild);
cout<<')';
}
}
}
void preOrder1(BinTree *root) //Recursive preorder traversal
{
if(root!=NULL)
{
cout<<root->data<<" ";
preOrder1(root->lchild);
preOrder1(root->rchild);
}
}
void inOrder1(BinTree *root) //Order traversal in recursion
{
if(root!=NULL)
{
inOrder1(root->lchild);
cout<<root->data<<" ";
inOrder1(root->rchild);
}
}
void postOrder1(BinTree *root) //Recursive sequential traversal
{
if(root!=NULL)
{
postOrder1(root->lchild);
postOrder1(root->rchild);
cout<<root->data<<" ";
}
}
void preOrder2(BinTree *root) // non Recursive preorder traversal
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->data<<" ";
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
void inOrder2(BinTree *root) // non Order traversal in recursion
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
cout<<p->data<<" ";
s.pop();
p=p->rchild;
}
}
}
void postOrder2(BinTree *root) // non Recursive sequential traversal
{
stack<BTNode*> s;
BinTree *p=root;
BTNode *temp;
while(p!=NULL||!s.empty())
{
while(p!=NULL) //Search down the left subtree until there is no left subtree node
{
BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
btn->btnode=p;
btn->isFirst=true;
s.push(btn);
p=p->lchild;
}
if(!s.empty())
{
temp=s.top();
s.pop();
if(temp->isFirst==true) //The representation appears at the top of the stack for the first time
{
temp->isFirst=false;
s.push(temp);
p=temp->btnode->rchild;
}
else //The second time appears at the top of the stack
{
cout<<temp->btnode->data<<" ";
p=NULL;
}
}
}
}
void postOrder3(BinTree *root) // non Recursive sequential traversal
{
stack<BinTree*> s;
BinTree *cur; //The current node
BinTree *pre=NULL; //The node that was previously accessed
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
cout<<cur->data<<" "; //If the current node does not have children or child nodes are already accessed
s.pop();
pre=cur;
}
else
{
if(cur->rchild!=NULL)
s.push(cur->rchild);
if(cur->lchild!=NULL)
s.push(cur->lchild);
}
}
}
int main(int argc, char *argv[])
{
char s[100];
while(scanf("%s",s)==1)
{
BinTree *root=(BinTree *)malloc(sizeof(BinTree));
creatBinTree(s,root);
display(root);
cout<<endl;
preOrder2(root);
cout<<endl;
inOrder2(root);
cout<<endl;
postOrder2(root);
cout<<endl;
postOrder3(root);
cout<<endl;
}
return 0;
}