544 Programming and Data Structures
Explanation In the above program, the following user-defined functions are given,
int insert (int) : This function is used for insertion of an element,
int del (int) : This function deletes a specific element.
int inorder (struct nodes *) : This function displays the elements in order traversal.
int preorder (struct nodes *) : This function is used to display the list of elements in preorder
traversal.
int postorder (struct nodes *) : This function displays the list of elements in postorder traversal
format.
int show (struct nodes*, int) : This function shows the elements in entered format.
For the details of above traversal methods read the topic Traversing Binary Trees.
15.6 BINARY SEARCH TREE
A binary search tree is a tree in which each node of the tree contains a value larger than all nodes of
their left subtree and smaller than all nodes of their right subtree. It is a very important data structure
and a particular element can be searched.
Fig. 15.13 shows the binary search tree.
Fig. 15.13 Binary search tree
15.7 INSERTION AND DELETION OPERATIONS
Searching and insertion operations are related with each other in a binary search tree. Before performing
insertion operation, the location where the element is to be inserted is known. For example, an element
is given and the task is to find and insert the element. This operation can be carried out as follows.
Compare the element with the root node element. The conditions would be as follows.
a) If element < root node element: If element is smaller than the element of the root node then select
left branch node and place it at the left side of the node.
b) If element> root node element: If element is greater than the element of the root node then place
the element in the right branch of root node.
This process is performed for all the nodes in the entire tree and an element is placed at the left when
its value is smaller than the root node and at the right side when its value is larger than the root node.
Finally, when our search is successful and we get the element having the same value as the element
to be inserted, we reach the accurate location to perform an insertion operation. Fig. 15.14 shows the
insertion operation.
Non-Linear Data Structure 545
Consider the following binary search tree.
(a) Before insertion
(b) After insertion
Fig. 15.14 Insertion in a binary search tree
We want to insert element 54. The comparison would be as follows.
a) (54<80): Here, 54 is smaller than 80 (root). Hence, next comparison will be done with the left
branch, that is, 50.
b) (54>50): Here, 54 is greater than 50 (left subtree). Hence, next comparison will be done with the
right branch node, that is, 90.
c) (54<58): Here, 58 is larger than 54. However, 58 does not have any branch and this is the exact
node where the element will be inserted, either left or right, as per the rules. Here, the element 54
is inserted at the left of node 58.
Deletion: Consider the following tree.
As shown in Fig. 15.15, we want to remove the element 95. The element (node 95) neither has a left
branch nor a right branch. This can be very easily seen from the above figure. Recall that in a single
linked list, the link pointer for the last element is assigned as NULL value. Therefore, it is marked as
end of the linked list. In the same way, the parent node of 95 is 90. 95 is the right branch of 90.
Therefore, 95 can be removed by assigning NULL value to its parent node, that is, 90. After, deletion
the binary search tree will as per Fig. 15.16.
Fig. 15.15 Model tree
546 Programming and Data Structures
Fig. 15.16 Tree after deletion
In case we want to remove the element 85, node 85 will have both left and right branches. In such a
case, follow the following steps.
1) The first element removed will be the inorder successor of 85, that is, 90.
2) As discussed in deletion operation, 90 can be deleted by giving NULL value to its parent node,
that is, 99.
3) Node 85 will be replaced with 90.
4) After replacing 85 with 90, pointer adjustment is to be done. The addresses of left and
right branches of 85 will be assigned to the left and right pointers of 90. In addition, the address
of the right pointer is given to its parent 72. Now, the binary tree will be as per Fig. 15.17.
Fig. 15.17 Tree after deletion
15.2 Write a program that performs insertion and deletion operation with binary search tree.
# Include <stdio.h>
# include <conio.h>
# include <process.h>
# include <malloc.h>
struct btree
{
struct b tree *ls,*rs;
int number;
} *r_node;
mainQ
Non-Linear Data Structure 547
int option,nums=l;
int ins item(int) ,del_item (int);
int in order (struct b t r e e * ), pre order (struct b t r e e * ) ;
int post order (struct b tree *);
int show (struct b_tre e*,int);
r_node=0;
clrscr();
for (;;)
{
puts ("nl.Insertion");
puts("2.Deletion”) ;
puts ( ” TRAVERSAL");
puts("3.Inorder ”);
puts ("4. Preorder”) ;
puts("5.Postorder");
puts ("6.Show Elements”) ;
puts(”7.Ex±tji");
puts ("Enter option : " );
scanf ("%d", fcoption);
switch (option)
{
case 1:
printf (* (Insertion ) Enter the nuober(O) to exit : ");
while (1)
{
scanf (”%d”,&xxums);
i f (nums»0) break;
ins item(nums);
}
break;
case 2:
printf ( ” (Remove) Enter the number : ”);
scanf ( ”%d”, &nums);
del item(nums);
break;
case 3:
puts ( ”n Inorder Traversal n”) ;
in order (r jaoda);
break;
case 4:
puts ( ”n preorder Traversal n ");
p re ord er(rn od e);
break;
548 Programming and Data Structures
case 5:
puts ("
postorder Traversal
") ;
post order (rn od e);
break;
case 6:
show(r node,1);
break;
case 7:
exit(0);
default:
printf ("Invalid opticnn");
}
}
>
search (int ele,struct b tree **p r,stru c t b tree **l_c)
{
struct b tree *p«tr, *p_«iav® 7
i£(r_nods—0)
{
* l j c * 0 ;
*p_r»0;
return 0;
}
i f (ele=«riKxJe->nunber)
{
*l_c=r_node;
*p_r»0;
return 0;
>
i f (ele<r_node->nunber)
pstr=r_node- >ls;
else
pstr=r node->rs;
p_save«rjoode;
while (pstrlsO)
{
i f (ele**pstr- >number)
{ *l_ca p str;
♦p rap save?
return 0;
}
p_save=pstr;
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.