java - 二叉搜索树删除方法错误

Question

我正在尝试编写一种方法，以递归方式从二叉搜索树中删除节点。我理解该算法，但我的代码当前返回错误。当我尝试删除叶节点(即没有子节点的节点)时，它会删除该节点，还会删除树的最顶层节点。

我已经有了查找节点头的方法 getValue()，以及查找左子树和右子树 getLeft() 和 >getRight()。我还有方法 isEmpty() 来检查树是否为空。

这是我目前的代码，其中x是要删除的节点，a是二叉搜索树:

 public static Tree delete(int x, Tree a) {
        if (a.isEmpty()) {
            return new Tree();
        } if (x>a.getValue()) {
            return delete(x, a.getRight());
        } else if (x<a.getValue()) {
            return delete(x, a.getLeft());
        } else {
            if (a.getLeft().isEmpty()&&a.getRight().isEmpty()) {
                return new Tree();
            } if (a.getRight().isEmpty()) {
                return delete(x, a.getLeft());
            } if (a.getLeft().isEmpty()) {
                return delete(x, a.getRight());
            } else {
                return new Tree(); //not yet completed
            }
        }
    }

任何人都可以给我任何关于为什么会发生这种情况的线索吗？提前致谢

编辑:如果有人偶然发现这个问题，这里是最终起作用的代码

public static Tree delete(int x, Tree a) {
        if (a.isEmpty()) {
            return new Tree();
        } if (x>a.getValue()) {
            return new Tree(a.getValue(), a.getLeft(), delete(x, a.getRight()));
        } else if (x<a.getValue()) {
            return new Tree(a.getValue(), delete(x, a.getLeft()), a.getRight());
        } else {
            if (a.getLeft().isEmpty()&&a.getRight().isEmpty()) {
                return new Tree();
            } if (a.getRight().isEmpty()) {
                return new Tree(a.getLeft().getValue(), delete(a.getLeft().getValue(), a.getLeft()), a.getRight());
            } if (a.getLeft().isEmpty()) {
                return new Tree(a.getRight().getValue(), a.getLeft(), delete(a.getRight().getValue(), a.getRight()));
            } else {
                 return new Tree(max(a.getLeft()), delete(max(a.getLeft()), a.getLeft()), a.getRight());
            }
        }
    }

Answer 1

此方法返回一个空树，而不是将 left 或 right 设置为空。这就是为什么您认为它正在删除顶部节点。而且它看起来并不处理删除节点本身，而只处理子节点。