How to delate a node from the threaded binary tree?

Question

Please share the code or algorithm to delete a node from Threaded Binary Tree.

Answer 1

This should help

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.
} ;

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;

/**
 * @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;
    treenode *temp;

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

    free(temp);  
 }

/**
 * This func 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(pType==0){
        pNode->uTag[pDir]=pNode->uLink[pDir]->uTag[pDir];
        pNode->uLink[pDir]=pNode->uLink[pDir]->uLink[pDir];
    }else{
        gRoot=NULL;
    }
}

/**
 * This func 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(pType==0){
        pNode->uLink[pDir]->uLink[RIGHT]->uLink[pDir]=pNode->uLink[pDir]->uLink[pDir];
        pNode->uLink[pDir]=pNode->uLink[pDir]->uLink[RIGHT];
    }else{
        gRoot=pNode->uLink[RIGHT];
        gRoot->uLink[LEFT]=NULL;
    }
}

/**
 * This func 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(pType==0){
        pNode->uLink[pDir]->uLink[LEFT]->uLink[pDir]=pNode->uLink[pDir]->uLink[pDir];
        pNode->uLink[pDir]=pNode->uLink[pDir]->uLink[LEFT];
    }else{
        gRoot=pNode->uLink[LEFT];
        gRoot->uLink[RIGHT]=NULL;
    }
}

/**
 * This func 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;
    treenode *node;
    treenode* temp;

    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];
    }   
}

/**
 * @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((pNode->uTag[RIGHT]==TBST_THREAD)||pNode->uLink[RIGHT]==NULL){
        return pNode;
    }
    FindLargestNode(pNode->uLink[RIGHT]);
}

/**
 * @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((pNode->uTag[LEFT]==TBST_THREAD)||pNode->uLink[LEFT]==NULL){
        return pNode;
    }

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