对于BST删除算法中递归的疑问
来源:6-12 删除二分搜索树的任意元素
程序员不会说方言
2019-08-18
老师您好!
①在BST删除元素的那个算法中,我不是很清楚老师写的那个算法中的递归终止条件是什么(没有像平时那样很清楚的写出来,也许是我太菜 -.-)
②在①的基础上我仔细思考想像之前那样明显的表现出递归终止条件,并结合BST添加算法中递归条件的简化那个想法,写出了以下程序,总体思想是根据:左右两边是空时这两种情况是Hibbard Deletion的特例。代码如下不知是否正确(测试了感觉因该没问题)
public void remove(E e){
root = remove(root, e);
}
private Node remove(Node node, E e){
//递归终止条件部分
if( node == null )
return null;
if( e.compareTo(node.e) == 0 ) {
//根据空也是一棵树,我们把待删除结点的后继分成空和非空两种情况考虑
if(node.right == null) {
return removeMin(node);
} else {
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
}
//递归部分
if( e.compareTo(node.e) < 0 ){
node.left = remove(node.left,e);
return node;
} else {
node.right = remove(node.right, e);
return node;
}
}
写回答
1回答
-
245行,246行,就是递归的终止条件,即当node为空时,返回空。
整个remove(Node node, E e)的语义是,在以node为根节点的二分搜索树中删除元素e,并且返回删除后的二分搜索树的根节点。当node为空时,肯定不包含元素e,直接返回空就好了。
======
你的代码整体思路没有问题,但是有一个小bug。在node.right == null的时候,应该删除removeMax(node)。因为此时要删除的节点是node,node->right是空,说明node是当前这棵树的最大元素,node的左子树中的所有元素,肯定比node小,所以要删除max,而不是min:)
继续加油!:)
112019-08-19
相似问题
为什么我思考的递归总和老师的不一样...
回答 1
关于递归算法的提问?
回答 1