Monday, 28 July 2014

C++ program to create a binary search tree (BST) and to perform in-order, pre-order and post-order traversal

/* Program to create a BST and to perform in-order, pre-order and post-order traversal */
#include<iostream.h>
#include<alloc.h>
#include<conio.h>
#include<stdio.h>
#include<process.h>
#define NULL 0

class treenode
{
 private: int data;
treenode *left,*right,*currptr,*n,*ptr;

 public : void create(int );
void preorder(treenode *);
void inorder(treenode *);
void postorder(treenode *);
};

treenode *root;

void treenode::create(int item)
{
 n=new treenode;
 n->data=item;
 n->left=NULL;
 n->right=NULL;
 if(root==NULL)
   root=n;
 else
    {
currptr=root;
while(currptr!=NULL)
{
ptr=currptr;
currptr=(item>currptr->data)?currptr->right:currptr->left;
}
if(ptr->data<item)
 ptr->right=n;
else
 ptr->left=n;
    }
}

void treenode::preorder(treenode *ptr)
{
 if(ptr!=NULL)
   {
    cout<<" "<<ptr->data;
    preorder(ptr->left);
    preorder(ptr->right);
   }
}

void treenode::inorder(treenode *ptr)
{
 if(ptr!=NULL)
   {
    inorder(ptr->left);
    cout<<" "<< ptr->data;
    inorder(ptr->right);
   }
}

void treenode::postorder(treenode *ptr)
{
 if(ptr!=NULL)
   {
    postorder(ptr->left);
    postorder(ptr->right);
    cout<<" "<<ptr->data;
   }
}

void main()
{
 treenode t1;
 int ch,i,n,item;
 char ans;
 clrscr();
 cout<<"\nEnter the number of nodes:";
 cin>>n;
 cout<<"\nEnter the node values\n";
 for(i=0;i<n;i++)
    {
cin>>item;
t1.create(item);
    }
 while(1)
{
 cout<<"\n\n********MENU*********\n\n";
 cout<<"1.Preorder Traversal\n";
 cout<<"2.Inorder Traversal\n";
 cout<<"3.Postorder Traversal\n";
 cout<<"4.Exit";
 cout<<"\nEnter your choice:";
 cin>>ch;
 clrscr();
 switch(ch)
  {
case 1 : cout<<"\nPreorder Traversal\n";
   t1.preorder(root);
   break;

case 2 : cout<<"Inorder Traversal\n";
   t1.inorder(root);
   break;

case 3 : cout<<"Postorder Traversal\n";
   t1.postorder(root);
   break;

case 4 : exit(0);

default: cout<<"\nWrong choice\n";
  }
}
}

No comments:

Post a Comment