In this article i would like to present the binary tree basics and how to implement it using C program .
Binary tree is a data structure , in which each of its node will have at most two children which we refer them as left child and right child.
As we can see from above picture , parent node has got two child nodes( Node2,Node3). Node2 has got again two child nodes (left child and right child) . Node 3 has got only child to its right side (Right child) .
We can organize this tree in two ways .
- Binary tree
- Binary search tree
A Binary tree can have up to two leaf nodes and there is no rule in filling / building the tree . Where as in a binary search tree
- Parent node data should be greater than all of its leaf nodes data.
- Right node data should be greater than its left siblings data
First we will see how we can construct a binary search tree (addition/deletion/display) in all the possible ways (pre-order ,in-order & post-order)
struct binary_tree{
int data;
struct binary_tree *pleft;
struct binary_tree *pright;
};
As we can see it contains node element or data of the node and self referenced left and right nodes .
Now , to add a node to the tree we need to look at the root node i.e. the top node of the binary tree (like a great grand father !! ) if it exists need to add the node to its proper position . Proper position here i mean is if the data is lesser than its parent node data , it should go to left branch of the tree , and if it is more than its parent data it should got to right node .
Now this will be called as a " binary search tree "
void add_node(int data, struct binary_tree *tree)
{
struct binary_tree *temp = NULL;
if(root == NULL)
{
temp = malloc(sizeof(struct binary_tree));
temp->data = data;
temp->pleft = NULL;
temp->pright = NULL;
root = temp;
return ;
}
temp = tree ;
if(data < temp->data)
add_left_node(data,temp);
else if(data > temp->data)
add_right_node(data,temp);
else
printf("Duplicate entry , not adding \n");
return ;
}
/*Adding a Right node*/
void add_right_node( int data, struct binary_tree *tree)
{
struct binary_tree *temp = NULL;
if(tree->pright == NULL)
{
printf("Adding to the Right node \n");
temp = malloc(sizeof(struct binary_tree));
temp->data = data;
tree->pright = temp;
temp->pleft = NULL;
return ;
}
temp = tree->pright;
if(data < temp->data)
add_left_node(data,temp);
else
add_right_node(data,temp);
}
/*Adding a left node*/
void add_left_node( int data, struct binary_tree *tree)
{
struct binary_tree *temp = NULL;
if(tree->pleft == NULL)
{
temp = malloc(sizeof(struct binary_tree));
temp->data = data;
tree->pleft = temp;
temp->pright = NULL;
return ;
}
temp = tree->pleft;
if(data < temp->data)
add_left_node(data,temp);
else if(data > temp->data)
add_right_node(data,temp);
else
printf("Duplicate entry , not adding \n");
}
We have three traversal techniques
- Pre order
- In order
- Post order
We shall see all the three traversal methods
/*In order display*/
/*Display left node , Root node , Right node */
void display_tree_inorder(struct binary_tree *temp)
{
if(temp != NULL)
{
display_tree_inorder(temp->pleft);
printf("node = %d \n",temp->data);
display_tree_inorder(temp->pright);
}
}
/*Pre order display*/
/*Display Root node , left node ,Right node */
void display_tree_preorder(struct binary_tree *temp)
{
if(temp != NULL)
{
printf("node = %d \n",temp->data);
display_tree_preorder(temp->pleft);
display_tree_preorder(temp->pright);
}
}
/*Postorder display*/
/*Display Root node ,left node , Right node */
void display_tree_postorder(struct binary_tree *temp)
{
if(temp != NULL)
{
display_tree_postorder(temp->pleft);
display_tree_postorder(temp->pright);
printf("node = %d \n",temp->data);
}
}
Deleting a node is a tricky part in entire binary tree , i must tell you
- Case 1 : Both left child and right child are NULL
- Case 2 : Right child exists and Left child is NULL
- Casee 3 : Left child exists and Right child is NULL
- Case 4 : Right child & Left Child exists !!
- Case 4 .b - Only one right child and from then no left child
These are the combinations one needs to consider before deleting a node from a binary search tree , to make sure it builds up properly after you delete any node !!
/*Deleting a node*/
void delete_node(int data, struct binary_tree *temp)
{
struct binary_tree *current_node = NULL;
struct binary_tree *prev_node = NULL;
struct binary_tree *tmp_node = NULL;
prev_node = current_node =temp;
while(current_node)
{
if(current_node->data == data) /*It is the node to be deleted*/
{
/* Case 1 : Both left child and right child are NULL*/
if(current_node->pright == NULL && current_node->pleft == NULL)
{
if(current_node->data < prev_node->data)
prev_node->pleft = NULL;
else
prev_node->pright = NULL;
free(current_node);
return;
}
/* Case 2 : Right child exists and Left child is NULL*/
if(current_node->pright != NULL && current_node->pleft == NULL)
{
prev_node->pright = current_node->pright;
free(current_node);
return;
}
/*Casee 3 : Left child exists and Right child is NULL*/
else if (current_node->pleft != NULL && current_node->pright == NULL )
{
prev_node->pleft = current_node->pleft;
free(current_node);
return ;
}
else /*Case - 4*/
/*Right child & Left Child exists !!*/
{
prev_node = current_node;
tmp_node = current_node->pright;
if(tmp_node && tmp_node->pleft != NULL)
{
while(tmp_node->pleft != NULL)
{
current_node = tmp_node;
tmp_node = tmp_node->pleft;
}
prev_node->data = tmp_node->data;
current_node->pleft = tmp_node->pleft;
free(tmp_node);
return;
}
else /*Case 4 .b - Only one right child and from then no left child */
{
current_node->data = tmp_node->data;
current_node->pright = NULL;
free(tmp_node);
return;
}
}
}
else
{
prev_node = current_node ;
if(data < current_node->data)
current_node = current_node->pleft;
else
if(data > current_node->data)
current_node = current_node->pright;
}
}
}
void delete_data()
{
int data ;
printf("Enter the node data to be deleted \n");
scanf("%d",&data);
delete_node(data,root);
}
void main()
{
int i ;
int number ;
//char test[20]={20,19,18,16,15,14,17,21,22,23,24,25};
//char test[20]={8,10,14,13,3,6,1,4,7};
unsigned char test[20]={90,150,95,175,92,111,166,200,20,75,5,25,66,80};
for ( i =0 ; i<14 div="" i="">
{
number = rand() % 30 ;
//printf("adding number %d \n", number);
printf("adding number %d \n", test[i]);
//add_node(number ,root);
add_node(test[i] ,root);
}
display_tree_inorder(root);
}
Hope I have covered binary search tree in the most simple way to learn ! My next topic would be " how to find out if a binary tree is a binary search tree or not " . Till then bye :-)
No comments:
Post a Comment