java - Java，二叉树删除方法

我正在尝试为已排序的二叉树编写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);
  }
}

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

最佳答案

通常有两种对树执行删除的方法：

第一种方法：

删除该节点，然后将其替换为任何一个子节点。然后，通过进行父子交换来重新排序树，直到重新排序树为止。

第二种方法：

遍历树以查找属于根*的下一个（最高或最低）值（如果它是叶节点），请与根交换该值，然后修剪要删除的值。如果它是内部节点，则必须在该节点上递归调用remove。重复直到删除叶节点。

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