BST删除函数不会删除预期的节点(Java)

Question

我正在尝试为我的BST类实现删除功能。我正在尝试遵循一些标准的教程，除了删除功能外，所有内容都很好。我没有任何错误，但不会删除预期的节点。我要递归地转到预期的节点，如果它只有一个孩子，则返回另一侧节点，否则我将从n.right中返回最小的值。

任何帮助将不胜感激 - 谢谢！

public class BinaryTree {
    private Node root = null;
    private class Node {
        private Node left;
        private Node right;
        private int data;
        public Node(int data, Node left, Node right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }
    public boolean add(int data) {
        root = add(root, data);
        return true;
    }
    private Node add(Node node, int data) {
        if (node == null) {
            node = new Node(data, null, null);
        }
        else {
            if (data < node.data) {
                node.left = add(node.left, data);
            }
            else {
                node.right = add(node.right, data);
            }
        }
        return node;
    }
    // Helper function
    private Node findMin(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
    private Node findMax(Node node) {
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }
    private void inOrderTraversal(Node n) {
        if (n == null) return;
        else {
            inOrderTraversal(n.left);
            System.out.println(n.data);
            inOrderTraversal(n.right);
        }
    }
    public void inOrderTraversal() {
        inOrderTraversal(root);
    }
    private Node deleteKey(Node n, int data) {
        if (n == null) return n;
        if (data < n.data) deleteKey(n.left, data);
        else if (data > n.data) deleteKey(n.right, data);
        else {
            if (n.left == null) return n.right;
            else if (n.right == null) return n.left;
            n.data =  findMin(n.right).data;
            n.right = deleteKey(n.right, n.data);
        }
        return n;
    }
    public void deleteKey(int data) {
        root = deleteKey(root, data);
    }
    public static void main(String[] args) {
        BinaryTree bst = new BinaryTree();
        bst.add(2);
        bst.add(8);
        bst.add(1);
        bst.add(7);
        bst.add(3);
        bst.add(11);
        bst.add(1);
        bst.add(21);
        bst.add(10);
        bst.add(12);
        bst.inOrderTraversal();
        System.out.println("----------------");
        bst.deleteKey(3);
        bst.inOrderTraversal();
    }
}

Answer 1

我认为问题在您的deleteKey函数中：

private Node deleteKey(Node n, int data) {
    if (n == null) return n;
    if (data < n.data)
        n.left = deleteKey(n.left, data); // must reassign child here
    else if (data > n.data)
        n.right = deleteKey(n.right, data); // must reassign child here
    else {
        if (n.left == null) return n.right;
        else if (n.right == null) return n.left;
        n.data = findMin(n.right).data;
        n.right = deleteKey(n.right, n.data); // this was correct
    }
    return n;
}

当data < n.data或data > n.data时，您不会更新当前节点的叶子。因此，这是查找删除适当的节点，但是在从递归中返回的途中，它并没有正确重建节点分支。