c - 二叉平衡树的指针问题

问题描述

问 题

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

如图，如果我想要删除14结点

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

当我找到14结点时， T=T->LeftChild; T变为它的左儿子13，TmpCell仍然是14结点，然后我free了TmpCell，就等于释放了14结点，14结点的父节点并没有链接13结点，但是为什么遍历时13结点也能输出。虽然这么写满足了需求，但是这里不太懂，希望解答下，谢谢。

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

还有这句代码的效率比较低，请问怎么改正。

解决方案

当你删除节点14后，程序返回，程序并没有结束，程序返回到这里

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

此时，T 指向节点10 ，Delete函数返回指向13的指针

关于效率问题
可以用循环代替递归，寻找目标节点

这篇关于c - 二叉平衡树的指针问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！