Search operation is pretty simple in Threaded Binary tree, we just need to follow a simple algorithm
If search key == root
stop algorithm
Else-if search key < root
go to left thread
If search key > root
go to right thread
Node of threaded binary tree is represent as
structNode
{structNode *left, *right;int data;
bool lthread; //false if left pointers is a thread;bool rthread; //false if right pointer is a thread;
};
C++ Program for search operation
struct Node *search( struct Node *root , int key ){
Node *ptr = root ;
while( ptr != null )
{
if( ptr->info == key )
{
// indicating that the element is found thenreturn ptr ;
}
elseif( ptr->info < key )
{
// moving to inorder predecessor of the current node
ptr = ptr->right ;
}
else{
// moving to inorder successor of the current node
ptr = ptr->left ;
}
}
// if element is not found then we can return nullptr indicating element not // found in the given binary search treereturn nullptr ;
}
Comments