#include<stdio.h>
#include<stdlib.h>
struct binary
{
int no; //Value Data Type
struct binary *left; //Left Link
struct binary *right; //Right Link
};
typedef struct binary *tree; //Pointer to Structure
int count = 0;
/*Prototypes for Documentation*/
tree insert(tree,int);
/* Insert
------
Inserts a node based on the Binary Search Tree condition.
The Binary Search Tree's condition is that any Node's
right child value will be greater than its own value and
left child value will be lesser than its own value.
An example of a Binary Search Tree:
(8) --> Root Node (Father of all Nodes)
/ \
/ \
Child Tree with one Child <-- (4) (9) --> Child Tree with two Children
/ /\
/ / \
(3) (6) (13) --> Leaf node with no Child
As you can see, the Root Node (8) is greater than its left child (4) and lesser than its right child (9).
Those two children in turn act as proper sub-trees themselves, following the Binary Search Tree conditions
with their children and so on.
Thus to insert a node, all we got to do is to traverse the tree based on the > or < conditions and place the node
where it ought to be inserted.
*/
tree delete(tree,int);
/* Delete
------
Deletion in Binary Search Tree is probably the most difficult thing to do, but that's only comparatively and
not to be taken as very difficult to do cause its easy, but just involves more than a single case to consider.
We can delete a leaf node by locating its value and using the free() method. But in cases where there are child
nodes available in the node to be deleted, we need to be careful.
For a single child node, all we need to do is shift the node's pointer to its next, be it left or right. That'd
delete the required value and yet have the tree under balance, pretty easy.
For a node with two children, we need to find the left most node of the right child of it and move it in place of
the node to be deleted and then free the left most node after this. Its easy too, but just needs a bit of extra
imagination.
*/
tree findmin(tree);
/* Find Minimum
---- -------
Finding the minimum value of the Tree is as easy as locating the left-most node of the tree.
Since the binary search tree conditions are such, we just have to traverse until the last left-most
node is reached.
*/
tree findmax(tree);
/* Find Maximum
---- -------
Similar to Find Minimum, with the only change being in locating the right-most node of the tree.
*/
void pretrav(tree);
/* Preorder Traversal
-------- ---------
Preorder Traversal is used to display the Tree in the order of Root Node first, Left Nodes second and Right Nodes last.
*/
void postrav(tree);
/* Postorder Traversal
--------- ---------
Postorder Traversal is used to display the Tree in the order of Right Nodes first, Left Nodes second and Root Node last.
*/
void intrav(tree);
/* Inorder Traversal
------- ---------
Inorder Traversal is used to display the Tree in the order of Left Nodes first, Root Node second and Right Nodes last.
This results in perfect compliance with the condition used to make the Tree and hence the name 'In Order'.
Thus this gives a sorted output in our case.
*/
int search(tree,int);
/* Searching
---------
Finally, the thing we build these trees for. Searching is an easy process. Start with the Root Node. If element's lesser
than its value, go left, else go right. Do the same for all the sub-trees thus encountered, and finally, return true or
false depending on the recursion reaching a NULL point or a case where both < and > fail and which means, the value was
found. Very efficient.
*/
int search(tree t, int item)
{
if(t!=NULL)
{
if(item==t->no)
{
return 1;
}
else
{
if(item<t->no)
{
return search(t->left,item);
}
else
{
if(item>t->no)
{
return search(t->right,item);
}
}
}
}
return 0;
}
int depth(tree t, int item)
{
tree p=t;
while(p!=NULL)
{
if(p->no==item)
{
return count;
}
else
{
if(item<p->no)
{
count++;
p=p->left;
}
else
{
if(item>p->no)
{
count++;
p=p->right;
}
}
}
}
return count;
}
void pretrav(tree t)
{
if(t!=NULL)
{
printf("%d ",t->no);
pretrav(t->left);
pretrav(t->right);
}
}
void intrav(tree t)
{
if(t!=NULL)
{
intrav(t->left);
printf("%d ",t->no);
intrav(t->right);
}
}
void postrav(tree t)
{
if(t!=NULL)
{
postrav(t->left);
postrav(t->right);
printf("%d ",t->no);
}
}
void createdisp()
{
printf("\n\nCreate a Binary Search Tree first ...\n\n");
}
tree empty(tree t)
{
if(t!=NULL)
{
t->left=empty(t->left);
t->right=empty(t->right);
free(t);
}
return NULL;
}
tree findmin(tree t)
{
if(t!=NULL)
{
while(t->left!=NULL)
{
t=t->left;
}
}
return t;
}
tree findmax(tree t)
{
if(t!=NULL)
{
while(t->right!=NULL)
{
t=t->right;
}
}
return t;
}
tree insert(tree t, int item)
{
if(t==NULL)
{
t=malloc(sizeof(struct binary));
t->no = item;
t->left=t->right=NULL;
}
else
{
if(item<t->no)
{
t->left=insert(t->left,item);
}
else
{
if(item>t->no)
{
t->right=insert(t->right,item);
}
}
}
return t;
}
tree delete(tree t, int item)
{
tree temp=NULL;
if(t==NULL)
{
printf("\nElement not found or Tree's empty\n");
}
else
{
if(item<t->no)
{
t->left=delete(t->left,item);
}
else
{
if(item>t->no)
{
t->right=delete(t->right,item);
}
else
{
if(t->right&&t->left)
{
temp=findmin(t->right);
t->no=temp->no;
t->right=delete(t->right,t->no);
}
else
{
temp=t;
if(t->left==NULL)
{
t=t->right;
}
else
{
if(t->right==NULL)
{
t=t->left;
}
free(temp);
}
}
}
}
}
return t;
}
int main()
{
int choice, dispchoice, created=0, item, i, number;
tree t=NULL, temp=NULL;
tree insert(tree,int);
while(1)
{
printf("\t\tBinary Search Tree\n\t\t------------------\n\n");
printf("Menu\n----\n\n1. Create\n2. Insert\n3. Delete\n4. Find Maximum\n5. Find Minimum\n6. Display\n7. Search\n8. Depth\n9. Exit\n\nChoice? : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
if(!created)
{
printf("\nCreating a Binary Search Tree\n\nHow many elements do you wish to enter? : ");
scanf("%d",&number);
printf("\nEnter the Root Node value: ");
scanf("%d",&item);
t=insert(t,item);
for(i=1;i<number;i++)
{
printf("\nEnter the value no. %d: ",i+1);
scanf("%d",&item);
t=insert(t,item);
}
created = 1;
printf("\nSearch Tree created with Root value %d\n\n",t->no);
}
else
{
t=empty(t);
printf("\nExisting Tree Emptied ...\n\nYou can now create a new tree.\n\n");
created=0;
}
break;
case 2:
if(created)
{
printf("\nInserting a node to the tree\n\nEnter the value to insert: ");
scanf("%d",&item);
t=insert(t,item);
printf("\nValue %d inserted into the tree\n\n",item);
}
else
{
createdisp();
}
break;
case 3:
if(created)
{
printf("\nDeleting a node from the tree\n\nEnter the value to delete from the tree: ");
scanf("%d",&item);
t=delete(t,item);
printf("\nValue %d deleted from the tree\n\n",item);
}
else
{
createdisp();
}
break;
case 4:
if(created)
{
temp = findmax(t);
printf("\nThe largest element in the tree is %d\n\n",temp->no);
}
else
{
createdisp();
}
break;
case 5:
if(created)
{
temp = findmin(t);
printf("\nThe smallest element in the tree is %d\n\n",temp->no);
}
else
{
createdisp();
}
break;
case 6:
printf("\n\nDisplay the Tree\n----------------\n\n");
printf("Menu\n----\n\n1. Preorder Traversal\n2. Inorder Traversal\n3. Postorder Traversal\n\nChoice? : ");
scanf("%d",&dispchoice);
switch(dispchoice)
{
case 1:
printf("\n\nThe tree in Preorder Traversal is: \n\n");
pretrav(t);
printf("\n");
break;
case 2:
printf("\n\nThe tree in Inorder Traversal is: \n\n");
intrav(t);
printf("\n");
break;
case 3:
printf("\n\nThe tree in Postorder Traversal is: \n\n");
postrav(t);
printf("\n");
break;
default:
printf("\n\nInvalid Choice, Retry ...\n\n");
}
break;
case 7:
printf("\n\nSearch an Element in the Tree\n-----------------------------\n\nEnter an element to search: ");
scanf("%d",&item);
if(search(t,item))
{
printf("\nElement %d present in the Tree\n\n",item);
}
else
{
printf("\nElement %d not present in the tree\n\n",item);
}
break;
case 8:
printf("\n\nDepth\n-----\n\nEnter the value to find the depth of: ");
scanf("%d",&item);
if(search(t,item))
{
printf("\nDepth of Element %d in the tree is: %d\n\n",item,depth(t,item));
}
else
{
printf("\nElement %d not present in the tree\n\n",item);
}
break;
case 9:
return 0;
}
}
}