C program for creation of Binary Search Tree with Preorder, Postorder and Inorder Traversals

".C" file is available in downloadable format at :

https://drive.google.com/file/d/0ByF0OId1bLx6ZHdHNFJaVGJ2R1E/view

(Open the link and click on the download arrow on the top right to download the file.)

Given Below is the code for creation of Binary Search Tree with Preorder, Postorder and Inorder Traversals :

---------------------------------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>

typedef struct tree
{
int info;
struct tree* left;
struct tree* right;
}node;



node* create (node*); 
void insert (node*, node*);
node* search (node*);
void display (node*);
node* del (node*, int);
node* preorder (node*);
node* inorder (node*);
node* postorder (node*);

node* create (node* root)
{

int no,ele,i;
node* n=NULL;

printf("\nNumber of entries:\t");
scanf("%d", &no);

for(i=0; i<no; i++)
{
printf("\n-------INSERT-------");
printf("\nEnter data:\t");
scanf("%d", &ele);

n=(node*)malloc(sizeof(node));
n->info = ele;
n->left=NULL; 
n->right=NULL;

if(root==NULL)
{
printf("\nIt's the first element of the tree.");
root=n;
}
else
{
insert(n, root);
}
}

printf("\n\nCREATED"); 

return root;
}


void insert (node* nw, node* root)
{
node *p;
node *q;
p=root; q=root;


while(q!=NULL)
{
p=q;

if(nw->info>q->info)
q=q->right;

else
q=q->left;
}

if(p->info > nw->info)
{
p->left = nw;
}
else
{
p->right = nw;
}
printf("\nInserted");
}


void display (node* root)
{

node *disp;
printf("\nDisplay Function.");

if(root!=NULL)
{
printf("\nLEFT:\t");
for(disp=root->left; disp!=NULL ; disp=disp->left)
printf(" %d ", disp->info);

printf("\nROOT:\t %d",root->info);

printf("\nRIGHT:\t");
for(disp=root->right; disp!=NULL ; disp=disp->right)
printf(" %d ", disp->info);
}

else
return;
printf("\n\n");
}


node* search(node* root)
{
node *q;
int ele;
q=root;

printf("Enter value to be searched:\t");
scanf("%d", &ele);

while((q!=NULL)&&(q->info!=ele))
{
if(q->info>ele)
q=q->left;
else
q=q->right;
}
printf("\nSearch Complete");
if(q==NULL) 
{
printf("\n%d doesn't exist in the tree.", ele);
}
else 
{
printf("\n%d found",q->info);
}
return q;
}


node* del(node* root, int ele)
{
node *temp, *r;
    if (root == NULL) return root;

    if (ele < root->info)
        root->left = del(root->left, ele);

    else if (ele > root->info)
        root->right = del(root->right, ele);

    else
    {
        if (root->left == NULL)
        {
            temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            temp = root->left;
            free(root);
            return temp;
        }

  r=root->right;
  while(r->left!=NULL)
  r=r->left;
 
        temp = r;
        
        root->info = temp->info;

        root->right = del(root->right, temp->info);
    }
    return root;
}

node* preorder (node* root)
{
node* q;
q=root;

if(q!=NULL)
{
printf("  |  %d  |  ", q->info);
q->left = preorder(q->left);
q->right = preorder(q->right);
}
return q;
}


node* inorder (node* q)
{
if(q!=NULL)
{
q->left=inorder(q->left);
printf("  |  %d  |  ", q->info);
q->right=inorder(q->right);
}
return q;
}  

node* postorder (node* q)
{
if(q!=NULL)
{
q->left=postorder(q->left);
q->right=postorder(q->right);
printf("  |  %d  |  ", q->info);
}
return q;
}  

void main()
{
node *root=NULL, *key;
int choice, val, check=0;


while(1)
{
printf("\n\n\n1. Create\n2. Display\n3. Search\n4. Delete a node.\n5. Preorder Traversal\n6. Inorder Traversal\n7. Postorder Traversal.\n8. Exit program.\n\nEnter your choice:\t");
scanf("%d", &choice);

switch(choice)

{
case 1: root=create(root); check=1; break;
case 2: if(check) display(root); else printf("\nNo data stored yet, first create the tree."); break;
case 3: key = search(root); break;
case 4: printf("Enter value to be deleted:\t"); scanf("%d", &val); root = del(root, val); printf("\nDeleted"); break;
case 5: preorder(root); break;
case 6: root=inorder(root); break;
case 7: root=postorder(root); break;
       case 8: if(root==NULL) printf("\nExiting with empty tree\n\n"); else { root->right=NULL; root->left=NULL; free(root); printf("\nFREED ROOT\n\n");} exit(0);


default: printf("\n\nHey!! Choose an option from the choices mentioned!!\n And stop testing my program!!");
}


}

}

---------------------------------------------------------------------------------