2

我正在尝试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);
  }
}

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

4

5 回答 5

4

通常有两种方法可以在树上执行删除：

第一种方法：

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

第二种方法：

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

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

于 2009-05-07T18:29:16.853 回答
2

从排序树中擦除节点的基本伪代码非常简单：

  1. 擦除节点值
  2. 找到最大值的子节点
  3. 使其成为根节点
  4. 如果它有孩子 - 递归转到 2

基本上你正在做的是在树上冒泡节点，每次每个节点中的最大子节点，所以最后你会留在一个排序的树上，并且在你去的完整路径的末尾只有一个节点丢失.

另请参阅有关该主题的维基百科，他们也有一些 C 示例代码。

于 2009-05-07T18:28:43.237 回答
1

在简单的 case3 中，您可以使用下一个算法：

if(removed node had left child)
{
   place left child instead of removed node;
   most_right = most right leaf in the left subtree;
   move right child of removed node as right child of most_right;
}
else
{
   place right child instead of removed node
}

在更复杂的情况下，您可能需要重新平衡您的树（参见 AVL 树，http: //www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html以获取 C++ 示例）

于 2009-05-07T18:38:30.623 回答
0
  1. 叶删除节点
  2. 1-child 提升子树
  3. 2-child case 将节点替换为
  4. 按顺序继任者或前任者
  5. 左大部分右子树或
  6. 左子树的最右边
于 2009-05-08T18:06:47.127 回答
0

我在Habrahabr上找到了这段代码。我刚刚添加了评论。

public void remove (T1 k){
    Node<T1,T2> x = root, y = null;
    // from while to if(x == null) - searching for key
    while(x != null){
        int cmp = k.compareTo(x.key);
        if(cmp == 0){
            break;  // quit cycle if key element is found
        } else {
            y = x;
            if(cmp < 0){
                x = x.left;
            } else {
                x = x.right;
            }
        }
    }
    if(x == null) return;   // if key is not found or tree is empty
    if(x.right == null){    // if element found has not right child
        if(y == null){      // if element found is root & has not right child
            root = x.left; 
        } else {            // if element found is not root & has not right child           
            if(x == y.left) y.left = x.left;    
            else y.right = x.left;              
        }
    } else {            // element found has right child, so search for most left of rights
        Node<T1,T2> mostLeft = x.right;
        y = null;
        while(mostLeft.left != null) {
            y = mostLeft;
            mostLeft = mostLeft.left;
        }
        if(y == null){  // if right child of element found has not left child
            x.right = mostLeft.right;
        } else {        // if right child of element found has left child
            y.left = mostLeft.right;
        }
        x.key = mostLeft.key;       
        x.value = mostLeft.value;   
    }
}
于 2016-01-29T17:24:40.730 回答