C++ Program to find Inoder Predecessor in Threaded Binary Tree
Description :
Threaded binary tree is a binary tree in which null pointers are replaced with either inorder predecessor or inorder successors. We have already seen insertion, displaying and deletion in Threaded binary tree.
( Insertion and Displaying - javascript:nicTemp(); )
( Deletion - javascript:nicTemp(); )
( Inorder Successor javascript:nicTemp(); )
Now lets see now to find inorder predecessor of a Node in Threaded Binary Tree
Inorder Predecessor : Inorder Predecessor of an input node can be defined as the node with the largest key smaller than the key of the input node.
Node of Threaded binary tree is defined as :
struct Node
{
struct Node *left, *right;
int data;
bool lthread; //false if left pointers is a thread;
bool rthread; //false if right pointer is a thread;
};
C++ Function to find inorder predecessor of a node
//returns inorder predecessor using lthread
struct Node *inorderpedecessor ( struct Node *ptr)
{
//if lthread is true, we can quickly find it
if( ptr -> lthread == true )
return ptr -> left;
//else return rightmost child of left subtree
else
{
ptr = ptr -> left;
while(ptr -> rthread == false)
ptr = ptr -> right;
return ptr;
}
}
Comments