BINARY TREE CREATION

# include <stdio.h>

# include <stdlib.h>

# include <alloc.h>

# define MAX 50/*Declaring maximum size of array used for stack and queue*/

struct node/*Declaring structure of a node*/

{

int info;

struct node *lchild;

struct node *rchild;

}*root;

struct node *stack[MAX];

int top=-1;/*Initializing top of stack*/

int front=-1,rear=-1;/*Initializing front and rear of queue*/

void find(int,struct node**,struct node**);

void main()

{

int choice,num,t,c,s,count=0,ch_t;

root=NULL;

void insert(int);

void del(int);

void nrec_pre(struct node*);

void nrec_in(struct node*);

void nrec_post(struct node*);

void display(struct node* ,int );

void level_trv(struct node* );

while(1)

{

printf("n.....Binary Search Tree Menu.....n");

printf("n1.Insertn");

printf("2.Traversaln");

printf("3.Deleten");

printf("4.Exitn");

printf("nEnter your choice : ");

scanf("%d",&choice);

switch(choice)

{

case 1:

printf("Enter the number to be inserted : ");

scanf("%d",&num);

insert(num);

count++;

break;

case 2:

printf("n....Tree traversal sub-menu....n");

printf("1.Inorder Traversaln");

printf("2.Preorder Traversaln");

printf("3.Postorder Traversaln");

printf("nEnter choice: ");

scanf("%d",&ch_t);

printf("n");

switch(ch_t)

{

case 1:

if(root==NULL)

{

printf("nTree is empty.n");

break ;

}

nrec_in(root);

break;

case 2:

if(root==NULL)

{

printf("nTree is empty.n");

break ;

}

nrec_pre(root);

break;

case 3:

if(root==NULL)

{

printf("nTree is empty.n");

break ;

}

nrec_post(root);

break;

default:

printf("nWrong choicen");

}

break;

case 3:

printf("Enter the number to be deleted : ");

scanf("%d",&num);

del(num);

break;

case 4: return;

default:

printf("nWrong choicen");

}

}

}

/*This function inserts an element into the tree*/

void insert(int item)

{

struct node *tmp,*parent,*location;

find(item,&parent,&location);

if(location!=NULL)

{

printf("nItem already present.n");

return;

}

tmp=(struct node *)malloc(sizeof(struct node));

tmp->info=item;

tmp->lchild=NULL;

tmp->rchild=NULL;

if(parent==NULL)

root=tmp;

else

if(item<parent->info)

parent->lchild=tmp;

else

parent->rchild=tmp;

}

/*Function to find the position of insertion */

void find(int item,struct node **par,struct node **loc)

{

struct node *ptr,*ptrsave;

if(root==NULL)/*Tree empty*/

{

*loc=NULL;

*par=NULL;

return;

}

if(item==root->info)/*Item is at root*/

{

*loc=root;

*par=NULL;

return;

}

/*Initialize ptr and ptrsave*/

if(item<root->info)

ptr=root->lchild;

else

ptr=root->rchild;

ptrsave=root;

while(ptr!=NULL)/*Until end is reached*/

{

if(item==ptr->info)

{ *loc=ptr;

*par=ptrsave;

return;

}

ptrsave=ptr;

if(item<ptr->info)

ptr=ptr->lchild;

else

ptr=ptr->rchild;

}

*loc=NULL;/*Item not found*/

*par=ptrsave;

}

/*Case in which no child is prsent*/

void case_a(struct node *par,struct node *loc )

{

if(par==NULL) /*item to be deleted is root node*/

root=NULL;

else

if(loc==par->lchild)

par->lchild=NULL;

else

par->rchild=NULL;

}

/*Case in which one child is present*/

void case_b(struct node *par,struct node *loc)

{

struct node *child;

/*Initialize child*/

if(loc->lchild!=NULL) /*item to be deleted has lchild */

child=loc->lchild;

else /*item to be deleted has rchild */

child=loc->rchild;

if(par==NULL ) /*Item to be deleted is root node*/

root=child;

else

if( loc==par->lchild) /*item is lchild of its parent*/

par->lchild=child;

else /*item is rchild of its parent*/

par->rchild=child;

}

/*Case in which two children are present*/

void case_c(struct node *par,struct node *loc)

{

struct node *ptr,*ptrsave,*suc,*parsuc;

/*Find inorder successor and its parent*/

ptrsave=loc;

ptr=loc->rchild;

while(ptr->lchild!=NULL)

{

ptrsave=ptr;

ptr=ptr->lchild;

}

suc=ptr;

parsuc=ptrsave;

if(suc->lchild==NULL && suc->rchild==NULL)

case_a(parsuc,suc);

else

case_b(parsuc,suc);

if(par==NULL) /*if item to be deleted is root node */

root=suc;

else

if(loc==par->lchild)

par->lchild=suc;

else

par->rchild=suc;

suc->lchild=loc->lchild;

suc->rchild=loc->rchild;

}

/*This function deletes an element from tree*/

void del(int item)

{

struct node *parent,*location;

if(root==NULL)

{

printf("Tree empty");

return;

}

find(item,&parent,&location);

if(location==NULL)

{

printf("Item not present in tree");

return;

}

if(location->lchild==NULL && location->rchild==NULL)

case_a(parent,location);

if(location->lchild!=NULL && location->rchild==NULL)

case_b(parent,location);

if(location->lchild==NULL && location->rchild!=NULL)

case_b(parent,location);

if(location->lchild!=NULL && location->rchild!=NULL)

case_c(parent,location);

free(location);

}

/*Tree traversal in non-recursive preorder */

void nrec_pre(struct node *ptr)

{

void push(struct node*);

struct node* pop();

push(ptr);

while(top!=-1)

{

ptr=pop();

if(ptr!=NULL)

{

printf("%d ",ptr->info);

push(ptr->rchild);

push(ptr->lchild);

}

}

}

/*Tree traversal in non-recursive inorder*/

void nrec_in(struct node *ptr)

{

void push(struct node*);

struct node* pop();

while(top!=-1||ptr!=NULL)

{

if(ptr!=NULL)

{

push(ptr);

ptr=ptr->lchild;

}

else

{

ptr=pop();

printf("%d ",ptr->info);

ptr=ptr->rchild;

}

}

printf("nn");

}

/*Tree traversal in non-recursive postorder*/

void nrec_post(struct node *ptr)

{

void push(struct node*);

struct node* pop();

int flag[MAX];

int top_prev;

push(NULL);

do

{

while(ptr!=NULL)

{

push(ptr);

flag[top]=1;

if(ptr->rchild!=NULL)

{

push(ptr->rchild);

flag[top]=-1;

}

ptr=ptr->lchild;

}

top_prev=top;

ptr=pop();

while(flag[top_prev]==1)

{

printf("%d ",ptr->info);

top_prev=top;

ptr=pop();

}

}while(ptr!=NULL);

printf("nn");

}

/*This function pushes an element into strack*/

void push(struct node *node)

{

if(top > MAX)

{

printf("Stack overflown");

return;

}

else

{

top=top+1;

stack[top] = node;

}

}

/*This function pops an element from stack*/

struct node *pop()

{

if (top == -1 )

{

printf("Stack underflow n");

return;

}

else

return (stack[top--]);

}

Output:

.....Binary Search Tree Menu.....n

1.Insertn

2.Traversaln

3.Deleten

4.Exitn

Enter your choice : 1

Enter the number to be inserted : 2

.....Binary Search Tree Menu.....n

1.Insertn

2.Traversaln

3.Deleten

4.Exitn

Enter your choice : 1

Enter the number to be inserted : 4

.....Binary Search Tree Menu.....n

1.Insertn

2.Traversaln

3.Deleten

4.Exitn

Enter your choice : 1

Enter the number to be inserted : 6

.....Binary Search Tree Menu.....n

1.Insertn

2.Traversaln

3.Deleten

4.Exitn

Enter your choice : 2

....Tree traversal sub-menu....n

1.Inorder Traversaln

2.Preorder Traversaln

3.Postorder Traversaln

4.Enter choice: 1

2 4 6 nn

.....Binary Search Tree Menu.....n

1.Insertn

2.Traversaln

3.Deleten

4.Exitn

Enter your choice : 2

....Tree traversal sub-menu....n

1.Inorder Traversaln

2.Preorder Traversaln

3.Postorder Traversaln

4.Enter choice: 3

6 4 2 nn

.....Binary Search Tree Menu.....n

1.Insertn

2.Traversaln

3.Deleten

4.Exitn

Enter your choice : 2

....Tree traversal sub-menu....n

1.Inorder Traversaln

2.Preorder Traversaln

3.Postorder Traversaln

4.Enter choice: 4

Wrong choicen

.....Binary Search Tree Menu.....n

1.Insertn

2.Traversaln

3.Deleten

4.Exitn

Enter your choice : 3

Enter the number to be deleted : 2

.....Binary Search Tree Menu.....n

1.Insertn

2.Traversaln

3.Deleten

4.Exitn

Enter your choice : 4