C++ program to implement binary tree traversals : inorder, preorder, postorder

C++ program to create binary tree and display the tree using inorder, preorder and postorder traversal.

C++ program to implement recursive inorder, preoder and postorder binary tree traversals

#include<iostream>
#include<conio.h>
using namespace std;
struct treenodes
{
    int data;
    treenodes *left;
    treenodes *right;
};
class tree
{
    treenodes *root;
public:
    void create();
    void inorder(treenodes *);
    void preorder(treenodes *);
    void postorder(treenodes *);
    treenodes *getroot()
    {
        return root;
    }
};
void tree::create()
{
    int flag;
    treenodes *temp;
    char ch,ch2;
    root=new treenodes;
    root->left=NULL;
    root->right=NULL;
    cout<<"Enter the element :";
    cin>>root->data;
    cout<<"Want to enter more element(Y/N) ";
    ch=getche();
    cout<<endl;
    while(ch=='y'||ch=='Y')
    {
        temp=root;
        flag=1;
        while(flag)
        {
            cout<<"Where to insert left or right(l/r) of "<<temp->data<<" ";
            ch2=getche();
            cout<<endl;
            if(ch2=='l'||ch2=='L')
            {
                if(temp->left==NULL)
                {
                    temp->left=new treenodes;
                    cout<<"Enter the element ";
                    cin>>(temp->left)->data;
                    (temp->left)->left=NULL;
                    (temp->left)->right=NULL;
                    flag=0;
                }
                else
                temp=temp->left;
            }
            else
            {
                if(temp->right==NULL)
                {
                    temp->right=new treenodes;
                    cout<<"Enter the element ";
                    cin>>(temp->right)->data;
                    (temp->right)->left=NULL;
                    (temp->right)->right=NULL;
                    flag=0;
                }
                else
                temp=temp->right;
            }
        }
        cout<<"Want to enter more element(Y/N) ";
        ch=getch();
        cout<<endl;
    }
}
void tree::inorder(treenodes *temp)
{
    if(temp==NULL)
        return ;
    inorder(temp->left);
    cout<<temp->data<<" ";
    inorder(temp->right);
}
void tree::preorder(treenodes *temp)
{
    if(temp==NULL)
        return;
    cout<<temp->data<<" ";
    preorder(temp->left);
    preorder(temp->right);
}
void tree::postorder(treenodes *temp)
{
    if(temp==NULL)
        return;
    postorder(temp->left);
    postorder(temp->right);
    cout<<temp->data<<" ";
}
int main()
{
    tree traversal;
    int a,flag=1;
    while(flag)
    {
        cout<<"Main Menu\n\t1.) Creation\n\t2.) Inorder Traversal\n\t3.) Preorder Traversal \n\t4.) Postorder Traversal\n\t5.) Exit";
        cout<<"\nEnter your choice ";
        cin>>a;
        switch(a)
        {
        case 1:
            traversal.create();
            break;
        case 2:
            cout<<"Inorder Traversal : ";
            traversal.inorder(traversal.getroot());
            break;
        case 3:
            cout<<"Preorder Traversal : ";
            traversal.preorder(traversal.getroot());
            break;
        case 4:
            cout<<"Postorder Traversal : ";
            traversal.postorder(traversal.getroot());
            break;
        case 5:
            flag=0;
            break;
        default:
            cout<<"Sorry wrong choice";
        }
        cout<<endl;
    }
}

OUTPUT

C++ program to implement non-recursive inorder, preoder and postorder binary tree traversals

#include<iostream>
#include<conio.h>
using namespace std;
struct treenodes
{
    int data;
    treenodes *left;
    treenodes *right;
};
class tree
{
    treenodes *root;
public:
    void create();
    void inorder();
    void preorder();
    void postorder();
};
void tree::create()
{
    int flag;
    treenodes *temp;
    char ch,ch2;
    root=new treenodes;
    root->left=NULL;
    root->right=NULL;
    cout<<"Enter the element :";
    cin>>root->data;
    cout<<"Want to enter more element(Y/N) ";
    ch=getche();
    cout<<endl;
    while(ch=='y'||ch=='Y')
    {
        temp=root;
        flag=1;
        while(flag)
        {
            cout<<"Where to insert left or right(l/r) of "<<temp->data<<" ";
            ch2=getche();
            cout<<endl;
            if(ch2=='l'||ch2=='L')
            {
                if(temp->left==NULL)
                {
                    temp->left=new treenodes;
                    cout<<"Enter the element ";
                    cin>>(temp->left)->data;
                    (temp->left)->left=NULL;
                    (temp->left)->right=NULL;
                    flag=0;
                }
                else
                temp=temp->left;
            }
            else
            {
                if(temp->right==NULL)
                {
                    temp->right=new treenodes;
                    cout<<"Enter the element ";
                    cin>>(temp->right)->data;
                    (temp->right)->left=NULL;
                    (temp->right)->right=NULL;
                    flag=0;
                }
                else
                temp=temp->right;
            }
        }
        cout<<"Want to enter more element(Y/N) ";
        ch=getch();
        cout<<endl;
    }
}
void tree::inorder()
{
    if(root==NULL)
    {
            cout<<"Empty "<<endl;
            return;
    }
    treenodes *temp=root,*stack[100];
    int top=-1;
    while(top>=0||temp!=NULL)
    {
        if(temp!=NULL)
        {
            stack[++top]=temp;
            temp=temp->left;
        }
        else if(temp==NULL)
        {
            cout<<stack[top]->data<<" ";
            temp=stack[top--]->right;
        }
    }
}
void tree::preorder()
{
    if(root==NULL)
    {
            cout<<"Empty "<<endl;
            return;
    }
    treenodes *temp=root,*stack[100];
    int top=-1;
    while(top>=0||temp!=NULL)
    {
        if(temp!=NULL)
        {
            cout<<temp->data<<" ";
            stack[++top]=temp->right;
            temp=temp->left;
        }
        else if(temp==NULL)
        {
            temp=stack[top--];
        }
    }
}
void tree::postorder()
{
    if(root==NULL)
    {
            cout<<"Empty "<<endl;
            return;
    }
    struct st
    {
        treenodes *node;
        int flag;
    };
    treenodes *temp=root;
    st stack[100];
    int top=-1;
    while(top>=0||temp!=NULL)
    {
        if(temp!=NULL)
        {
            stack[++top].node=temp;
            stack[top].flag=1;
            temp=temp->left;
        }
        else if(temp==NULL)
        {
            temp=(stack[top].node)->right;
            if(temp==NULL||stack[top].flag==0)
            {
                cout<<(stack[top--].node)->data<<" ";
                temp=NULL;
            }
            if(temp!=NULL)
            {
                stack[top].flag=0;
                temp=(stack[top].node)->right;
            }

        }
    }
}
int main()
{
    tree traversal;
    int a,flag=1;
    while(flag)
    {
        cout<<"Main Menu\n\t1.) Creation\n\t2.) Inorder Traversal\n\t3.) Preorder Traversal \n\t4.) Postorder Traversal\n\t5.) Exit";
        cout<<"\nEnter your choice ";
        cin>>a;
        switch(a)
        {
        case 1:
            traversal.create();
            break;
        case 2:
            cout<<"Inorder Traversal : ";
            traversal.inorder();
            break;
        case 3:
            cout<<"Preorder Traversal : ";
            traversal.preorder();
            break;
        case 4:
            cout<<"Postorder Traversal : ";
            traversal.postorder();
            break;
        case 5:
            flag=0;
            break;
        default:
            cout<<"Sorry wrong choice";
        }
        cout<<endl;
    }
}