Threaded Binary Trees

Threaded Binary Trees

• Basic concept : A threaded binary tree is a binary tree in which the NULL pointers of nodes are replaced with special pointers (threads) that point to the inorder predecessor or inorder successor of the node.

• These "threads" make inorder traversal faster and eliminate the need for recursion or stacks.

• We will discuss the inoder threading technique. The typical threaded binary tree looks like this

• The typical 'C' structure of the node is

typedef struct thread

{

   int data;

   int lth,rth;

   struct thread *left;

   struct thread *right;

}Th;

 

• The basic idea in inorder threading is that the left thread should point to the predecessor and the right thread points to the successor. Here we are assuming the head node as the starting node and the root node of the tree is attached to left of head node.

• Let us see the C++ program for the creation of threaded binary tree.

C++ Program

/************************************************************************

Program For Implementation Of Inorder Threaded Binary Search Treeand perform insertion, deletion and display of tree.

*** *********************************************************************/

#include<iostream>

using namespace std;

class thread

{

private:

typedef struct bst

{

   int data;

   int lth,rth;

   struct bst *left, *right;

}node;

node *dummy;

node *New,*root, *temp, *parent;

public:

thread();

void create(); //All The implementation Details are hidden!

void display();

void find();

void delet();

};

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The constructor defined

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

thread::thread()

{

   root=NULL;

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The create function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void thread::create()

{

   void insert(node *,node *);

   New=new node;

   New‒>left=NULL;

   New‒>right=NULL;

   New‒>lth=0;

   New‒>rth=0;

   cout<<"\n Enter The Element

   cin>>New‒>data;

   if(root= = NULL)

   {                    // Tree is not Created

      root=New;

      dummy=new node;

      dummy‒>data= ‒999;

      dummy‒>left=root;

      root‒>left=dummy;

      root‒>right=dummy;

   }

   else

      insert(root,New);

   }

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The display function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void thread::display()

{

void inorder(node *,node *dummy);

if(root= =NULL)

   cout<<"Tree Is Not Created";

else

{

   cout<<"\n The Tree is : ";

   inorder(root,dummy);

}

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The find function which calls the routine for searching an element

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void thread::find()

{

   node *search(node *,node *,int,node **);

   int key;

   cout<<"\n Enter The Element Which You Want To Search";

   cin>>key;

   temp=search(root, dummy,key,&parent);

   if(temp= = NULL)

      cout<<"\nElement is Not Present";

   else

      cout<<" It's Parent Node is "<<parent‒>data;

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The delet function which calls the routine for deletion of an element

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void thread::delet()

{

   void del(node *,node *,int);

   int key;

   cout<<"\n Enter The Element U wish to Delete";

   cin>>key;

   del(root,dummy,key);

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

This function is for creating a binary search tree

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void insert(node *root,node *New)

{

   if(New‒>data<root‒>data)

   {

      if(root‒>lth= =0)

      {

         New‒>left=root‒>left;

         New‒>right=root;

         root‒>left=New;

         root‒>lth=1;

      }

      else

         insert(root‒>left,New);

      }

   if(New‒>data>root‒>data)

   {

         if(root‒>rth= =0)

         {

            New‒>right=root‒>right;

            New‒>left=root;

            root‒>rth=1;

           root‒>right=New;

         }

    else

      insert(root‒>right,New);

}

}

*/

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The search function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

node *search(node *root,node "dummy,int key,node **parent)

{

node *temp;

int flag=0;

temp=root;

while((temp! =dummy))

{

   if(temp‒>data= =key)

   {

      cout<<"\n The "<<temp‒>data<<" Element is Present";

      flag=1;

      return temp;

   }

*parent=temp;

if(temp‒>data>key)

   temp=temp‒>left;

else

   temp=temp‒>right;

}

return NULL;

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

This function is for deleting a node from binary search tree There exists three possible cases for deletion of a node

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void del(node *root,node *dummy,int key)

{

node *temp,*parent,*temp_succ;

node *search(node *,node *,int,node **);

int flag=0;

temp=search(root,dummy,key,&parent);

if(root =temp)

{

   cout<<"\n Its Root Node Which Can Not Be Deleted!!";

   return;

}

//deleting a node with two children

if(temp‒>lth= =1 && temp‒>rth= =1)

{

   parent=temp;

   temp_succ=temp‒>right;//Finding Inorder successor

   while(temp_succ‒>lth= =1)

   {

      flag=1;

      parent=temp_succ;

      temp_succ=temp_succ>left;

   }

   if(flag= =0)

   {

      temp‒>data=temp_succ‒>data;

      parent‒>right=temp_succ‒>right;

      parent‒>rth=0;

   }

else//inorder successor is on left subbranch.

                  // and it has to be traversed

{

   temp‒>data=temp_succ‒>data;

   parent‒>rth=0;

   parent‒>lth=0;

   parent‒>left=temp_succ‒>left;

}

cout<<" Now Deleted it!";

return;

}

//deleting a node having only one child

//The node to be deleted has left child

 if(temp‒>lth= =1 && temp‒>rth‒=0)

{

if(parent‒>left= =temp)

{

 (temp‒>left)‒>right=parent;

parent‒>left=temp‒>left;

}

else

{

    (temp‒>left)‒>right=temp‒>right;

   parent‒>right=temp‒>left;

}

temp=NULL;

delete temp;

cout<<" Now Deleted it!";

return;

}

//The node to be deleted has right child

if(temp‒>lth= =0 && temp‒>rth!=0)

{

if(parent‒>left= =temp)

{

   parent‒>left=temp‒>right;

    (temp‒>right)‒>left=temp‒>left;

    (temp‒>right)‒>right=parent;

}

else

{

   parent‒>right=temp‒>right;

    (temp‒>right)‒>left=parent;

}

temp=NULL;

delete temp;

cout<<" Now Deleted it!";

retum;

}

//deleting a node which is having no child

if(temp‒>lth= =0 && temp‒>rth= =0)

{

   if(parent‒>left= =temp)

   {

      parent‒>left=temp‒>left;

      parent‒>lth=0;

   }

   else

   {

      parent‒>right=temp‒>right;

      parent‒>rth=0;

      cout<<" Now Deleted it!";

      return;

   }

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The inorder function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void inorder(node *temp,node *dummy)

{

   while(templ=dummy)

   {

      while(temp‒>lth= =1)

      temp=temp‒>left;

      cout<<" "<<temp‒>data;

      while(temp‒>rth= =0)

      {

         temp=temp‒>right;

         if(temp= =dummy)

         return;

         cout<<" "<<temp‒>data;

      }

      temp=temp‒>right;

   }

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The main function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void main()

{

int choice;

char ans='N';

thread th;

clrscr();

do

{

   clrscr();

   cout<<"\n\t Program For Threaded Binary Tree";

   cout<<"\n1.Create \n2.Display \n3.Search \n4.Delete";

   cin>>choice;

   switch(choice)

   {

   case 1:do

   {

      th.create();

      cout<<"\n Do u Want To enter More Elements?(y/n)";

      ans=getch();

   } while (ans= ='y');

   break;

   case 2:th.display();

   break;

   case 3:th.find();

   break;

   case 4:th.delet();

   break;

}

cout<<"\n\nWant To See Main Menu?(y/n)";

ans=getche();

while(ans= ='y');

}

Output

Program For Threaded Binary Tree.

1.Create

2.Display

3.Search

4.Delete1

Enter The Element 4

Do u Want To enter More Elements?(y/n)

Enter The Element 2

Do u Want To enter More Elements?(y/n)

Enter The Element 3

Do u Want To enter More Elements?(y/n)

Enter The Element 1

Do u Want To enter More Elements?(y/n)

Enter The Element 6

Do u Want To enter More Elements?(y/n)

Enter The Element 5

Do u Want To enter More Elements?(y/n)

Enter The Element 7

Do u Want To enter More Elements?(y/n)

Want To See Main Menu?(y/n)

Program For Threaded Binary Tree

1.Create

2.Display

3.Search

4.Delete2

The Tree is: 1 2 3 4 5 6 7

Want To See Main Menu?(y/n)

Program For Threaded Binary Tree

1.Create

2.Display

3.Search

4.Delete3

Enter The Element Which You Want To Search1

The 1 Element is Present It's Parent Node is 2

Want To See Main Menu?(y/n)

Program For Threaded Binary Tree

1.Create

2.Display

3.Search

4.Delete4

Enter The Element U wish to Delete2

The 2 Element is Present Now Deleted it!

Want To See Main Menu?(y/n)

Program For Threaded Binary Tree

1.Create

2.Display

3.Search

4.Delete2

The Tree is: 1 3 4 5 6 7

Want To See Main Menu?(y/n)

 

Logic explanation for threaded binary tree ‒

In thread binary tree, the NULL pointers are avoided. Instead of left NULL pointer the link points to inorder predecessor of that node. Similarly instead of right NULL pointer the link points to inorder successor of that node.

There are two additional fields in each node named as 1th and rth these fields indicate whether left or right thread is present. Thread present means the NULL link is replaced by a link to inorder predecessor or inorder successor. To represent that there exists thread the lth or rth Fields are set to 0. Let us take one example to explain how a threaded binary tree gets created. Suppose we want to create a threaded binary tree for the nodes haivng values ‒

10, 8, 6, 12, 9, 11, 14

Initially we will create a dummy node which will act as a header of the tree.

Now let us take first value i.e. 10. The node with value 10 will be the root node we will attach this root node as left child of dummy node.

The NULL links of root's left and right child will be pointed to dummy.

Now next comes 8. The 8 will be compared with 10, as the value is less than 10, we will attach 8 as left child of 10 and we will set root's lth field to 1, indicating that the node 10 is having left child. See then how the links are arranged.

New → left = root left

New → right = root;

root → left = New;

root → Ith = 1;

Note that the left link of node 8 points to its inorder predecessor and right link of node 8 points to its inorder successor.

Next comes 6. The value 6 will be first compared with root i.e. with 10. As 6 is less than 10, we will move on left sub‒branch. The 6 will then be compared with 8, so we have to move on left sub‒branched of 8. But 1th of node 8 is 0, indicating that there is no left child to 8, so we will attach 6 as left child to 8.

Then comes 12. We will compare 12 with 10. As 12 is greater than 10, we will attach the node 12 as right child of 10.

New →right = root → right

New → left = root

root →rth = 1

root → right = New

Note that the left field of node 12 points to its inorder predecessor and right field of node 12 points to its inorder sussessor. Thus by attaching 9, 11, 14 as appropriate children, the threaded binary tree will look like this ‒

Such a threaded tree is called inorder treaded binary tree.

Advantages of threaded binary tree :

1. In threaded binary tree there is no NULL pointer present. Hence memory wastage in occupying NULL links is avoided.

2. The threads are pointing to successor and predecessor nodes. This makes us to obtain predecessor and successor node of any node quickly.

3. There is no need of stack while traversing the tree, because using thread links we can reach to previously visited nodes.

Disadvantages of threaded binary tree :

1. Implementing threads for every possible node is complicated.

 

Example : 1

Construct inorder threaded binary tree for the following data:

Inorder : D‒E+C $ B*A‒G*F

Postorder : DE‒C+B$A*GF*‒

Write its preorder traversal. Represent stepwise construction.

Solution: Step 1:

Inorder : D‒E+C$B*A‒G*F

Postorder : DE‒C+B$A*GF*‒

The last node in postorder sequence ‒. is It is actually a root node. We will locate ‒ in inorder sequence. Left sequence of "‒" represent left subtree and right sequence of "‒" represent right subtree.

Step 2:

Step 3:

Step 4:

Step 5:

Step 6:

is the required threaded binary tree.

Preorder sequence

 ‒ * $+  D E C B A *  G F