删除最小非递归,老师您看看我这个对吗?
来源:5-7 删除最大值,最小值

慕虎6513783
2020-10-18
public void delMin(){
//当前树为空
if(this.root == null) return;
//当前树只有一个节点
if(this.size == 1) {
this.root = null;
this.size--;
return;
}
Node pre = this.root;
Node cur = pre.lChild;
//根节点的左孩子为空,最小就是根节点
if(cur == null) {
this.root = pre.rChild;
this.size--;
return;
}
//处理其他情况,根节点的左右孩子都存在
while(cur.lChild!=null){
pre = pre.lChild;
cur = cur.lChild;
}
//循环结束,cur为最小的结点,pre为最小结点的父节点
Node rightChild = cur.rChild;
if(rightChild == null){
pre.lChild = null;
}else{
pre.lChild = rightChild;
}
this.size--;
}
写回答
2回答
-
liuyubobobo
2020-10-18
你的思路是正确的。最小值就是都在左子树呀。这是 BST 的性质,左子树的所有值一定小于右子树,所以最小值就是在不断往左走,知道不能继续走的位置:)
继续加油!:)
00 -
慕虎6513783
提问者
2020-10-18
我感觉我有问题,我错误的以为最小的都在左子树
00
相似问题