Java，二叉树删除方法 [英] Java, Binary tree remove method

问题描述

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

I am trying to write a remove(node cRoot, Object o) function for a sorted binary tree.

这是我到目前为止所拥有的:

Here is what I have so far:

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);
  }
}

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

It does not work correctly. To delete a node you have to repair the tree to fix the hole. How should this be done?

推荐答案

通常有两种在树上执行删除的方法:

There are generally two ways of performing a remove on the tree:

第一种方法:

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

Remove the node, then replace it with either child. Then, resort the tree by doing parent-child swapping until the tree is once again sorted.

第二种方法:

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

Traverse the tree to find the next (highest or lowest) value that belongs as the root*, if it is a leaf node, swap that with the root, then trim off the value you want to remove. If it is an internal node, you will have to recursively call remove on that node. Repeat until a leaf node is removed.

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

*What I mean is, if you convert your BST into a sorted list, then you will want to pick either value to the left or right of the root as the new root. I.e. leftmost child of the right subtree, or right most child of the left subtree.

这篇关于Java，二叉树删除方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！