A binary tree is a tree data
structure in which each node has at most two child nodes, usually distinguished
as "left" and "right". Nodes with children are parent
nodes, and child nodes may contain references to their parents. Outside the
tree, there is often a reference to the "root" node (the ancestor of
all nodes), if it exists. Any node in the data structure can be reached by
starting at root node and repeatedly following references to either the left or
right child.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct
Btree
{
char
data;
struct
Btree *left;
struct
Btree *right;
}*root;
char
Search(char ch,struct Btree **pr,struct Btree **Rt)
{
struct
Btree *ptr,*ptrs;
if(root==NULL)
{
*Rt=NULL;
*pr=NULL;
return;
}
if(ch==root->data)
//Checking the value in root position
{
*Rt=root;
*pr=NULL;
return;
}
if(ch)
ptr=root->left;
else
ptr=root->right;
ptrs=root;
while(ptr!=NULL)
{
if(ch==ptr->data)
{
*Rt=ptr;
*pr=ptrs;
return;
}
ptrs=ptr;
if(ch)
ptr=ptr->left;
else
ptr=ptr->right;
}
*Rt=NULL;
/*item not found*/
*pr=ptrs;
}
char insert(char ch)
{
struct
Btree *tmp,*prt,*lt;
Search(ch,&prt,<);
if(lt!=NULL)
{
printf("\n\tItem
already present");
return;
}
tmp=(struct
Btree *)malloc(sizeof(struct Btree));
tmp->data=ch;
tmp->left=NULL;
tmp->right=NULL;
if(prt==NULL)
root=tmp;
else
if(ch)
prt->left=tmp;
else
prt->right=tmp;
}
char
Chk_1(struct Btree *pr,struct Btree *Rt )
{
if(pr==NULL)
/*item to be deleted is root node*/
root=NULL;
else
if(Rt==pr->left)
pr->left=NULL;
else
pr->right=NULL;
}
char
Chk_2(struct Btree *pr,struct Btree *Rt)
{
struct
Btree *child;
if(Rt->left!=NULL)
child=Rt->left;
else
child=Rt->right;
if(pr==NULL
)
root=child;
else
if( Rt==pr->left)
pr->left=child;
else
pr->right=child;
}
char
Chk_3(struct Btree *pr,struct Btree *Rt)
{
struct
Btree *ptr,*ptrs,*nxt,*prnxt;
ptrs=Rt;
ptr=Rt->right;
while(ptr->left!=NULL)
{
ptrs=ptr;
ptr=ptr->left;
}
nxt=ptr;
prnxt=ptrs;
if(nxt->left==NULL
&& nxt->right==NULL)
Chk_1(prnxt,nxt);
else
Chk_2(prnxt,nxt);
if(pr==NULL)
root=nxt;
else
if(Rt==pr->left)
pr->left=nxt;
else
pr->right=nxt;
nxt->left=Rt->left;
nxt->right=Rt->right;
}
/******************************************/
/* Delete */
/******************************************/
char del(char ch)
{
struct
Btree *prt,*lt;
if(root==NULL)
{
printf("\n\tTree
empty");
return;
}
Search(ch,&prt,<);
if(lt==NULL)
{
printf("\n\tItem
not present in tree");
return;
}
if(lt->left==NULL
&& lt->right==NULL)
Chk_1(prt,lt);
if(lt->left!=NULL
&& lt->right==NULL)
Chk_2(prt,lt);
if(lt->left==NULL
&& lt->right!=NULL)
Chk_2(prt,lt);
if(lt->left!=NULL
&& lt->right!=NULL)
Chk_3(prt,lt);
free(lt);
}
/******************************************/
/* Display in Order of Insert */
/******************************************/
char
display(struct Btree *ptr,int level)
{
int
i;
if
( ptr!=NULL )
{
display(ptr->right,
level+1);
printf("\n");
for
(i = 0; i < level; i++)
printf(" ");
printf("%c",
ptr->data);
display(ptr->left,
level+1);
}
}
/******************************************/
/* Preorder */
/******************************************/
char
preorder(struct Btree *ptr)
{
if(root==NULL)
{
printf("\n\tTree
is empty");
return;
}
if(ptr!=NULL)
{
printf("%c
",ptr->data);
preorder(ptr->left);
preorder(ptr->right);
}
}/*End
of preorder()*/
/******************************************/
/* Inorder */
/******************************************/
char
inorder(struct Btree *ptr)
{
if(root==NULL)
{
printf("\n\tTree
is empty");
return;
}
if(ptr!=NULL)
{
inorder(ptr->left);
printf("%c
",ptr->data);
inorder(ptr->right);
}
}
/******************************************/
/* Postorder */
/******************************************/
char
postorder(struct Btree *ptr)
{
if(root==NULL)
{
printf("\n\tTree
is empty");
return;
}
if(ptr!=NULL)
{
postorder(ptr->left);
postorder(ptr->right);
printf("%c
",ptr->data);
}
}
void
main()
{
int
choice;
char
data;
root=NULL;
clrscr();
do
{
printf("\n\n");
printf("\t1.Insert\n");
printf("\t2.Display\n");
printf("\t3.Preorder\n");
printf("\t4.Inorder\n");
printf("\t5.Postorder\n");
printf("\t6.Delete\n");
printf("\t7.Quit\n");
printf("\tEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n\tEnter Character : ");
data=getche();
insert(data);
break;
case 2:
display(root,1);
break;
case 3:
printf("\n\t");
preorder(root);
break;
case 4:
printf("\n\t");
inorder(root);
break;
case 5:
printf("\n\t");
postorder(root);
break;
case 6:
printf("\n\tEnter the Character for Deletion : ");
data=getche();
del(data);
break;
case 7:
printf("\n\tQuiting..........");
getch();
exit(0);
default:
printf("\n\tInvalid Choice\n");
}
}while(choice!=8);
}
printf("\t4.Inorder\n");
printf("\t5.Postorder\n");
printf("\t6.Delete\n");
printf("\t7.Quit\n");
printf("\tEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n\tEnter Character : ");
data=getche();
insert(data);
break;
case 2:
display(root,1);
break;
case 3:
printf("\n\t");
preorder(root);
break;
case 4:
printf("\n\t");
inorder(root);
break;
case 5:
printf("\n\t");
postorder(root);
break;
case 6:
printf("\n\tEnter the Character for Deletion : ");
data=getche();
del(data);
break;
case 7:
printf("\n\tQuiting..........");
getch();
exit(0);
default:
printf("\n\tInvalid Choice\n");
}
}while(choice!=8);
}
No comments:
Post a Comment