CODE FOR THREADED BINARY TREE

THREADED BINARY TREE IMPLEMENTATION (C++ CODE)

Last Updated On: 12th Dec 2015

Introduction

If we consider the case of Binary Tree creation, for the leaf nodes there is no sub tree further. So we are just setting the left and right fields of leaf nodes to NULL. Since NULL value is put in the left and right field of the node, it is just a wastage of the memory. So to avoid null values in the node we just set the threads which are actually the links to the predecessor and successor nodes.

There are three types of threading possible:

• Inorder Threading
• Preorder Threading
• Postorder Threading 

In this tutorial we will be looking at Inorder Threading Technique which is the most famous one. The typical C structure of the node of Threaded Binary Tree would like :

typedef struct bst
  {
   int data;
   int lth,rth;
   struct bst *left,*right;
  }

And The typical threaded binary tree looks like this:

Now let's see the code for threaded binary tree in action:

# include <iostream.h>
# include <conio.h>
 typedef struct bst
  {
   int data;
   int lth,rth;
   struct bst *left,*right;
  }node;
class thread
{
  private:

  node *dummy;
  node *New,*root,*temp,*parent;
 public:
 thread();
 void create(); //All The implementation Details are hidden!
 void display();
 void find();
 void delet();
};
/*
--------------------------------------------------------------------------
constructor 
--------------------------------------------------------------------------
*/
thread::thread()
{
 root=NULL;
}
/*
--------------------------------------------------------------------------
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);
}

/*
--------------------------------------------------------------------------
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);
            }
}
/*
--------------------------------------------------------------------------
find function which calls the routine for searching an elemnt
--------------------------------------------------------------------------
*/
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;
}
/*
--------------------------------------------------------------------------
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);
}
/*
--------------------------------------------------------------------------
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);
  }
}
/*
--------------------------------------------------------------------------
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;
}

/*
--------------------------------------------------------------------------
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!";
   return;
  }
  //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;
  }
}
/*
--------------------------------------------------------------------------
inorder function
--------------------------------------------------------------------------
*/
void inorder(node *temp,node *dummy)
{
   while(temp!=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;
  }
 }
/*
--------------------------------------------------------------------------
main function
--------------------------------------------------------------------------
*/
void main()
{
   int choice;
   char ans='N';
   thread th;
   clrscr();
   do
   {

            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');
}