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.
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 orInorder 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 :
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++ Function to find inorder successor of a node
//returns inorder successor using rthreadstruct 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 subtreeelse
{
ptr = ptr -> right;
while(ptr -> lthread == false)
ptr = ptr -> left;
return ptr;
}
}
Comments