在bst中删除带有两个子节点的节点

xbp102n0  于 2021-06-30  发布在  Java
关注(0)|答案(0)|浏览(170)

我正在尝试实现二叉搜索树的remove方法,但是当移除的节点同时有两个子节点时,我无法正确地移除和替换节点。我认为问题可能出在我用删除节点替换节点的代码中,或者我的顺序继承代码可能是错误的。我已经分析了很多,但没有运气,所以我需要帮助纠正我的错误。删除节点后尝试打印树时,会弹出错误。
我现在只在删除节点的时候使用顺序继承者,我想知道什么时候我也应该使用顺序继承者。 BinarySearchTree.java: ```
public class BinarySearchTree<V extends Comparable> {

public class Node<V extends Comparable<V>> {
    V value;
    Node<V> parent, left, right;

    public Node(V value, Node<V> parent, Node<V> left, Node<V> right) {
        this.value = value;
        this.parent = parent;
        this.left = left;
        this.right = right;
    }
}

private Node<V> root = null;

public BinarySearchTree() { this.root = null; }

public int height() { return this.height(this.root); }

private int height(Node<V> at) {
    if (at != null) return 1 + Math.max(this.height(at.left), this.height(at.right));
    return 0;
}

/*
--------------------------------------------------
------------------------ FIND --------------------
--------------------------------------------------
*/

public Node<V> getNode(V value) { return this.getNode(this.root, value); }

private Node<V> getNode(Node<V> at, V value) {
    while (at != null) {
        int c = value.compareTo(at.value);
        if (c < 0) at = at.left;
        else if (c > 0) at = at.right;
        else return at;
    }
    return at;
}

private Node<V> minNode(Node<V> at) {
    while (at != null) {
        if (at.left == null) break;
        at = at.left;
    }
    return at;
}

private Node<V> maxNode(Node<V> at) {
    while (at != null) {
        if (at.right == null) break;
        at = at.right;
    }
    return at;
}

private Node<V> getInorderSuccessor(Node<V> at) { return this.minNode(at.right); }
private Node<V> getInorderPredecessor(Node<V> at) { return this.maxNode(at.left); }

/*
--------------------------------------------------
---------------------- INSERT --------------------
--------------------------------------------------
*/

public void insert(V value) { this.insert(this.root, new Node<V>(value,null,null,null)); }

private void insert(Node<V> at, Node<V> i) {
    int c;
    Node<V> p = null;

    while (at != null) {
        p = at;
        c = i.value.compareTo(at.value);
        at = (c < 0) ? at.left : at.right;
    }

    if (p == null) this.root = i;
    else {
        c = i.value.compareTo(p.value);
        if (c < 0) p.left = i;
        else p.right = i;
    }
    i.parent = p;
}

/*
--------------------------------------------------
---------------------- REMOVE --------------------
--------------------------------------------------
*/

public void remove(V value) {
    if (this.height(this.root) <= 1) this.root = null;
    else {
        Node<V> r = getNode(value);
        if (r != null) this.remove(r);
    }
}

private void remove(Node<V> r) {
    int c = r.value.compareTo(r.parent.value);

    if (r.left == null && r.right == null) {
        if (c < 0) r.parent.left = null;
        else r.parent.right = null;
    } else if (r.left != null && r.right == null) {
        r.left.parent = r.parent;
        if (c < 0) r.parent.left = r.left;
        else r.parent.right = r.left;
    } else if (r.left == null && r.right != null) {
        r.right.parent = r.parent;
        if (c < 0) r.parent.left = r.right;
        else r.parent.right = r.right;
    } else if (r.left != null && r.right != null) {
        Node<V> s = this.getInorderSuccessor(r);
        if (s.right != null) {
            s.parent.left = s.right;
            s.right.parent = s.parent;
        }
        s.parent = r.parent;
        c = s.value.compareTo(s.parent.value);
        if (c < 0) s.parent.left = s;
        else s.parent.right = s;

        s.left = r.left;
        s.left.parent = s;

        s.right = r.right;
        s.right.parent = s;
    }
    r.parent = r.left = r.right = null;
    r = null;

    this.print();
}

/*
--------------------------------------------------
---------------------- PRINT ---------------------
--------------------------------------------------
*/

public void print() { if (this.root != null) this.print(this.root, 0); }

private void print(Node<V> at, int s) {
    if (at == null) return;

    s += 5;

    this.print(at.right, s);

    System.out.print("\n");

    for (int i=5; i<s; i++) System.out.print(" ");

    System.out.print(at.value + "\n");

    this.print(at.left, s);
}

public String nlr() { return this.nlr(this.root); }

private String nlr(Node<V> at) {
    if (at != null) {
        String result = at.value.toString(),
               leftResult = nlr(at.left),
               rightResult = nlr(at.right);

        if (!leftResult.equals("")) result += " " + leftResult;
        if (!rightResult.equals("")) result += " " + rightResult;
        return result;
    }
    return "";
}

public static void main(String[] args) {
    BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
    tree.insert(7);
    tree.insert(3);
    tree.insert(1);
    tree.insert(5);
    tree.insert(4);
    tree.insert(11);
    tree.insert(10);
    tree.insert(15);
    System.out.println("BST construction:");
    System.out.println("Your Pre-order result is: " + tree.nlr());
    System.out.println("    The answer should be: 7 3 1 5 4 11 10 15 \n");
    System.out.println("\nBST print:");
    tree.print();

    System.out.println("\nRemove items: ");
    tree.remove(11);
    System.out.println("Your Pre-order result is: " + tree.nlr());
    System.out.println("    The answer should be: 7 3 1 15 \n");
}

}

暂无答案!

目前还没有任何答案,快来回答吧!

相关问题