Threaded Binary Tree:-
If a node in a binary tree is not having left or right child or it is a leaf node then that absence of child node is represented by the null pointers. The space occupied by these null entries can be utilized to store some kind of valuable information. One possible way to utilize this space is to have special pointer that point to nodes higher in the tree that is ancestors. These special pointers are called threads and the binary tree having such pointers is called threaded binary tree.
There are many ways to thread a binary tree each of these ways either correspond either in-order or pre-order traversal of T.A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (in actual sense, a link) to its INORDER successor. By doing this threading we avoid the recursive method of traversing a Tree, which makes use of stacks and consumes a lot of memory and time.
The node structure for a threaded binary tree varies a bit and its like this
struct NODE
{
struct NODE *leftchild;
int node_value;
struct NODE *rightchild;
struct NODE *thread;
}
The INORDER traversal for the above tree is -- D B A E C. So, the respective Threaded Binary tree will be --
B has no right child and its inorder successor is A and so a thread has been made in between them. Similarly, for D and E. C has no right child but it has no inorder successor even, so it has a hanging thread.
The algorithm for doing the above task is as follows;
Void inorder (NODEPTR root)
{
NODEPTR p, trail;
p = root;
do
{
trail = null;
while ( p!= null)
{
trail = p;
p = p -> left;
}
if (trail != null)
{
printf (“ %d\n”, trail->info);
p = trail -> right;
while ( trail -> rt && p != NULL)
{
printf (“%d/x”, p -> info);
trail =p;
p = p -> right;
}
}
} while (trail != NULL);
}
