Threaded Binary Tree

Discussion in 'C++' started by aisha.ansari84, Jul 17, 2008.

  1. aisha.ansari84

    aisha.ansari84 New Member

    Joined:
    Feb 13, 2008
    Messages:
    82
    Likes Received:
    1
    Trophy Points:
    0

    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:
    
    //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 .
     
  2. coderzone

    coderzone Super Moderator

    Joined:
    Jul 25, 2004
    Messages:
    736
    Likes Received:
    38
    Trophy Points:
    28
    Well explained code.
     
  3. imrantechi

    imrantechi New Member

    Joined:
    Feb 12, 2008
    Messages:
    116
    Likes Received:
    4
    Trophy Points:
    0
  4. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
  5. skp819

    skp819 New Member

    Joined:
    Dec 8, 2008
    Messages:
    89
    Likes Received:
    3
    Trophy Points:
    0
    that is very good. It is easy to understand.
     
  6. mayjune

    mayjune New Member

    Joined:
    Jun 14, 2009
    Messages:
    814
    Likes Received:
    33
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Pune,Delhi
    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?
     
  7. Saket

    Saket New Member

    Joined:
    Jul 21, 2009
    Messages:
    42
    Likes Received:
    0
    Trophy Points:
    0
    Location:
    Don't Know
    What is threaded binary tree. ?
     
  8. sura

    sura Banned

    Joined:
    Aug 4, 2011
    Messages:
    47
    Likes Received:
    1
    Trophy Points:
    0
    Location:
    India,Tamil Nadu.
    can you tell how the insertion and deletion is done please..................................
     
  9. mukeshsoftona

    mukeshsoftona Banned

    Joined:
    Oct 28, 2011
    Messages:
    47
    Likes Received:
    0
    Trophy Points:
    0
    nice one dear. l love your way.
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice