CODEWITHSUNDEEP
cdata-structuresbinary-search-tree
ZIHAO LIU
ZIHAO LIU

Reputation: 387

point error in BST's delete function

Delete(key, T){
    BstTree TmpCell; //one tree node
    if(T == NULL)
        return Not Found;
    else if(key < T->data)
        T->LeftChild = Delete(key, T->LeftChild);
    else if(key > T->data)
        T->RightChild = Delete(key, T->RightChild);
    else if(T->LeftChild&& T->RightChild){
        TmpCell = Findmin(T->RightChild);
        T->data = TmpCell->data;
        T->RightChild = Delete(T->data, T->RightChild);
    }
    else{
        TmpCell = T;
        if(T->LeftChild = NULL) T= T->RightChild; 
        if(T->RightChild = NULL) T=T->LeftChild;
        free(TmpCell); 
    }
    return T; 
}

BSTTREE

I found the code in 《data structures and algorithm analysis in C》.

If I want to delete 14

 else{
        TmpCell = T;
        if(T->LeftChild = NULL) T = T->RightChild; 
        if(T->RightChild = NULL) T =T->LeftChild;
        free(TmpCell); 
     }

After I find 14, T (14) moves to T's LeftChild (13), but TmpCell is still pointing to 14, and then I free it. But when I output the Tree, it outputs 13, so how did 13 get connected to 14's parent?

Upvotes: 0

Views: 24

Answers (1)

melpomene
melpomene

Reputation: 85767

The "connecting" part happens when Delete's return value is assigned to something, i.e. in the lines

        T->LeftChild = Delete(key, T->LeftChild);

and

        T->RightChild = Delete(key, T->RightChild);

in the function itself, and at its caller:

myTree = Delete(x, myTree);

(that's how you're supposed to call it).

Upvotes: 1

Related Questions