删除二分搜索树中最下节点的非递归实现

来源：1-13 删除二分搜索树的最大元素和最小元素

飞半天的鱼儿

2020-09-07 10:45:56

/**
* 移除二分搜索树中的最小元素(非递归方式)
*/
public E removeMinNR() {

if (size == 0) {
throw new IllegalArgumentException("BST is empty");
}

Node cur = root;
Node preCur = null;
Node rightNode = null;

while (cur.left != null) {
preCur = cur;
cur = cur.left;
rightNode = cur.right;
}

preCur.left = rightNode;
cur.right = null;

return cur.e;
}

写回答

3回答

慕UI4021841

2020-09-18

只有一个根节点时，你这是有bug的，处理下

慕UI4021841

2020-09-18

// 删除二分搜索树最小值
public E removeMinimum() {

    if (root == null)
        throw new IllegalArgumentException(" BST is empty!");

    if (root.left == null){
        E result = root.e;
        root = root.right;
        return result;
    }

    Node cur = root;
    Node preCur = null;

    while (cur.left != null) {
        preCur = cur;
        cur = cur.left;
    }
    Node right = cur.right;
    preCur.left = right;
    cur.right = null;
    return cur.e;
}


// 删除二分搜索树最大值
public E removeMaxmum() {
    if (root == null)
        throw new IllegalArgumentException(" BST is empty!");

    if (root.right == null){
        E result = root.e;
        root = root.left;
        return result;
    }
    Node cur = root;  
    Node preCur = null; 

    while (cur.right != null) {
        preCur =cur;
        cur = preCur.right;
    }
    Node left = cur.left;
    preCur.right=left;
    cur.left=null;  //gc

    return cur.e;
}