Threaded binary Trees !!


Traversing the binary tree is the most important operation and used in almost every application. The iterative implementation of traversing the binary tree is implemented using either stack (simulation of recursion) or using the threaded binary trees , later being the more efficient. The idea is to maintain extra information of a particular traversal which saves a lot of pushing and popping in stack implementation. This is done by maintaining extra pointer to the leaf nodes (right child in case of right-in threaded binary tree, named on the basis of same) known as thread . This is done as follows:

While adding a left child in right-in threaded binary tree

– Point the right child of the node to its parent.

While adding a right child in right -in threaded binary tree

-Point the right child of the node to the thread of the parent

The thread is detected from the normal links by using a boolean field in the node , when set to true indicates that it is actually a thread .

Here is the implementation
struct tnode *insert(struct tnode *p , int val)
{
if(p==NULL)
{
p = (struct tnode *)malloc(sizeof(struct tnode));
p->data = val;
p->left = NULL;
p->right = NULL;
p->rthread=true;
}
else
{
struct tnode *q,*temp;
q=p;
temp=p;
while(q != NULL && q->rthread==false)
{
temp= q;
if( val >= temp->data )
q=temp->right;
else if( val < temp->data )
q=temp->left;
}
struct tnode *n;
n= (struct tnode *)malloc (sizeof(struct tnode));
n->data =val;
if( val >=temp->data )
{
if(temp->rthread)
{
struct tnode *r;
r=temp->right;
temp->right =n;
temp->rthread=false;
n->left=NULL;
n->right=r;
n->rthread=true;
}
}
else
{
temp->left = n;
n->left=NULL;
n->right=temp;
n->rthread=true;
}
}
return p;
}

A left-in-threaded binary tree  may be defined similarly, as one in which each NULL left pointer  is altered to contain a thread to that node’s inorder predecessor. An in-threaded binary tree may then be defined as a binary tree that is  both left in-threaded and right in-threaded. 

Advertisements
  1. #1 by Piendycreemem on August 3, 2008 - 4:11 am

    I agreed with you

  2. #2 by Miximmash on January 22, 2009 - 3:09 am

    Nothing seems to be easier than seeing someone whom you can help but not helping.
    I suggest we start giving it a try. Give love to the ones that need it.
    God will appreciate it.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: