C++ Program For Inorder Tree Traversal without Recursion

«
»
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.

  1. /*
  2.  * C++ Program For Inorder Tree Traversal without recursion
  3.  */
  4. #include<iostream>
  5. using namespace std;
  6. #include<conio.h>
  7. struct tree
  8. {
  9.     tree *l, *r;
  10.     int data;
  11. }*root = NULL, *p = NULL, *s = NULL;
  12. struct node
  13. {
  14.     tree *pt;
  15.     node *next;
  16. }*q = NULL, *top = NULL, *np = NULL;       
  17. void create()
  18. {
  19.     int value ,c = 0;      
  20.     while (c < 6)
  21.     {
  22.         if (root == NULL)
  23.         {
  24.             root = new tree;
  25.             cout<<"enter value of root node\n";
  26.             cin>>root->data;
  27.             root->r = NULL;
  28.             root->l = NULL;
  29.         }
  30.         else
  31.         {
  32.             p = root;
  33.             cout<<"enter value of node\n";
  34.             cin>>value;
  35.             while(true)
  36.             {
  37.                 if(value < p->data)
  38.                 {
  39.                     if (p->l == NULL)
  40.                     {
  41.                         p->l = new tree;
  42.                         p = p->l;
  43.                         p->data = value;
  44.                         p->l = NULL;
  45.                         p->r = NULL;
  46.                         cout<<"value entered in left\n";
  47.                         break;
  48.                     }
  49.                     else if (p->l != NULL)
  50.                     {
  51.                         p = p->l;
  52.                     }
  53.                 }
  54.                else if (value > p->data)
  55.                {
  56.                     if (p->r == NULL)
  57.                     {
  58.                         p->r = new tree;
  59.                         p = p->r;
  60.                         p->data = value;
  61.                         p->l = NULL;
  62.                         p->r = NULL;
  63.                         cout<<"value entered in right\n";
  64.                         break;
  65.                     }
  66.                     else if(p->r != NULL)
  67.                     {
  68.                        p = p->r;
  69.                     }
  70.                 }
  71.             }
  72.         }
  73.     c++;
  74.     }
  75. }
  76. void push(tree *ptr)
  77. {
  78.     np = new node;
  79.     np->pt = ptr;
  80.     np->next = NULL;
  81.     if (top == NULL)
  82.     {
  83.         top = np;
  84.     }
  85.     else
  86.     {
  87.         q = top;
  88.         top = np;
  89.         np->next = q;
  90.     }
  91. }
  92. tree *pop()
  93. {
  94.     if (top == NULL)
  95.     {
  96.         cout<<"underflow\n";
  97.     }
  98.     else
  99.     {
  100.         q = top;
  101.         top = top->next;
  102.         return(q->pt);
  103.         delete(q);
  104.     }
  105. }
  106. void traverse(tree *p)
  107. {
  108.     push(p);
  109.     while (top != NULL)
  110.     {
  111.         while (p != NULL)
  112.         {
  113.             push(p);
  114.             p = p->l;
  115.         }
  116.         if (top != NULL && p == NULL)
  117.         {
  118.             p = pop();
  119.             cout<<p->data<<endl;
  120.             p = p->r;
  121.         }
  122.     }
  123. }
  124. int main()
  125. {
  126.     int val;
  127.     create();
  128.     cout<<"printing traversal in inorder\n";
  129.     traverse(root);                 
  130.     getch();
  131. }

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.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn