我正在尝试编写一种方法,以递归方式从二叉搜索树中删除节点。我理解该算法,但我的代码当前返回错误。当我尝试删除叶节点(即没有子节点的节点)时,它会删除该节点,还会删除树的最顶层节点。
我已经有了查找节点头的方法 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());
}
}
}
最佳答案
此方法返回一个空树,而不是将 left 或 right 设置为空。这就是为什么您认为它正在删除顶部节点。而且它看起来并不处理删除节点本身,而只处理子节点。
关于java - 二叉搜索树删除方法错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41876777/