Click here to hide categories Click here to show left categories

User: Home          welcome : Guest          Log In / Register here     




Tree Traversals implementation in C++

Download Attachment
#include < iostream.h>
#include < conio.h>
#include < malloc.h>

struct tree
{
    struct tree *left;
    int info;
    struct tree *right;
}*root,*ptr,*newnode,*par,*stack[100];

int loc=0;

void create();
void find(int);
void preorder();
void inorder();
void postorder();

void main()
{
    int i;
    clrscr();
    for(i=0;i<5;i++)
    {
        create();
    }
    preorder();
    inorder();
    postorder();
    getch();
}

void create()
{
    int item;
    cout<<"\nEnter the info: ";
    cin>>item;
    find(item);
    if(loc==1)
    {

    }
    else
    {
        newnode=(struct tree*)malloc(sizeof(struct tree));
        newnode->info=item;
        newnode->left=NULL;
        newnode->right=NULL;
        if(par==NULL)
        {
            root=newnode;
        }
        else if(iteminfo)
        {
            par->left=newnode;
        }
        else
        {
            par->right=newnode;
        }
    }
}

void find(int item)
{
    struct tree *save;
    if(root==NULL)
    {
        loc=0;
        par=NULL;
        return;
    }
    else if(item==root->info)
    {
        loc=1;
        par=NULL;
        return;
    }
    else if(iteminfo)
    {
        ptr=root->left;
        save=root;
    }
    else
    {
        ptr=root->right;
        save=root;
    }

    while(ptr!=NULL)
    {
        if(item==ptr->info)
        {
            loc=1;
            par=save;
            return;
        }
        else if(iteminfo)
        {
            save=ptr;
            ptr=ptr->left;
        }
        else
        {
            save=ptr;
            ptr=ptr->right;
        }
    }
    loc=0;
    par=save;
}

void preorder()
{
    int top=0;
    stack[0]=NULL;
    ptr=root;
    cout<<"\nPreorder Traversal of Tree is:\n";
    while(ptr!=NULL)
    {
        cout<info<<" ";
        if(ptr->right!=NULL)
        {
            top=top+1;
            stack[top]=ptr->right;
        }
        if(ptr->left!=NULL)
        {
            ptr=ptr->left;
        }
        else
        {
            ptr=stack[top];
            top=top-1;
        }
    }
}

void inorder()
{
    int top=0;
    stack[0]=NULL;
    ptr=root;
    cout<<"\nInorder Traversal of Tree is:\n";
    again:
    while(ptr!=NULL)
    {
        top=top+1;
        stack[top]=ptr;
        ptr=ptr->left;
    }
    ptr=stack[top];
    top=top-1;
    while(ptr!=NULL)
    {
        cout<info<<" ";
        if(ptr->right!=NULL)
        {
            ptr=ptr->right;
            goto again;
        }
        ptr=stack[top];
        top=top-1;
    }
}

void postorder()
{
    int top=0,temp,track[100];
    stack[0]=NULL;
    track[0]=-1;
    ptr=root;

    cout<<"\nPostorder Traversal of Tree is:\n";
    again:
    while(ptr!=NULL)
    {
        top=top+1;
        stack[top]=ptr;
        track[top]=0;
        if(ptr->right!=NULL)
        {
            top=top+1;
            stack[top]=ptr->right;
            track[top]=1;
        }
        ptr=ptr->left;
    }
    ptr=stack[top];
    temp=track[top];
    top=top-1;
    while(temp==0)
    {
        cout<info<<" ";
        ptr=stack[top];
        temp=track[top];
        top=top-1;
    }
    if(temp==1)
    {
        top=top+1;
        track[top]=0;
        top=top-1;
        goto again;
    }

}
Share this article   |    Print    |    Article read by 3678 times
Author:
Rohit kakria
I am software developer
Related Articles:
Related Interview Questions: No related interview question