C++ Program to Perform Postorder Non-Recursive Traversal of a Given Binary Tree

«
»
This is a C++ Program to print postorder traversal of the given binary tree without using recursion.

Here is source code of the C++ Program to Perform Postorder Non-Recursive Traversal of a Given Binary Tree. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<iostream>
  2. #include<conio.h>
  3. #include<stdlib.h>
  4.  
  5. using namespace std;
  6.  
  7. class node
  8. {
  9.     public:
  10.         class node *left;
  11.         class node *right;
  12.         int data;
  13. };
  14.  
  15. class tree: public node
  16. {
  17.     public:
  18.         int stk[50], top;
  19.         node *root;
  20.         tree()
  21.         {
  22.             root = NULL;
  23.             top = 0;
  24.         }
  25.         void insert(int ch)
  26.         {
  27.             node *temp, *temp1;
  28.             if (root == NULL)
  29.             {
  30.                 root = new node;
  31.                 root->data = ch;
  32.                 root->left = NULL;
  33.                 root->right = NULL;
  34.                 return;
  35.             }
  36.             temp1 = new node;
  37.             temp1->data = ch;
  38.             temp1->right = temp1->left = NULL;
  39.             temp = search(root, ch);
  40.             if (temp->data > ch)
  41.                 temp->left = temp1;
  42.             else
  43.                 temp->right = temp1;
  44.  
  45.         }
  46.         node *search(node *temp, int ch)
  47.         {
  48.             if (root == NULL)
  49.             {
  50.                 cout << "no node present";
  51.                 return NULL;
  52.             }
  53.             if (temp->left == NULL && temp->right == NULL)
  54.                 return temp;
  55.  
  56.             if (temp->data > ch)
  57.             {
  58.                 if (temp->left == NULL)
  59.                     return temp;
  60.                 search(temp->left, ch);
  61.             }
  62.             else
  63.             {
  64.                 if (temp->right == NULL)
  65.                     return temp;
  66.                 search(temp->right, ch);
  67.  
  68.             }
  69.         }
  70.  
  71.         void display(node *temp)
  72.         {
  73.             if (temp == NULL)
  74.                 return;
  75.             display(temp->left);
  76.             cout << temp->data << " ";
  77.             display(temp->right);
  78.         }
  79.         void postorder(node *root)
  80.         {
  81.             node *p;
  82.             p = root;
  83.             top = 0;
  84.  
  85.             while (1)
  86.             {
  87.                 while (p != NULL)
  88.                 {
  89.                     stk[top] = p->data;
  90.                     top++;
  91.                     if (p->right != NULL)
  92.                         stk[top++] = -p->right->data;
  93.                     p = p->left;
  94.                 }
  95.                 while (stk[top - 1] > 0 || top == 0)
  96.                 {
  97.                     if (top == 0)
  98.                         return;
  99.                     cout << stk[top - 1] << " ";
  100.                     p = pop(root);
  101.                 }
  102.                 if (stk[top - 1] < 0)
  103.                 {
  104.                     stk[top - 1] = -stk[top - 1];
  105.                     p = pop(root);
  106.                 }
  107.             }
  108.  
  109.         }
  110.         node * pop(node *p)
  111.         {
  112.             int ch;
  113.             ch = stk[top - 1];
  114.             if (p->data == ch)
  115.             {
  116.                 top--;
  117.                 return p;
  118.             }
  119.             if (p->data > ch)
  120.                 pop(p->left);
  121.             else
  122.                 pop(p->right);
  123.         }
  124. };
  125.  
  126. int main(int argc, char **argv)
  127. {
  128.     tree t1;
  129.     int ch, n, i;
  130.     while (1)
  131.     {
  132.         cout
  133.                 << "\n1.INSERT\n2.DISPLAY\n3.POSTORDER TRAVERSE\n4.EXIT\nEnter your choice:";
  134.         cin >> ch;
  135.         switch (ch)
  136.         {
  137.             case 1:
  138.                 cout << "Enter no of elements to insert: ";
  139.                 cin >> n;
  140.                 for (i = 1; i <= n; i++)
  141.                 {
  142.                     cin >> ch;
  143.                     t1.insert(ch);
  144.                 }
  145.                 break;
  146.             case 2:
  147.                 t1.display(t1.root);
  148.                 break;
  149.             case 3:
  150.                 t1.postorder(t1.root);
  151.                 break;
  152.             case 4:
  153.                 exit(1);
  154.         }
  155.     }
  156. }

Output:

advertisement
$ g++ NonRecursivePostorder.cpp
$ a.out
 
 
1.INSERT
2.DISPLAY
3.POSTORDER TRAVERSE
4.EXIT
Enter your choice:1
Enter no of elements to insert: 5
12 23 34 45 56
 
1.INSERT
2.DISPLAY
3.POSTORDER TRAVERSE
4.EXIT
Enter your choice:3
56 45 34 23 12 
 
1.INSERT
2.DISPLAY
3.POSTORDER TRAVERSE
4.EXIT
Enter your choice:4
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement

Here’s the list of Best Reference Books in C++ Programming, Data Structures and Algorithms.

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