Threaded Binary Tree in Data Structure

Threaded Binary Tree

If a binary tree has n number of nodes, then the total number of links in the tree is 2n and the total number of NULL links is n+1. A.J. Perlis and C. Thorton jointly proposed an idea to make effective use of these NULL pointers. The basic idea is to replace the NULL pointers with some appropriate pointer values called Threaded Binary Tree.

The general rule is to replace the NULL left pointer of a node with the address of the immediate predecessor of this node and replace the NULL right pointer of a node with the address of the immediate successor of this node.
In the Threaded Binary Tree still, the left pointer of node D and the right pointer of node H is NULL.

Algorithm for find Inorder Successor of Threaded Binary Tree

Algorithm fnFindInorder_Successor(x)
{
ThreadTreeNode *p;
p=x->ptrRight;
if(x->rThread==0)
while(p->lThread==0)
p=p->ptrLeft;
return p;
} // End of Algorithm

Algorithm for find Inorder Predecessor of Threaded Binary Tree

Algorithm fnFindInorder_Predecessor(x)
{
ThreadTreeNode *p;
p=x->ptrLeft;
if(x->lThread==0)
while(p->rThread==0)
p=p->ptrRight;
return p;
} // End of Algorithm

Algorithm for Inorder Traversal of Threaded Binary Tree

ALgorithm fnInorder(H)
{
ThreadedTreeNode *Header;
Header=H;
while(1)
{
H=fnFindInorder_Successor(H);
if(H==Header)
return;
else
print(H->info);
}
} // End of Algorithm