C++ program to find Inorder Successor 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(); )
Now lets see now to find inorder successors of a Node in Threaded Binary Tree
Inorder Successor : Inorder successor of a node is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inorder traversal or Inorder Successor of an input node can also be defined as the node with the smallest key greater 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 successor of a node
//returns inorder successor using rthread
struct Node *inordersuccessor (struct Node *ptr)
{
//if rthread is true, we can quickly find it
if( ptr -> rthread == true )
return ptr->right;
//else return leftmost child of right subtree
else
{
ptr = ptr -> right;
while(ptr -> lthread == false)
ptr = ptr -> left;
return ptr;
}
}
Comments