Code Bye

二叉查找树的删除疑问

书上写到 只有一个儿子的节点在删除时“可以在其父节点调整指针绕过该节点后删除”,这个本人理解,但是后面给的程序不太清楚。
BiSearchTree Delete(ElementType X, BiSearchTree T)
{
Position TmpCell;
if(T==NULL)
{
fprintf(stderr,”Element does not exist!”);
}
else if(X < T->Element)
{
T->Left = Delete(X,T->Left);
}
else if(X > T->Element)
{
T->Right = Delete(X,T->Right);
}
else if(T->Left && T->Right)
{
TmpCell = FindMin(T->Right);
T->Element = TmpCell->Element;
T->Right = Delete(T->Element,T->Right);
}
else          //此处为只有一个儿子的情况
{
TmpCell = T;
if(T->Left == NULL)
{
T = T->Right;
}
else if(T->Right == NULL)
{
T = T->Left;
}
free(TmpCell);
}
return T;
}
1.照前面说的,不应该是找出T的父亲节点F,然后再改变F的儿子指针吗?
(T->Left == NULL)     T = T->Right;
是什么意思?
2.tmpcell=t;
free(tmpcell);
这两句是什么意思?
刚刚开始入门,第一次来这个地方,谢谢大家
解决方案

30

原因是这个是递归调用的,当最后一次调用的时候找到了需要删除的结点后,你应该返回的是替换它的结点的地址
假设它的上一级是T->Right = Delete(T->Element,T->Right);
你的Delete(T->Element,T->Right);  是不是只需要返回替换它的节点的地址,然后这个删除节点的父节点就是上一级的这个T
T->Right = 新的替换节点的地址
PS:表达的不是太好,题主可以在纸上演算一下,或单步调试一步步看结果

5

“给定一个小点的输入,完整单步跟踪(同时按Alt+7键查看Call Stack里面从上到下列出的对应从里层到外层的函数调用历史)一遍。”是理解递归函数工作原理的不二法门!
递归函数关注以下几个因素
·退出条件
·参数有哪些
·返回值是什么
·局部变量有哪些
·全局变量有哪些
·何时输出
·会不会导致堆栈溢出

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明二叉查找树的删除疑问