二进制搜索树的删除方法

Question

我正在一个实验室工作，该实验室要求我为二进制搜索树创建一个删除方法。这是我的remove方法的代码。

public void remove(T r)
  {
    remove(root, r);
  }

  private TreeNode <T> remove(TreeNode <T> tree, T r)
  {
    if(tree == null)
    return tree;
    if(r.compareTo(tree.getValue())<0)  // my num is smaller
        tree.setLeft(remove(tree.getLeft(), r));
    else if (r.compareTo(tree.getValue())>0)  // my num is larger
        tree.setRight(remove(tree.getRight(), r));
    else  // this is my number
    {
      if(tree.getLeft() == null && tree.getRight() == null)
      return null;
      else if(tree.getLeft() == null)
      return tree.getRight();
      else if (tree.getRight() == null)
      return tree.getLeft();
    else
    {
      T min = getSmallest(tree.getRight());
      tree.setValue(min);
      //System.out.println("2 + " + toString(tree));
      tree.setRight(remove(tree.getRight(), min));
    }
  }
  return tree;
  }

运行代码时得到的输出是：

移除90后的树。70 80 85 98 100 120

移除70. 80 85 98 100 120后的树

移除85后的树。80 98 100 120

移除98后的树。80 100 120

移除80后的树。100 120

移除120后的树。100

移除100后的树。100

我不知道为什么只有当二叉树中只剩下一个节点时，它才起作用。非常感谢您的帮助。

Answer 1

如果删除根节点，则还必须更新根节点。

public void remove(T r) {
    root = remove(root, r);
}

Answer 2

您可能在代码中调用tree.remove（r），它不返回任何内容，也不更改tree，而只更改它的子级或值。解决这个问题的方法是更改

public TreeNode<T> remove(T r)
  {
    return remove(root, r);
  }

和使用

tree = tree.remove(r)

在代码中。要查看代码中发生了什么：我假设您有一个构造函数TreeNode（parent，left，right，value）

TreeNode<Integer> tree = new TreeNode(null,null,null,100);
tree.remove(100);
#remove(100) is called
#remove(root,100) is called
#remove(root,100) returns null after if(tree.getLeft() == null && tree.getRight() == null) without changing anything
#remove(100) returns