数据结构:关于二叉查找树(BinarySearchTree)的删除算法的疑问?

Mark Allen Weiss的《数据结构与算法分析》第4章中讲到二叉查找树这种数据结构,关于删除的代码是这样的:

  
// 删除以t为根的BST中值为x的节点
void remove(int x, BinaryNode*& t)
{
if ( t == NULL)
{
return ;
}
if (x < t->data)
{
remove(x, t->left);
}
else if (x > t->data)
{
remove(x, t->right);
}
// 左右都有节点的情况
else if (t->left != NULL && t->right != NULL)
{
t->data = findMin(t->right)->data; // 右子树最小的节点
remove(t->data, t->right);
}
else
{
BinaryNode* oldNode = t;
t = (t->left != NULL) ? t->left : t->right);
delete oldNode;
}
}

二叉树的基本性质是节点大于其左子树的所有节点,小于其右子树的所有节点,
在这个删除算法中,当删除的节点有2个儿子的情况的时候,为什么是从右子树找出最小的节点而不是从左子树找出最大的节点呢?

评论 (0)链接2014-04-20 

http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9#.E5.9C.A8.E4.BA.8C.E5.8F.89.E6.9F.A5.E6.89.BE.E6.A0.91.E5.88.A0.E9.99.A4.E7.BB.93.E7.82.B9.E7.9A.84.E7.AE.97.E6.B3.95

若*p结点的左子树和右子树均不空。在删去*p之后,为保持其它元素之间的相对位置不变,可按中序遍历保持有序进行调整,可以有两种做法:其一是...;其二是令*p的直接前驱(in-order predecessor)或直接后继(in-order successor)替代*p,然后再从二叉查找树中删去它的直接前驱(或直接后继)。

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2014-04-21
德问是一个专业的编程问答社区,请 登录注册 后再提交答案