从 BST 中删除节点

Question

除了情况 2（删除节点只有一个子树）之外，我认为大多数情况都能正常工作。我的测试用例是下面没有 1、2、3 和 4 节点的树：

这个程序告诉我 6 已从树中删除，但是当我尝试打印树时，它仍然显示树中有 6。

public class RandomNode {

static int size;

public static class Node {

    int data;
    Node left;
    Node right;

    public Node(int data) {

        this.data = data;
        left = null;
        right = null;
        size++;
    }

}

// delete node in right subtree
public Node delete(Node root, int data) {
    // base case - if tree is empty
    if (root == null)
        return root;

    // search for deletion node 
    else if (data < root.data)
        root.left = delete(root.left, data);
    else if (data > root.data) {
        root.right = delete(root.right, data);

    } else {

        // case 1: deletion node has no subtrees
        if (root.left == null && root.right == null) {
            root = null;
            size--;
            System.out.println(data + " successfully deleted from tree (case1)");

            // case 2: deletion node has only one subtree
        } else if (root.left != null && root.right == null) {
            root = root.left;
            size--;
            System.out.println(data + " successfully deleted from tree (case2a)");
        } else if (root.left == null && root.right != null) {
            root = root.left;
            size--;
            System.out.println(data + " successfully deleted from tree (case2b)");

            // case 3: deletion node has two subtrees
            // *find min value in right subtree
            // *replace deletion node with min value
            // *remove the min value from right subtree or else there'll be
            // a duplicate
        } else if (root.left != null && root.right != null) {

            Node temp;
            if (root.right.right == null && root.right.left == null)
                temp = findMinNode(root.left);
            else
                temp = findMinNode(root.right);

            System.out.println(root.data + " replaced with " + temp.data);
            root.data = temp.data;

            if (root.right.right == null || root.left.left == null)
                root.left = delete(root.left, root.data);
            else
                root.right = delete(root.right, root.data);

            size--;
            System.out.println(temp.data + " succesfuly deleted from tree (case3)");

        }
    }

    return root;

}

// find min value in tree
public Node findMinNode(Node root) {

    while (root.left != null)
        root = root.left;
    System.out.println("min value: " + root.data);
    return root;

}

public void preOrderTraversal(Node root) {

    if (root == null)
        return;

    preOrderTraversal(root.left);
    System.out.println(root.data);
    preOrderTraversal(root.right);

}

public static void main(String[] args) {

    RandomNode r = new RandomNode();

    Node root = new Node(6);
    //root.left = new Node(2);
    root.right = new Node(9);
    //root.left.left = new Node(1);
    //root.left.right = new Node(5);
    //root.left.right.left = new Node(4);
    //root.left.right.left.left = new Node(3);
    root.right.left = new Node(8);
    root.right.right = new Node(13);
    root.right.left.left = new Node(7);
    root.right.right.left = new Node(11);
    root.right.right.right = new Node(18);

    r.delete(root, 6);
    r.preOrderTraversal(root);

}

}

Answer 1

当你做 root = root.left;和大小 --，您还必须使 root.left = null.

在这里，您只是将 root 设置为 root.left，而不是将 root.left 设置为 null。

Answer 2

我很难理解，因为我是按功能编写的。
然而，

if (root.right.right == null || root.left.left == null)
    root.left = delete(root.left, root.data);
else
    root.right = delete(root.right, root.data);

可能是错误的，因为它应该反映您之前的 findMinNode() 调用，因此可能应该是

if(root.right.right == null && root.right.left == null)
    root.left = delete(root.left, root.data);

调试的时候错误较多

首先，java 是按值传递的，因此如果您要删除顶级节点（根），您的指针也应该更新。因此，调用应该是 root = r.delete(root, 6);

其次，还有一个bug。情况 2a 将 root 分配给 root.left... 为 null。应该是 root.right.

进行这些更改后，输出将变为：

6 successfully deleted from tree (case2b)
7
8
9
11
13
18

从 BST 中删除节点

Deleting Node from BST

java

binary-search-tree