Java，二叉树删除方法

Question

我正在尝试为已排序的二叉树编写一个 remove(node cRoot, Object o) 函数。

这是我目前所拥有的:

private boolean remove(Node cRoot, Object o) {
  if (cRoot == null) {
    return false;
  }
  else if (cRoot.item.equals(o)) { 
    //erase node fix tree
    return true;
  }
  else if (((Comparable)item).compareTo(cRoot.item)<=0){
    return remove(cRoot.lChild, o);
  }
  else { 
     return remove(cRoot.rChild,o);
  }
}

它不能正常工作。要删除节点，您必须修复树以修复漏洞。应该怎么做？

Answer 1

通常有两种方法可以对树执行删除操作:

第一种方法:

删除节点，然后用任一子节点替换它。然后，通过父子交换对树进行排序，直到树再次排序。

第二种方法:

遍历树找到属于根*的下一个(最高或最低)值，如果它是叶节点，则将其与根交换，然后修剪掉要删除的值。如果它是一个内部节点，您将不得不在该节点上递归调用 remove。重复直到移除一个叶节点。

*我的意思是，如果您将 BST 转换为排序列表，那么您将需要选择根左侧或右侧的值作为新根。 IE。右子树的最左子树，或左子树的最右子树。