A binary search tree (BST) is a node-based binary tree data structure with following properties:
1. The left subtree
of a node contains only nodes with keys less than the node's key.
2. The right subtree
of a node contains only nodes with keys greater than or equal to the node's key.
3. Both the left and
right subtrees must also be binary search trees.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef
struct BST
{
int
data;
struct
BST *left;
struct
BST *right;
}bNode;
int FindHeight(bNode *pr)
{
int
high,lf,rt;
high=lf=rt=0;
if(pr->left!=NULL)
lf=(1+FindHeight(pr->left));
else
if(pr->right!=NULL)
rt=(1+FindHeight(pr->right));
if(lf>rt)
high=lf;
else
high=rt;
return(high);
}
void
insert(bNode **root,int num)
{
if((*root)==NULL)
{
(*root)=(bNode
*)malloc(sizeof(bNode));
(*root)->data=num;
(*root)->left=NULL;
(*root)->right=NULL;
}
else
{
if((*root)->data>num)
insert(&(*root)->left,num);
else
if((*root)->data<num)
insert(&(*root)->right,num);
else
{
printf("\n\n\t
%d is an Exsiting Number......",num);
getch();
return;
}
}
}
void
Preorder(bNode *root)
{
if(root!=NULL)
{
printf(" %d",root->data);
Preorder(root->left);
Preorder(root->right);
}
}
void
Inorder(bNode *root)
{
if(root!=NULL)
{
Inorder(root->left);
printf(" %d",root->data);
Inorder(root->right);
}
}
void
Postorder(bNode *root)
{
if(root!=NULL)
{
Postorder(root->left);
Postorder(root->right);
printf(" %d",root->data);
}
}
void
Delete(bNode **root)
{
bNode
*ptr;
if(*root==NULL)
{
printf("\n\n\tTree
is Empty.........");
getch();
}
else
if((*root)->right==NULL)
{
ptr=*root;
*root=(*root)->left;
free(ptr);
}
else
if((*root)->left==NULL)
{
ptr=*root;
*root=(*root)->right;
free(ptr);
}
else
{
for(ptr=(*root)->right;ptr->left;ptr=ptr->left);
ptr->left=(*root)->left;
ptr=*root;
*root=(*root)->right;
free(ptr);
}
}
void
main()
{
int
num,ch;
bNode
*head;
clrscr();
head=(bNode
*)malloc(sizeof(bNode));
printf("\n\n\n\n\t\tCreating
a New Tree >> ");
printf("\n\n\t\tEnter
a Number for : ");
scanf("%d",&head->data);
head->left=NULL;
head->right=NULL;
do
{
clrscr();
printf("\n\n\n\t\t1. Add");
printf("\n\t\t2. Inorder");
printf("\n\t\t3. Preorder");
printf("\n\t\t4. Postorder");
printf("\n\t\t5. Delete");
printf("\n\t\t6. Caculate Height");
printf("\n\t\t7. Exit");
printf("\n\n\t\tEnter a choice :
");
scanf("%d",&ch);
switch(ch)
{
case
1:
clrscr();
printf("\n\tEnter a Number :
");
scanf("%d",&num);
insert(&head,num);
break;
case
2:
clrscr();
printf("\n\n\tInorder
Traversal :\n\n\t\t");
Inorder(head);
getch();
break;
case
3:
clrscr();
printf("\n\n\tPreorder
Traversal :\n\n\t\t");
Preorder(head);
getch();
break;
case
4:
clrscr();
printf("\n\n\tPostorder
Traversal :\n\n\t\t");
Postorder(head);
getch();
break;
case
5:
clrscr();
printf("\n\n
Deletion ................");
printf("\n\n One node has
been deleted ");
Delete(&head);
getch();
break;
case
6:
clrscr();
printf("\n\n\tHeight of Tree is = %d",FindHeight(head));
getch();
break;
case
7:
printf("\n\n\tQuit............");
getch();
exit(0);
default:
printf("\n\n\tInvalid Choice ......");
getch();
break;
}
}while(ch!=7);
}
No comments:
Post a Comment