Threaded Binary Search Tree

 THREADED BINARY SEARCH TREE

THREADS:  We will replace certain NULL entries by spacial pointer which point to nodes higher in tree.These special pointer are called threads.

LINKS: Those pointers which contain the address of its successor node in tree is called link.

EXAMPLE:

RIGHT THREADED BINARY SEARCH TREE: Those tree which have only right threaded than it is known as right threaded  binary search tree.

LEFT THREADED BINARY SEARCH TREE: Those tree which have only left threaded than it is known as left threaded  binary search tree.

COMPLETE THREADED BINARY SEARCH TREE: Those binary search tree which contain both right thread and left thread is known as complete threaded binary search tree.

HEADER NODE OR DUMMY NODE: It is a header node created whose left child point to the root of threaded binary search tree.

CONDITION FOR CHECKING THREAD ARE LEFT OR RIGHT:

CREATE OR INSERT FUNCTION FOR THREADED BINARY SEARCH TREE:

struct node * create ( struct node *head , int d )

{

    struct node *newnode , *temp;

    /* Create new node */

    newnode = (struct node *) malloc (sizeof (struct node));

    newnode ➜ left =1;

    newnode  ➜ right =1;

    newnode  ➜ data =d ;

    /* Create head */

    if ( head == NULL )

    {

        head = ( struct node *) malloc (sizeof (struct node));

        head ➜ right =0;

        head ➜ left =0;

        head ➜ data =-999;

        head ➜ lc = newnode;

        head ➜ rc = head;

        newnode ➜ lc = head;

        newnode ➜ rc = head;

    }

    else

    {

        temp = head ➜ lc;

    }

    do

    {

        /* For right case */

        if (temp ➜ data < d )

        {

            if ( temp ➜ right ==1 )

            {

                newnode ➜ rc = temp ➜ rc;

                temp ➜ rc = newnode;

                newnode ➜ lc = temp;

                temp ➜ right = 0;

                return;  /* control is return back in create node statement */

            }

            else

            {

                temp = temp ➜ rc;

            }

        }

        else   /* For left case */

        {

            if (temp ➜ left == 1)

            {

                newnode ➜ lc = temp ➜ lc;

                temp ➜ lc = newnode;

                newnode ➜ rc = temp;

                temp ➜ left = 0;

                return;

            }

            else

            {

                temp = temp ➜ lc;

            }

        }

     }

    while (1);

    return

}

          

Examples

Trace the above function::

First create Newnode or allocate memory for Newnode

 /* Create new node */

    newnode = (struct node *) malloc (sizeof (struct node));

    newnode ➜ left =1;

    newnode  ➜ right =1;

    newnode  ➜ data =d ;

Second create Header and initialise to NULL

customise Head and Newnode

  /* Create head */

    if ( head == NULL )

    {

        head = ( struct node *) malloc (sizeof (struct node));

        head ➜ right =0;

        head ➜ left =0;

        head ➜ data =-999;

        head ➜ lc = newnode;

        head ➜ rc = head;

        newnode ➜ lc = head;

        newnode ➜ rc = head;

    }

Now if d= 50 than insert 50 in newnode at data part

Now finally we get :

Now if we want to insert suppose d= 60,50 than we perform following above steps such as 

1. First we assign newnode to temp.

2. Create newnode means allocate memory for newnode.

Finally we get

The above example is for the right case:

If we want to insert data such as d= 60 , 50 which is the example of left case

then we get