Sunday 16 December 2012

Part I : Threaded Binary Search Tree ( Definition and Insertion)

Usually, in the binary tree, we notice more null links than acutal pointer.
In a binary tree with n nodes, we have
    2n = total links
    n+1 = null links
We can make use of these null links to point other nodes in the tree as a result of which we can traverse a tree without thre requirement of having stack. It can facilitate the traversal of all three viz Inorder, Preorder and Postorder traversal without the need of extra memory required.
In the memory representation, we must be able to distinguish between threads and normal pointer. This is done by adding two extra bit fields isright and isleft.

isleft=1 if parent->left is a normal pointer.
isleft=0 if parent ->left is a thread.

isright=1 if parent->right is a normal pointer.
isright=0 if parent->right is a thread.

If the node->right_child==NULL, now we will replace it by a pointer to the node which would be printed after P when traversing the tree in inorder.
If the node->left_child==NULL, we will replace it by a pointer to the node which immediately precedes node P in inorder.

However, we will still be having two pointers viz the one in the extreme left(directly down the left line from root) and the one in the extreme right(directly along the right line from root). To prevent it we will assume a head node for threaded binary trees.
The actual tree is the left subtree of the head node. And these two NULL pointers in the extreme points to this head node as well.

The following code is to declare a node structure for the threaded binary search tree and the insertion of the node in that tree.



struct node
{
    int info;
    struct node *left,*right;
    unsigned int isleft:1;
    unsigned int isright:1;
};
/* Be pretty clear here use UNSIGNED otherwise if you will use 1 bit signed number then it will be 0 and -1 so in the subsequent comparison you have to use -1 instead of 1. If you will use 1 bit unsigned number then it will behave like a binary 0 and 1 bit.*/

void insert(struct node *head_tree,int num)
{
    struct node *tree,*temp;
    tree=head_tree->left;
    if(head_tree->isleft==0)
    {
        head_tree->left=(struct node*)malloc(sizeof(struct node));
        head_tree->left->left=head_tree;
        head_tree->left->right=head_tree;
        head_tree->left->info=num;
        head_tree->isleft=1;
        head_tree->left->isleft=0;
        head_tree->left->isright=0;
        return;
    }
    while(1)
    {
        if((tree->isleft==0 && tree->info>=num) || (tree->isright==0 && tree->info<=num))
            break;
        else if(tree->info>num)
            tree=tree->left;
        else
            tree=tree->right;
    }
    temp=(struct node*)malloc(sizeof(struct node));
    temp->info=num;
    temp->left=NULL;
    temp->right=NULL;
    temp->isleft=0;
    temp->isright=0;
    if(tree->info>num)
    {
        temp->left=tree->left;
        temp->right=tree;
        tree->left=temp;
        tree->isleft=1;
    }
    else
    {
        temp->right=tree->right;
        temp->left=tree;
        tree->right=temp;
        tree->isright=1;
    }
}

No comments :

Post a Comment