Friday, 24 November 2017

Binary Search Tree : A Non-Linear Data Structure

Definition: A binary search tree is a binary tree.  It may be empty. If it is not empty, it satisfies the following properties:
1. Every element has a key, and no two elements have the same key, that is, the keys are unique.
2. The keys in a nonempty left sub-tree must be smaller than the key in the root of the sub-tree.
3. The keys in a nonempty right sub-tree must be larger than the key in the root of the sub-tree.
4. The left and right sub-trees are also binary search trees.

Function for Inserting new element into Binary Search Tree:
To insert a new element, key, we must first verify that the key is different from those of existing elements.  To do this we search the tree.  If the search is unsuccessful, then we insert the element at the point the search terminated.

Important Note: ** The function modified_search that is slightly modified version of function search.  This function searches the binary search tree *node for the key number(num).  If the tree is empty or if number(num) is present, it returns NULL.  Otherwise, it returns a pointer to the last node of the tree that was encountered during the search.  The new element is to be inserted as a child of this node.

void   insert_node ( tree_ptr   *node, int   num )
{
tree_ptr   ptr, temp = modified_search ( *node, num );  // **
if ( temp  ||  !( *node ) )
{
ptr = new node;
if ( ptr = = NULL)
{
cout << “The memory is full \n”;
exit ( 1 );
}
ptr->data = num;
ptr->left_child = ptr->right_child = NULL;
if ( *node )
{
if ( num < temp->data )
temp->left_child = ptr;
else
temp->right_child = ptr;
}
else
*node = ptr;
}
}


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput