删除节点二进制搜索树

Question

目前，我在理解如何在没有传递节点时从二进制搜索树中删除节点时遇到了一个问题。我有两个类，BSTSet和BSTNode，每个类都有一个remove方法。。

public class BSTSet <E extends Comparable<E>> extends AbstractSet <E> {

  // the root of the supporting binary search tree
  private BSTNode<E> root;

  // number of elements in the set
  private int count = 0;


  public boolean remove(E item) {
     if(root == null) return false;
     else return root.remove(item);
  }
}


 public class BSTNode <E extends Comparable<E>> {

   private E value;
   private BSTNode<E> left;
   public BSTNode<E> right;

   public BSTNode<E>remove(E item) {
      //The code i'm confused about
   }

 }

当我被传递一个节点时，我理解删除方法，但当我在根上调用remove方法并试图从node类中删除节点时，我不知道从何处开始。有人能告诉我吗？谢谢如果您想了解更多信息，请询问。

Answer 1

我觉得这是一个学校作业（因为使用二元搜索树几乎不存在，所以我会解释，但我不会包含任何代码）。

从树中删除元素时，希望从BSTNode中进行一些升级。正当要删除的节点的右侧子节点是将取代已删除节点的节点。您还没有包含关于添加的代码，但我假设右侧大于根节点，左侧小于根节点。这意味着如果删除当前节点，则要升级下一个最近的节点，即右侧。

现在，你有问题了。如果当前的\u节点。右侧有一个自己的左侧节点，那么您可能会有两个左侧节点。您将要移动当前的\u节点。正当左侧位于当前的\u节点处。左边正当然后这个问题在树的其余部分递归地重复出现，因此您需要进行相应的调整。只需确保不会因为替换节点而没有处理子节点，从而使节点更靠近叶子。

如果有什么不清楚的地方，或者你有其他问题，请告诉我。正如我所说，我不介意帮助你，但我想每个人都会同意，我们不想为你写作业，所以我不会包含这个问题的特定代码来为你解决它。。。对不起：/