This C++ program, without recursion, displays the nodes of a particular binary tree in inorder fashion without using recursive traversal.
Here is the source code of the C++ program to display the tree in inorder. The C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is also shown below.
/*
* C++ Program For Inorder Tree Traversal without recursion
*/
#include<iostream>
using namespace std;
#include<conio.h>
struct tree
{
tree *l, *r;
int data;
}*root = NULL, *p = NULL, *s = NULL;
struct node
{
tree *pt;
node *next;
}*q = NULL, *top = NULL, *np = NULL;
void create()
{
int value ,c = 0;
while (c < 6)
{
if (root == NULL)
{
root = new tree;
cout<<"enter value of root node\n";
cin>>root->data;
root->r = NULL;
root->l = NULL;
}
else
{
p = root;
cout<<"enter value of node\n";
cin>>value;
while(true)
{
if(value < p->data)
{
if (p->l == NULL)
{
p->l = new tree;
p = p->l;
p->data = value;
p->l = NULL;
p->r = NULL;
cout<<"value entered in left\n";
break;
}
else if (p->l != NULL)
{
p = p->l;
}
}
else if (value > p->data)
{
if (p->r == NULL)
{
p->r = new tree;
p = p->r;
p->data = value;
p->l = NULL;
p->r = NULL;
cout<<"value entered in right\n";
break;
}
else if(p->r != NULL)
{
p = p->r;
}
}
}
}
c++;
}
}
void push(tree *ptr)
{
np = new node;
np->pt = ptr;
np->next = NULL;
if (top == NULL)
{
top = np;
}
else
{
q = top;
top = np;
np->next = q;
}
}
tree *pop()
{
if (top == NULL)
{
cout<<"underflow\n";
}
else
{
q = top;
top = top->next;
return(q->pt);
delete(q);
}
}
void traverse(tree *p)
{
push(p);
while (top != NULL)
{
while (p != NULL)
{
push(p);
p = p->l;
}
if (top != NULL && p == NULL)
{
p = pop();
cout<<p->data<<endl;
p = p->r;
}
}
}
int main()
{
int val;
create();
cout<<"printing traversal in inorder\n";
traverse(root);
getch();
}
advertisement
Output enter value of root node 6 enter value of node 2 value entered in left enter value of node 9 value entered in right enter value of node 3 value entered in right enter value of node 5 value entered in right enter value of node 7 value entered in left printing traversal in inorder 2 3 5 6 7 9 6
Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.