Threaded Binary Tree

aisha.ansari84's Avatar author of Threaded Binary Tree
This is an article on Threaded Binary Tree in C++.

Introduction



Here is the code for a threaded binary tree.

The basic difference between a binary tree and the threaded binary tree is that in the binary trees the nodes are null if there is no child associated with it and so there is no way to traverse back.

But in a threaded binary tree we have threads associated with the nodes i.e they either are linked to the predecessor or successor in the inorder traversal of the nodes. This helps us to traverse further or backward in the inorder traversal fashion.

There can be two types of threaded binary tree :-

1) Single Threaded :- i.e nodes are threaded either towards its inorder predecessor or successor.

2) Double threaded:- i.e nodes are threaded towards both the inorder predecessor and successor.

The code below is for double threaded binary tree.

Code: CPP
//Header Files

#include<stdio.h>
#include<conio.h>
#include<windows.h>

//macro

# define INSERT 'i'  ///<used for inserting option.

# define DELETION 'd'      ///<used for deletion option.

# define DISPLAY 'w'        ///<used for display option.

# define EXIT  'e'    ///<used for exit option.

# define FIRST 'f'    ///<used for the smallest element in the tree.

# define LAST 'l'      ///<used for the largest element in the tree.

# define LEFT 0  ///<used to denote the left link.

# define RIGHT 1        ///<used to denote the right link.

struct tbst_node
{
    int uData ;             ///<contains the data stored in the tree.

    unsigned int uTag[2] ;            ///<contains the link to the left and right subtrees.

    struct tbst_node* uLink[2] ;    ///<contains the tags to the left and right subtrees i.e whether child or thread.

} ;

 //here we type def struct bst_node to denote it as treenode for Further reference.

typedef struct tbst_node treenode;

enum tbst_tag
{

    TBST_CHILD,   ///<used to denote that the next link is towards a child node.

    TBST_THREAD   ///<used to denote that the next link is towards a parent node.

};

//Global Variables.

treenode *gRoot=NULL;

/**
 * main () this is used to receive the choice of the user and perform the tree operations as desired by the user.
 *
 */


int main()
{   

        char choice;        ///<contains the choice of the user.

        int data;         ///<contains the data to be inserted into the tree.

        treenode* node;  ///<variable decleration for the tree.

        int type=0;   ///<contains the type of deletion.

    //clears the screen.
    system("cls");   

    while(1){

        printf("\n..............................MENU.....................................");

        printf("\n\t\t what do you want to do\n");

        printf("\n\t\t enter 'i' to insert\n");

        printf("\n\t\t enter 'd' to delete\n");

        printf("\n\t\t enter 'w' to display the tree\n");

        printf("\n\t\t enter 'f' to display least value entered by the user \n");

        printf("\n\t\t enter 'l' to display maximum value entered by the user \n");

        printf("\n\t\t enter 'e' to exit\n");

        printf("\n..............................MENU.....................................\n");

        printf("\n the choice is:      ");

        fflush(stdin);

        scanf("%c",&choice);
       
        switch(tolower(choice)){
       
        case INSERT:

            printf("\n ENTER THE DATA TO BE INSERTED");

            //accepts data to be inserted into the tree.
            scanf("%d",&data);         

            //inserts data into the tree.
            if(Insert(gRoot,data)==TRUE){            

                printf("\n INSERTION SUCCESSFUL");

            }else{

                printf("\n INSERTION UNSUCCESSFUL");

            }

            break;


        case DELETION:

            printf("\n ENTER THE DATA TO BE DELETED");

            //gets the data to be deleted.
            scanf("%d",&data);         


            //searches the data in the tree and stores the parent node in the temp.
            node=Search(gRoot,data);   

            if(node==NULL){

                printf("\n item does not exist,cannot be deleted");

            }else{

                //checks if the data to be deleted is the data of the root.
                if(gRoot->uData==data){

                    type=1;

                }
                //calls the Delete Node function to delete the node.
                DeleteNode(node,data,type)

                printf("\n item deleted");

            }

            break;

        case DISPLAY:

            if(gRoot==NULL){

                printf("\n EMPTY TREE ");

            }else{

                printf("\n THE TREE ELEMENTS ARE");

                //calls the walk function to display the tree data in in order traversal.
                Walk(gRoot);   

            }

            break;

        case FIRST:

            //if there are no elements in the tree
            if(gRoot==NULL){

                printf("\n the TREE is EMPTY");

            //gets the smallest element in the tree.
            }else{

                printf("\n the smallest value is ");

                node=FindSmallestNode(gRoot);

                printf("%d",node->uData);

            }
           
            break;

        case LAST:

            //if there are no elements in the tree
            if(gRoot==NULL){

                printf("\n the TREE is EMPTY");

            //gets the largest element in the tree.
            }else{

                printf("\n the largest value is ");

                node=FindLargestNode(gRoot);

                printf("%d",node->uData);

            }
           

            break;

        case EXIT:

            //frees the whole tree.
            Free(gRoot);

            return 0;

            break;
           
        default:

            printf("\n INVALID CHOICE ,RETRY \n");
           
        }
   
    }

    _getch();

}

/**
 * Walk(treenode* pNode) is used to traverse the nodes of the tree in inorder traversal.
 *
 * @param [in]  pNode contains the node of the tree through which traversal is to be done.
 *
 */



void Walk(treenode *pNode)
{

    //prints the data of the tree only if it is not empty.
    if(pNode!=NULL){   

        if(pNode->uTag[LEFT]==TBST_CHILD){
           
            //calls the walk function recursively to get the left node.
            Walk(pNode->uLink[LEFT]);

        }

        //prints the data of the node.
        printf("\n %d",pNode->uData);   

        if(pNode->uTag[RIGHT]==TBST_CHILD){

            //calls the walk function recursively to get the right node.
            Walk(pNode->uLink[RIGHT])

        }

    }

}

/**
 * Insert(int pIteme) is used to insert a new node to the tree.
 *
 * @param [in]  pItem contains the data to be inserted to the tree.
 *
 * @return    BOOL  returns FALSE if insertion fails,else TRUE.
 *
 */


BOOL Insert(treenode *pNode,int pItem)
{
        treenode* ptr;      ///<variable for the tree.

    //allocates memory for ptr.
    ptr=(treenode*)calloc(1,sizeof(treenode));

    //assignes pItem to the data field of ptr.
    ptr->uData=pItem;

    //assigns both the tags as threads.
    ptr->uTag[LEFT]=ptr->uTag[RIGHT]=TBST_THREAD;

    if(gRoot==NULL){

        //assigns ptr to gRoot if the tree is empty.
        gRoot=ptr;

        //sets the right link of root to null.
        ptr->uLink[RIGHT]=NULL

        return TRUE;

    //if the data to be entered is already present in the tree.
    }else if(pItem==pNode->uData){

        return FALSE;

    //if the data to be entered is greater than the data field of the present node
    }else if(pItem>pNode->uData){

        //if the present nodes right tag is a child then insert function is called again with the present nodes right link .
        if(pNode->uTag[RIGHT]==TBST_CHILD){

            Insert(pNode->uLink[RIGHT],pItem);

        //if the present nodes right tag is a thread, then node is inserted in the right of the present node.
        }else{

            ptr->uLink[RIGHT]=pNode->uLink[RIGHT];

            pNode->uLink[RIGHT]=ptr;

            ptr->uLink[LEFT]=pNode;

            pNode->uTag[RIGHT]=TBST_CHILD;

            return TRUE;

        }

    //if the data to be entered is greater than the data field of the present node
    }else if(pItem<pNode->uData){

        //if the present nodes right tag is a child then insert function is called again with the present nodes left link .
        if(pNode->uTag[LEFT]==TBST_CHILD){

            Insert(pNode->uLink[LEFT],pItem);

        //if the present nodes right tag is a thread, then node is inserted in the left of the present node.
        }else{

            ptr->uLink[LEFT]=pNode->uLink[LEFT];

            pNode->uLink[LEFT]=ptr;

            ptr->uLink[RIGHT]=pNode;

            pNode->uTag[LEFT]=TBST_CHILD;

            return TRUE;

        }
    }   
}


/**
 * DeleteNode(treenode * pNode,int pItem) is used to delete a particular node from the tree.
 *
 * @param [in]  pNode contains the parent node of the node to be deleted.
 *
 * @param [in]  pItem contains the data to be deleted in the tree.
 *
 * @param [in]  pType tells whether the pNode is the root node i.e if pType=1 or the parent of the node to be deleted i.e if pType=0
 *
 */


void DeleteNode(treenode * pNode,int pItem,BOOL pType)
{

        int i=0;                ///<variable declaration.

        treenode *temp;   ///<variable for the tree.

       
    //checks if the item to be searched is greater than the pNode nodes data.
    if(pItem>pNode->uData && pType==0){ 
   
        i=RIGHT;

    }

    if(pType==0){

        //assigns the node to be deleted.
        temp=pNode->uLink[i];   

    }else{

        //assigns the node to be deleted.
        temp=pNode; 

    }

    //this condition is true if the node to be deleted has no child
    if((temp->uTag[LEFT]== TBST_THREAD ||temp->uLink[LEFT]==NULL)&& (temp->uTag[RIGHT]== TBST_THREAD||temp->uLink[RIGHT]==NULL)){

        SettingDeleteNodeWithNoChild(pType,pNode,i);

    //this condition is true if the node to be deleted has right child
    }else if((temp->uLink[LEFT]== NULL||temp->uTag[LEFT]==TBST_THREAD) && temp->uTag[RIGHT]==TBST_CHILD){
   
        SettingDeleteNodeWithRightChild(pType,pNode,i);

    //this condition is true if the node to be deleted has left child
    }else if(temp->uTag[LEFT]==TBST_CHILD && (temp->uLink[RIGHT]==NULL || temp->uTag[RIGHT]==TBST_THREAD)){
   
        SettingDeleteNodeWithLeftChild(pType,pNode,i);

    //this condition is true if the node to be deleted has both childs
    }else if(temp->uTag[LEFT]==TBST_CHILD && temp->uTag[RIGHT]==TBST_CHILD){   

        SettingDeleteNodeWithBothChild(pType,pNode,i);

    }

    //frees the memory allocated for temp.
    free(temp);  

    printf("\n node deleted");

 }

/**
 * SettingDeleteNodeWithNoChild(int pType,treenode* pNode,int pDir) is used to set the nodes after deleting the node with no child.
 *
 * @param [in]  pNode contains the parent node of the node to be deleted or the root node if it is to be deleted.
 *
 * @param [in]  pDir  contains the direction from the parent node to thechild node.
 *
 * @param [in]  pType tells whether the pNode is the root node i.e if pType=1 or the parent of the node to be deleted i.e if pType=0
 *
 */


void SettingDeleteNodeWithNoChild(int pType,treenode* pNode,int pDir)
{
    //if the node to be deleted has no childs we simply assign NULL to it.
    if(pType==0){

        pNode->uTag[pDir]=pNode->uLink[pDir]->uTag[pDir];
        pNode->uLink[pDir]=pNode->uLink[pDir]->uLink[pDir];

    }else{

        //if the node to be deleted has no childs and it is the root node we simply assign NULL to root node.
        gRoot=NULL;

    }

}

/**
 * SettingDeleteNodeWithRightChild(int pType,treenode* pNode,int pDir) is used to set the nodes after deleting the node with right child.
 *
 * @param [in]  pNode contains the parent node of the node to be deleted or the root node if it is to be deleted.
 *
 * @param [in]  pDir  contains the direction from the parent node to thechild node.
 *
 * @param [in]  pType tells whether the pNode is the root node i.e if pType=1 or the parent of the node to be deleted i.e if pType=0
 *
 */


void SettingDeleteNodeWithRightChild(int pType,treenode* pNode,int pDir)
{

    //if the node to be deleted has only right child we simply assign its right child to it's parent.
    if(pType==0){

        pNode->uLink[pDir]->uLink[RIGHT]->uLink[pDir]=pNode->uLink[pDir]->uLink[pDir];
       
        pNode->uLink[pDir]=pNode->uLink[pDir]->uLink[RIGHT];

       

    }else{

        //if the node to be deleted has only right child and it is the root node we simply assign its right child to root node.
        gRoot=pNode->uLink[RIGHT];
        gRoot->uLink[LEFT]=NULL;

    }

}

/**
 * SettingDeleteNodeWithLeftChild(int pType,treenode* pNode,int pDir) is used to set the nodes after deleting the node with left child.
 *
 * @param [in]  pNode contains the parent node of the node to be deleted or the root node if it is to be deleted.
 *
 * @param [in]  pDir  contains the direction from the parent node to thechild node.
 *
 * @param [in]  pType tells whether the pNode is the root node i.e if pType=1 or the parent of the node to be deleted i.e if pType=0
 *
 */


void SettingDeleteNodeWithLeftChild(int pType,treenode* pNode,int pDir)
{

    //if the node to be deleted has only left child we simply assign its left child to it's parent.
    if(pType==0){

        pNode->uLink[pDir]->uLink[LEFT]->uLink[pDir]=pNode->uLink[pDir]->uLink[pDir];
        pNode->uLink[pDir]=pNode->uLink[pDir]->uLink[LEFT];

    }else{

        //if the node to be deleted has only left child and it is the root node we simply assign its left child to root node.
        gRoot=pNode->uLink[LEFT];
        gRoot->uLink[RIGHT]=NULL;

    }

}

/**
 * SettingDeleteNodeWithBothChild(int pType,treenode* pNode,int pDir) is used to set the nodes after deleting the node with both child.
 *
 * @param [in]  pNode contains the parent node of the node to be deleted or the root node if it is to be deleted.
 *
 * @param [in]  pDir  contains the direction from the parent node to thechild node.
 *
 * @param [in]  pType tells whether the pNode is the root node i.e if pType=1 or the parent of the node to be deleted i.e if pType=0
 *
 */


void SettingDeleteNodeWithBothChild(int pType,treenode* pNode,int pDir)
{
       
        treenode *temporary;    ///<variable for the tree.

        treenode *node;   ///<variable for the tree.

        treenode* temp;   ///<variable for the tree.

   
    if(pType==0){
       
        temp=pNode->uLink[pDir]

    }else{

        temp=pNode; 

    }

    //we assign the node to be deleted's right link to temporary.
    temporary=temp->uLink[RIGHT];

    //we find the next smallest number in the tree after the node to be deleted.
    if(temporary->uLink[LEFT]!= NULL && temporary->uTag[LEFT]==TBST_CHILD ){   

        while(temporary->uTag[LEFT]==TBST_CHILD && temporary->uLink[LEFT]!= NULL){

            node=temporary;

            temporary=temporary->uLink[LEFT];         

        }

        //assigns temporary to the parent of the node to be deleted.
        if(pType==0){

            pNode->uLink[pDir]=temporary;

        }else{

            gRoot=temporary;

        }

        //assigns the left link of the node to be deleted to the temporary's left.
        temporary->uLink[LEFT]=temp->uLink[LEFT];   

        temporary->uTag[LEFT]=temp->uTag[LEFT];

        temporary->uTag[RIGHT]=temp->uTag[RIGHT];

        //assigns the right link of the node to be deleted to the temporary's right.
        temporary->uLink[RIGHT]=temp->uLink[RIGHT];

        node->uTag[LEFT]=TBST_THREAD;

    }else{

        //assigns temporary to the parent of the node to be deleted.
        if(pType==0){

            pNode->uLink[pDir]=temporary;

        }else{

            gRoot=temporary;

        }


        //assigns the left link of the node to be deleted to the temporary's left.
        temporary->uLink[LEFT]=temp->uLink[LEFT];
   
        temporary->uTag[LEFT]=temp->uTag[LEFT];


    }   

}
 
/**
 * FindLargestNode(treenode* pNode) is used to find the largest node of the tree.
 *
 * @param [in]  pNode contains the node to be checked as the largest node.
 *
 * @return treenode  returns the largest node of the tree.
 *
 */


treenode* FindLargestNode(treenode* pNode)
{

    //if the node is the right most node of the tree, then returns the node as the largest node.
    if((pNode->uTag[RIGHT]==TBST_THREAD)||pNode->uLink[RIGHT]==NULL){

        return pNode;

    }

    FindLargestNode(pNode->uLink[RIGHT]);

}

/**
 * FindSmallestNode(treenode* pNode) is used to find the smallest node of the tree.
 *
 * @param [in]  pNode contains the node to be checked as the smallest node.
 *
 * @return treenode  returns the smallest node of the tree.
 *
 */


treenode* FindSmallestNode(treenode* pNode)
{

    //if the node is the left most node of the tree, then returns the node as the smallest node.
    if((pNode->uTag[LEFT]==TBST_THREAD)||pNode->uLink[LEFT]==NULL){

        return pNode;

    }

    FindSmallestNode(pNode->uLink[LEFT]);
   
}

/**
 * Free(treenode* pNode) is used to free the memory allocated for the tree.
 *
 * @param [in]  pNode contains the node to be freed.
 *
 */


void Free(treenode* pNode)
{
    //frees the data of the tree only if it is not empty.
    if(pNode!=NULL){       

        if(pNode->uTag[LEFT]==TBST_CHILD){

            //calls the free function recursively to get the left node.
            Free(pNode->uLink[LEFT]);   

        }

        if(pNode->uTag[RIGHT]==TBST_CHILD){

            //calls the free function recursively to get the right node.
            Free(pNode->uLink[RIGHT])

        }

        //frees the data of the node.
        free(pNode);       

    }

}
/**
 * Search(treenode* pNode,int pItem) is used to search a value in the tree.
 *
 * @param [in]  pNode contains the node of the tree through which searching is to be done.
 *
 * @param [in]  pItem contains the data to be searched in the tree.
 *
 * @return    treenode  returns the parent node of the node which contains the data,
 *              if the search node is the root node tehn returns the search node,else NULL.
 *
 */



treenode* Search(treenode* pNode,int pItem)
{
    //checks if the node to be searched is the root node itself.
    if(gRoot->uData==pItem){
   
        return pNode;

    }
    //checks if the item to be searched is greater than the current nodes data.
    if(pItem>pNode->uData ){       

        //checks if the item is same as the current node's right links data.
        if(pItem==pNode->uLink[RIGHT]->uData ){ 

            return pNode;   //returns the current node.
           
        }else if(pNode->uTag[RIGHT]!=TBST_THREAD ){

            //calls the search function with the current nodes right node.
            Search(pNode->uLink[RIGHT],pItem)

        }else{

        //returns NULL.
        return NULL;   

        }

    //checks if the item to be searched is less than the current nodes data.
    }else if(pItem<pNode->uData){

        //checks if the item is same as the current node's left links data.
        if( pItem==pNode->uLink[LEFT]->uData){

            //returns the current node.
            return pNode;   

        }else if(pNode->uTag[LEFT]!=TBST_THREAD ){

            //calls the search function with the current nodes left node.
            Search(pNode->uLink[LEFT],pItem);
   
        }else{

        //returns NULL.
        return NULL;   

        }

    }

}


I think the code is very much self explanatory but if any problems , you can feel free to ask me .
coderzone's Avatar, Join Date: Jul 2004
Team Leader
Well explained code.
imrantechi's Avatar, Join Date: Feb 2008
Ambitious contributor
nice one
skp819's Avatar
Contributor
that is very good. It is easy to understand.
mayjune's Avatar, Join Date: Jun 2009
Invasive contributor
isn't this a double threaded binary "search" tree...
as what we have been taught a threaded tree can have insertion at any point,
need not be smallest on left and largest on right sub tree
and hence its a special case of a threaded tree.
correct me if i am wrong?
Saket's Avatar
Banned
What is threaded binary tree. ?
sura's Avatar
Banned
can you tell how the insertion and deletion is done please..................................
mukeshsoftona's Avatar
Banned
nice one dear. l love your way.