从二进制搜索树中删除节点-Java 学习之路

当我调用deleteNode方法时，我的二进制搜索树程序似乎没有删除任何内容 . BST完美构建，只是删除不起作用的节点部分 . 我这样从我的主要叫它：

System.out.println("Please enter a number you would like to delete from the tree");
    temp = reader.nextLine();
    try {
        int numTemp = Integer.parseInt(temp);
        TreeNode treeTemp = bst.deleteNode(numTemp, bst.getRoot());
        bst.setRoot(treeTemp);
    }
    catch(Throwable e){
        System.err.println(e);
    }
    bst.printInBST(bst.getRoot());

在我的BinarySearchTree类中，我实现了我的deleteNode方法，如下所示：

public TreeNode deleteNode(int x, TreeNode temp){
    if(temp != null){
        if(x > (int)((Integer)temp.getValue())){
            temp.setLeft(deleteNode(new Integer(x), temp.getLeft()));
        }
        else if(x < (int)((Integer)temp.getValue())){
            temp.setRight(deleteNode(new Integer(x), temp.getRight()));
        }
        else if(temp.getLeft() != null & temp.getRight() != null){
            TreeNode temp2 = new TreeNode(temp.getRight().getValue());
            while(temp2.getLeft() != null){
                temp2 = temp2.getLeft();
            }
            temp = temp2;
            temp.setRight(remove(temp.getRight()));
        }
    }
    return temp;
}
public TreeNode remove(TreeNode temp){
        if(temp.getLeft() != null){
            temp.setLeft(remove(temp.getLeft()));
            return temp;
        }
        else {
            return temp.getRight();
        }
}

4 回答

我想你不是在处理

情况1：删除节点是叶节点

情况2：删除节点只有1个孩子

否则如果部分应该是这样的 .

else if( temp.getLeft() != null && temp.getRight() != null ) // Two children
{
      temp.setValue( findMin( temp.getRight() ).getValue());
      temp.setRight ( deleteNode( temp.getValue(), temp.getRight() );
}
else
     temp = ( temp.getLeft() != null ) ? temp.getLeft() : temp.getRight();

return temp;

findMin方法是查找要删除的节点的inorder后继 .

private TreeNode findMin( TreeNode t )
{
        if( t == null )
            return null;
        else if( t.getLeft() == null )
            return t;
        return findMin( t.getLeft() );
}

我希望这能回答你的问题 .

回复于 2024-05-06T17:23:52+08:00

0
编写清晰的代码可以让您更容易发现错误 - 无论是您自己还是其他人 . 第一步是选择比 temp ， temp2 和 treeTemp 更具表现力的变量名称 .

另外，实际上不需要 new Integer(x) 来分配 int 类型的方法参数 . 简单地写 x 具有相同的效果，在运行时更快，并且更容易发现重要的代码 .

至于bug，我看到的第一个是：
```
TreeNode temp2 = new TreeNode(temp.getRight().getValue());
```
这会创建TreeNode的副本 . 由于您只将 value 传递给构造函数，因此更改该副本会设置 left 或 right . 我想知道为什么你认为你需要一份副本？毕竟，你不在这里创建一个：
```
deleteNode(new Integer(x), temp.getRight())
```
接下来，正如Sashwat指出的那样，如果要删除的节点少于2个子节点，则代码不会执行任何操作，因为 deleteNode 中的所有条件都不匹配 .
回复于 2024-05-06T17:23:52+08:00
2
不是100％确定这是否是您唯一的问题，但应该：
```
else if(temp.getLeft() != null & temp.getRight() != null)
```
实际上是：
```
else if(temp.getLeft() != null && temp.getRight() != null)
```
即，当你应该有两个时，你只有一个和“和”操作？
回复于 2024-05-06T17:23:52+08:00

public class BSTNode {
  …

  public boolean remove(int value, BSTNode parent) {
        if (value < this.value) {
              if (left != null)
                    return left.remove(value, this);
              else
                    return false;
        } else if (value > this.value) {
              if (right != null)
                    return right.remove(value, this);
              else
                    return false;
        } else {
              if (left != null && right != null) {
                    this.value = right.minValue();
                    right.remove(this.value, this);
              } else if (parent.left == this) {
                    parent.left = (left != null) ? left : right;
              } else if (parent.right == this) {
                    parent.right = (left != null) ? left : right;
              }
              return true;
        }
  }

回复于 2024-05-06T17:23:52+08:00

从二进制搜索树中删除节点

4 回答

相关问题