Threaded binary tree

Since traversing the three is the most frequent operation, a method must be devised to improve the speed. In case of iterative traversal, speed is less than recursive one. So we cans use Threaded tree. If the right link of a node in a tree is NULL, it can be replaced by the address of its inorder successor. This tree is called right in-threaded binary tree. An extra field called the rthread is used.


If (rthread == 1), then it means that the right link of the node points to the inorder success.
If its equal to 0, then the right link represents an ordinary link connecting the right subtree.




Similarily left in-threaded tree in which each NULL left pointer is altered to contain a thread to that node's inorder predecessor.

There can be two types of threaded binary tree :-

1) Single Threaded :- i.e nodes are threaded either towards its inorder predecessor or successor.

2) Double threaded:- i.e nodes are threaded towards both the inorder predecessor and successor.


We may also define right and left pre-threaded binary tree, in which NULL right and left pointers of nodes are replaced by their preorder successors and predecessors. A right in and pre threaded tree can be traversed without the use of stack.


We consider the case of right in-threaded binary tree.
struct node
{
  int value;
  struct node *left;
  struct node *right;
  int rthread;
}


Function to find the inorder successor


node *inorder_successor(node *x)
{
  node *temp;

  temp = x->right;

  if(x->rthread==1)return(temp);

  while(temp->left!=NULL)temp = temp->left;

  return(temp);
}


Function to traverse the threaded tree in inorder


void inorder(node *head)
{
   node *temp;

   if(head->left==head)
   {
      printf("\nTree is empty!\n");
      return;
   }

   temp = head;

   for(;;)
   {
       temp = inorder_successor(temp);
       if(temp==head)return;
       printf("%d ", temp->value);
   }

}



Inserting toward the left of a node in a threaded binary tree.


void insert(int item, node *x)
{
   node *temp;
   temp = getnode();
   temp->value = item;
   x->left = temp;
   temp->left=NULL;
   temp->right=x;
   temp->rthread=1;
}


Function to insert towards the right of a node in a threaded binary tree.


void insert_right(int item, node *x)
{
   node *temp, r;

   temp=getnode();
   temp->info=item;
   r=x->right;
   x->right=temp;
   x->rthread=0;
   temp->left=NULL;
   temp->right=r;
   temp->rthread=1;
}


Function to find the inorder predecessor (for a left threaded binary three)


node *inorder_predecessor(node *x)
{
     node *temp;

     temp = x->left;

     if(x->lthread==1)return(temp);

     while(temp->right!=NULL)
       temp=temp->right;

     return(temp);
}