老师，请问bst循环删除任意元素如何实现？

循环中如何找到待删除的元素，是根据根节点的值去比较要删除的值是否相等吗？

学无止境呀呀呀 2020-11-25

源自：二分搜索树 2-1 集合基础和基于二分搜索树的集合实现

收起

1回答

liuyubobobo 2020-11-25 20:35:05

对的呀。我们的递归算法也是根据节点的值去比较，和要删除的值相等呀：）

继续加油！：）

收起回答

提问者学无止境呀呀呀 #1

那是不是可以理解为当while(root.date.compareTo(e)!=0)时去找待删除节点吗？＝0就是找到了，然后去判断左右子树存不存在的情况进行删除？

2020-11-25 21:12:35
liuyubobobo 回复提问者学无止境呀呀呀 #2

是的。其实和链表一样。只不过当 node.date.compareTo(e)!=0 的时候，要根据是 > 0 还是 <0，去选择下一个要找的节点是左节点还是右节点而已：）

2020-11-26 04:11:06

提问者学无止境呀呀呀回复 liuyubobobo #3

public void remove(E e){
    if (root.size==0)return;
    Node curNode=root;
    Node n=null;
    while (curNode.data.compareTo(e)!=0){
        n=curNode;
        if (curNode.data.compareTo(e)<0) {
            curNode=curNode.right;
        }else if (curNode.data.compareTo(e)>0){
            curNode=curNode.left;
        }
    }
    if (null==curNode.right) {
        Node leftNode=curNode.left;
        curNode.size--;
        n.left=leftNode;
    }else if (null==curNode.left){
        Node rightNode=curNode.right;
        curNode.size--;
        n.right=rightNode;
    }else{
        Node successor=minimun(curNode);
        successor.right=removeMin(curNode.right);
        successor.left=curNode.left;
        curNode.left=curNode.right=null;
        curNode=successor;
        root=curNode;
    }