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.
#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
class node
{
public:
class node *left;
class node *right;
int data;
};
class tree: public node
{
public:
int stk[50], top;
node *root;
tree()
{
root = NULL;
top = 0;
}
void insert(int ch)
{
node *temp, *temp1;
if (root == NULL)
{
root = new node;
root->data = ch;
root->left = NULL;
root->right = NULL;
return;
}
temp1 = new node;
temp1->data = ch;
temp1->right = temp1->left = NULL;
temp = search(root, ch);
if (temp->data > ch)
temp->left = temp1;
else
temp->right = temp1;
}
node *search(node *temp, int ch)
{
if (root == NULL)
{
cout << "no node present";
return NULL;
}
if (temp->left == NULL && temp->right == NULL)
return temp;
if (temp->data > ch)
{
if (temp->left == NULL)
return temp;
search(temp->left, ch);
}
else
{
if (temp->right == NULL)
return temp;
search(temp->right, ch);
}
}
void display(node *temp)
{
if (temp == NULL)
return;
display(temp->left);
cout << temp->data << " ";
display(temp->right);
}
void postorder(node *root)
{
node *p;
p = root;
top = 0;
while (1)
{
while (p != NULL)
{
stk[top] = p->data;
top++;
if (p->right != NULL)
stk[top++] = -p->right->data;
p = p->left;
}
while (stk[top - 1] > 0 || top == 0)
{
if (top == 0)
return;
cout << stk[top - 1] << " ";
p = pop(root);
}
if (stk[top - 1] < 0)
{
stk[top - 1] = -stk[top - 1];
p = pop(root);
}
}
}
node * pop(node *p)
{
int ch;
ch = stk[top - 1];
if (p->data == ch)
{
top--;
return p;
}
if (p->data > ch)
pop(p->left);
else
pop(p->right);
}
};
int main(int argc, char **argv)
{
tree t1;
int ch, n, i;
while (1)
{
cout
<< "\n1.INSERT\n2.DISPLAY\n3.POSTORDER TRAVERSE\n4.EXIT\nEnter your choice:";
cin >> ch;
switch (ch)
{
case 1:
cout << "Enter no of elements to insert: ";
cin >> n;
for (i = 1; i <= n; i++)
{
cin >> ch;
t1.insert(ch);
}
break;
case 2:
t1.display(t1.root);
break;
case 3:
t1.postorder(t1.root);
break;
case 4:
exit(1);
}
}
}
Output:
$ 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
advertisement
Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.
Related Posts:
- Check Programming Books
- Check C++ Books
- Practice Computer Science MCQs
- Check Computer Science Books
- Apply for Computer Science Internship