为什么我的Java Binary Search Tree类没有实际删除节点，而我告诉它这样做？

Question

我正在用Java构建一个二进制搜索树，以便更好地理解它们是如何工作的，并且我正在使用这个函数来删除具有特定值的节点。

我基本上遍历树，直到找到具有正确值的节点，然后根据它有多少子节点执行相应的操作。

如果它没有子元素，我将其设置为null。如果它有一个，我会将它自己设置为等于这个孩子。如果它有两个，我遍历左边的树，沿着左边直到我到达左边，然后删除它，并将我所在的节点的值设置为删除的节点的值。

class BTree {
    public int data;
    public BTree leftTree;
    public BTree rightTree;

    public BTree(int data) {
        this.data = data;
    }

    public BTree(int data, BTree leftTree, BTree rightTree) {
        this.data = data;
        this.leftTree = leftTree;
        this.rightTree = rightTree;
    }

    public void insert(int data) {
        if (data < this.data) {
            if (this.leftTree == null) {
                BTree newTree = new BTree(data);
                this.leftTree = newTree;
            } else {
                insert(this.leftTree, data);
            }
        } else {
            if (this.rightTree == null) {
                BTree newTree = new BTree(data);
                this.rightTree = newTree;
            } else {
                insert(this.rightTree, data);
            }
        }
    }

    private void insert(BTree tree, int data) {
        if (tree.data == data) {
            return;
        }

        if (data < tree.data) {
            if (tree.leftTree == null) {
                BTree newTree = new BTree(data);
                tree.leftTree = newTree;
            } else {
                insert(tree.leftTree, data);
            }
        } else {
            if (tree.rightTree == null) {
                BTree newTree = new BTree(data);
                tree.rightTree = newTree;
            } else {
                insert(tree.rightTree, data);
            }
        }
    }

    public void inorderTraversal(BTree tree) {
        if (tree.leftTree != null) {
            inorderTraversal(tree.leftTree);
        }

        System.out.print(tree.data + ", ");

        if (tree.rightTree != null) {
            inorderTraversal(tree.rightTree);
        }
    }

    public void remove(int data, BTree tree) {
        if (tree == null) {
            return;
        }

        if (data == tree.data) {
            if (tree.leftTree != null && tree.rightTree != null) {
                int minimumValue = getMinimumValue(tree.leftTree);
                remove(minimumValue, tree);

                tree.data = minimumValue;
            } else if (tree.leftTree != null) {
                tree = tree.leftTree;
            } else if (tree.rightTree != null) {
                tree = tree.rightTree;
            } else {
                tree = null;
            }
        } else if (data < tree.data) {
            remove(data, tree.leftTree);
        } else {
            remove(data, tree.rightTree);
        }
    }

    public int getMinimumValue(BTree tree) {
        if (tree.leftTree == null) {
            return tree.data;
        } else {
            return getMinimumValue(tree.leftTree);
        }
    }

    public static void main(String[] args) {
        BTree myTree = new BTree(5);
        myTree.insert(6);
        myTree.insert(12);
        myTree.insert(4);
        myTree.insert(3);
        myTree.insert(6);
        myTree.insert(15);
        myTree.insert(1);
        myTree.insert(9);
        myTree.insert(-2);

        myTree.remove(3, myTree);

        myTree.inorderTraversal(myTree);
    }
}

尽管如此，3仍然出现在顺序遍历中。我做错了什么？

Answer 1

您的第二个插入在我看来很奇怪，因为您只需要创建一个包含数据的新BTree，或者只需使用您已经在其中的同一个插入就可以处理所有可能的情况。inOrderTraversal也是如此。

对于remove，你需要返回一个BTree，以处理"this“引用是你想要删除的那个引用的情况(你不能指定"this")。

class BTree {

    public int data;
    public BTree leftTree;
    public BTree rightTree;

    public BTree(int data) {
        this.data = data;
    }

    public BTree(int data, BTree leftTree, BTree rightTree) {
        this.data = data;
        this.leftTree = leftTree;
        this.rightTree = rightTree;
    }

    public void insert(int data) {
        if (this.data == data) {
            return;
        }

        if (data < this.data) {
            if (leftTree == null) {
                leftTree = new BTree(data);
            } else {
                leftTree.insert(data);
            }
        } else {
            if (this.rightTree == null) {
                rightTree = new BTree(data);
            } else {
                rightTree.insert(data);
            }
        }
    }

    public void inOrderTraversal() {
        if (leftTree != null) {
            leftTree.inOrderTraversal();
        }

        System.out.print(data + ", ");

        if (rightTree != null) {
            rightTree.inOrderTraversal();
        }
    }

    //the void equivalents are in comments
    public BTree remove(int data) {
        if (data == this.data) {
            if (leftTree != null && rightTree != null) {
                //this is the only legal case for the void remove.
                int minValue = getMinimumValue();
                this.data = minValue;
                //leftTree.remove(minValue); //and no return is needed
                leftTree = leftTree.remove(minValue);
                return this;
            } else if (leftTree != null) {
                //this = leftTree; //illegal
                return leftTree;
            } else if (rightTree != null) {
                //this = rightTree; //illegal
                return rightTree;
            } else {
                //this = null; //illegal
                return null;
            }
        } else if (data < this.data) {
            leftTree = leftTree.remove(data);
            return this;
        } else {
            rightTree = rightTree.remove(data);
            return this;
        }
    }

    public int getMinimumValue() {
        if (leftTree == null) {
            return data;
        } else {
            return leftTree.getMinimumValue();
        }
    }

    public static void main(String[] args) {
        BTree myTree = new BTree(5);
        myTree.insert(6);
        myTree.insert(12);
        myTree.insert(4);
        myTree.insert(3);
        myTree.insert(6);
        myTree.insert(15);
        myTree.insert(1);
        myTree.insert(9);
        myTree.insert(-2);

        myTree = myTree.remove(3);

        myTree.inOrderTraversal();
    }
}