删除最小非递归,老师您看看我这个对吗?

来源: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 的性质,左子树的所有值一定小于右子树,所以最小值就是在不断往左走,知道不能继续走的位置:)


继续加油!:)

0
0

慕虎6513783

提问者

2020-10-18

我感觉我有问题,我错误的以为最小的都在左子树

0
0

算法与数据结构(C++版) 面试/评级的算法复习技能包

课程专为:短时间内应对面试、升职测评等艰巨任务打造

11210 学习 · 1617 问题

查看课程