Non-recursive traversal of binary trees
Recently, I read about six ways to write binary tree traversal. Previously, I only wrote it recursively. This time, I will try writing it non-recursively.
The idea of recursion is also the idea of stack. Since you don't need recursion, you use stack instead.
"Recursion = Stack"
1. Pre-order traversal
Pre-order traversal is accessed in the order Root Node-Left Child-Right Child.
a) Recursively implement prefix traversal:
void PreOrderTraverse(BiTNode *T) /*Recursive Pre-traversal*/
{
if (T==NULL)
return;
std::cout<<T->data<<"\t";
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
b) Non-recursive implementation of prefix traversal:
For root node P:
1) Access node P and stack node P;
2) Determine if the left child of node P is empty, if it is empty, take the top node of the stack and perform stack operation, and set the right child of the top node of the stack as the current node P, cycling to 1; if not, set the left child of P as the current node P;
3) The traversal ends until P is NULL and the stack is empty.
void nPreOrderTraverse(BiTNode *T) /*Non-recursive Pre-traversal*/
{
if (T==NULL)
return;
BiTNode *p;
p = T;
std::stack<BiTNode*> stk;
while(p!=NULL||!stk.empty())
{
while(p!=NULL)
{
std::cout<<p->data<<"\t";
stk.push(p);
p = p->lchild;
}
if(!stk.empty())
{
p = stk.top();
stk.pop();
p = p->rchild;
}
}
}
2. Intermediate traversal
Medium traversal is accessed in the order Left Child-Root Node-Right Child.
a) Recursive implementation of sequential traversal
void InOrderTraverse(BiTNode *T) /*Recursive Ordered Traversal*/
{
if (T==NULL)
return;
InOrderTraverse(T->lchild);
std::cout<<T->data<<"\t";
InOrderTraverse(T->rchild);
}
b) Ordered traversal in a non-recursive implementation
For root node P:
1) If its left child is not empty, put P on the stack and set the left child of P as the current P, then do the same for the current node P;
2) If the left child is empty, take the top element of the stack and perform stack operation, visit the top node of the stack, and then place the current P as the right child of the top node of the stack;
3) Until P is NULL and the stack is empty, the traversal ends.
void nInOrderTraverse(BiTNode *T) /*Non-recursive middle traversal*/
{
if(T==NULL)
return;
std::stack<BiTNode*> stk;
BiTNode* p;
p = T;
while(p!=NULL || !stk.empty())
{
while(p!=NULL)
{
stk.push(p);
p = p->lchild;
}
if(!stk.empty())
{
p = stk.top();
stk.pop();
std::cout<<p->data<<"\t";
p = p->rchild;
}
}
}
3. Post-order traversal
Post-order traversal is accessed in the order Left Child-Right Child-Root Node.
a) Recursive post-implementation traversal
void PostOrderTraverse(BiTNode *T) /*Recursive Successive Traverse*/
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
std::cout<<T->data<<"\t";
}
b) Non-recursive post-implementation traversal
To ensure that the root node is accessible only after the left and right children visit it, stack any node P first.If P does not have left and right children, you can access it directly; or P has left or right children, but both left and right children have been visited, you can also access the node directly.If not, the right and left children of P are placed on the stack in turn, which ensures that each time the top element of the stack is taken, the left child is visited in front of the right child, and the left and right children are visited in front of the root node.
For root node P:
1) Place P on the stack and set cur for the current node;
2) Set the current cur as the top node of the stack. If cur does not have left and right children, or cur has left or right children, but both left and right children have been visited, you can access the cur directly and stack out.Otherwise put cur's right and left children on the stack in turn;
3) until the stack is empty, the traversal ends.
void nPostOrderTraverse(BiTNode *T) /*Non-recursive postorder traversal*/
{
if(T==NULL)
return;
BiTNode* cur; /*current node*/
BiTNode* pre = NULL; /*Node of previous output*/
std::stack<BiTNode*> stk;
stk.push(T);
while(!stk.empty())
{
cur = stk.top();
if((cur->lchild==NULL && cur->rchild==NULL) ||
(pre!=NULL && (cur->lchild==pre || cur->rchild==pre)))
{ /*If the current node has no child nodes or the child nodes have been visited*/
std::cout<<cur->data<<"\t";
stk.pop();
pre = cur;
}
else
{
if(cur->rchild!=NULL)
stk.push(cur->rchild);
if(cur->lchild!=NULL)
stk.push(cur->lchild);
}
}
}
4. Complete test code
1)BiTree.h header file
/* BiTree.h header file */
#include<iostream>
#include<stack>
typedef char TElemType;
class BiTNode{ /*Create a node class using left-right child representation*/
public:
BiTNode():data(0),lchild(NULL),rchild(NULL){}
TElemType data;
BiTNode *lchild,*rchild;
};
void CreateBiTree(BiTNode **T) /*Binary tree, where the formal parameter is a double pointer, needs attention*/
{ /*The input here is an extended binary tree, where each node has a null pointer.*/
TElemType ch; /*Set its value to a specific value, in this code is'#'*/
std::cin>>ch;
std::cin.clear();
if(ch=='#')
*T=NULL;
else
{
*T=new BiTNode;
if(!*T)
exit(1);
(*T)->data=ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
void PreOrderTraverse(BiTNode *T) /*Recursive Pre-traversal*/
{
if (T==NULL)
return;
std::cout<<T->data<<"\t";
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
void nPreOrderTraverse(BiTNode *T) /*Non-recursive Pre-traversal*/
{
if (T==NULL)
return;
BiTNode *p;
p = T;
std::stack<BiTNode*> stk;
while(p!=NULL||!stk.empty())
{
while(p!=NULL)
{
std::cout<<p->data<<"\t";
stk.push(p);
p = p->lchild;
}
if(!stk.empty())
{
p = stk.top();
stk.pop();
p = p->rchild;
}
}
}
void InOrderTraverse(BiTNode *T) /*Recursive Ordered Traversal*/
{
if (T==NULL)
return;
InOrderTraverse(T->lchild);
std::cout<<T->data<<"\t";
InOrderTraverse(T->rchild);
}
void nInOrderTraverse(BiTNode *T) /*Non-recursive middle traversal*/
{
if(T==NULL)
return;
std::stack<BiTNode*> stk;
BiTNode* p;
p = T;
while(p!=NULL || !stk.empty())
{
while(p!=NULL)
{
stk.push(p);
p = p->lchild;
}
if(!stk.empty())
{
p = stk.top();
stk.pop();
std::cout<<p->data<<"\t";
p = p->rchild;
}
}
}
void PostOrderTraverse(BiTNode *T) /*Recursive Successive Traverse*/
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
std::cout<<T->data<<"\t";
}
void nPostOrderTraverse(BiTNode *T) /*Non-recursive postorder traversal*/
{
if(T==NULL)
return;
BiTNode* cur; /*current node*/
BiTNode* pre = NULL; /*Node of previous output*/
std::stack<BiTNode*> stk;
stk.push(T);
while(!stk.empty())
{
cur = stk.top();
if((cur->lchild==NULL && cur->rchild==NULL) ||
(pre!=NULL && (cur->lchild==pre || cur->rchild==pre)))
{ /*If the current node has no child nodes or the child nodes have been visited*/
std::cout<<cur->data<<"\t";
stk.pop();
pre = cur;
}
else
{
if(cur->rchild!=NULL)
stk.push(cur->rchild);
if(cur->lchild!=NULL)
stk.push(cur->lchild);
}
}
}
2)main file
#include"BiTree.h"
using namespace std;
int main()
{
BiTNode *T=new BiTNode;
std::cout<<"Please traverse the input nodes in order:";
CreateBiTree(&T);
cout<<"\n The prefix traversal output of the tree is:"<<endl;
PreOrderTraverse(T);
cout<<endl;
nPreOrderTraverse(T);
cout<<"\n The middle-order traversal output of the tree is:"<<endl;
InOrderTraverse(T);
cout<<endl;
nInOrderTraverse(T);
cout<<"\n The output of the post-order traversal of the tree is:"<<endl;
PostOrderTraverse(T);
cout<<endl;
nPostOrderTraverse(T);
cout<<endl;
return 0;
}
5. Test results
Reprinted at: https://www.cnblogs.com/fengty90/p/3768831.html