Java，二叉树删除方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/836212/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java, Binary tree remove method
提问by user101934
I am trying to write a remove(node cRoot, Object o)function for a sorted binary tree.
我正在尝试remove(node cRoot, Object o)为排序的二叉树编写一个函数。
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?
它不能正常工作。要删除节点，您必须修复树以修复漏洞。这应该怎么做？
回答by z -
There are generally two ways of performing a remove on the tree:
在树上执行remove通常有两种方式：
First method:
第一种方法：
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.
删除节点，然后将其替换为任一子节点。然后，通过执行父子交换来重新排序树，直到树再次排序。
The second method:
第二种方法：
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.
遍历树以找到属于根*的下一个（最高或最低）值，如果它是叶节点，则将其与根交换，然后修剪要删除的值。如果它是内部节点，则必须在该节点上递归调用 remove。重复直到删除一个叶节点。
*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.
*我的意思是，如果您将 BST 转换为排序列表，那么您将需要选择根左侧或右侧的任一值作为新根。即右子树的最左子树，或左子树的最右子树。
回答by Yuval Adam
The basic pseudo-code for erasing a node from a sorted tree is pretty simple:
从排序树中删除节点的基本伪代码非常简单：
- erase the node value
- find child node with maximum value
- make it the root node
- if it had children - goto 2 recursively
- 擦除节点值
- 找到具有最大值的子节点
- 使其成为根节点
- 如果它有孩子 - 递归地转到 2
Basically what you are doing is bubbling nodes up the tree, each time the maximum of the children node in each node, so that in the end you stay with a sorted tree, and only one node missing at the end of the full path you went.
基本上你正在做的是在树上冒泡节点，每次都是每个节点中子节点的最大值，所以最后你留在一个排序的树上，并且在你走的完整路径的末尾只有一个节点丢失.
Also - see wikipedia on the subject, they have some sample code in C as well.
另外 - 请参阅有关该主题的维基百科，他们也有一些 C 语言示例代码。
回答by Alex
In the simple case3 you can use next algorithm:
在简单的 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
}
In more complicated case you may need to rebalance your tree (see AVL trees, http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.htmlfor C++ example)
在更复杂的情况下，您可能需要重新平衡树（参见 AVL 树，http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html以获取 C++ 示例）
回答by user101934
- leaf-delete node
- 1-child Promote the subtree
- 2-child case replace the node with either
- in order successor or predecessor
- left most of the right subtree or
- right most of the left subtree
- 叶删除节点
- 1-child 提升子树
- 2-child case 将节点替换为
- 按顺序继任者或前任
- 左大部分右子树或
- 左子树的最右侧
回答by guzoff
I found this code on Habrahabr. I've just added comments.
我在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;
}
}
