java 在二叉搜索树中实现删除节点
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16253716/
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
Implementing Delete a Node in Binary Search Tree
提问by Gaurav Wadhwani
Trying to delete a node from BST. After the execution, the node still persists in the tree. How can I implement it properly?
试图从 BST 中删除一个节点。执行后，该节点仍然存在于树中。我该如何正确实施它？
public void deleteNode(TreeNode removeNode, TreeNode root)
{
if(removeNode.Left==null && removeNode.Right==null) //0 children
{
removeNode = null;
}
else if(removeNode.Left==null)//1 children
{
removeNode = removeNode.Right;
}
else if(removeNode.Right==null)//1 children
{
removeNode = removeNode.Left;
}
else // 2 children
{
int successorValue = this.getSuccessor(removeNode, root);
TreeNode successor = this.search(successorValue,root);
removeNode.data = successor.data;
deleteNode(successor, root);
}
}
回答by MAV
The node is still there because you never remove it from the tree.
该节点仍然存在，因为您从未将其从树中删除。
When you call deleteNodeyou get a referenceto the node you want to delete and the root of the tree. When you say removeNode = null;you set your reference to null, you don't remove the object. This means the nodes in the tree still reference that node.
当您调用时，deleteNode您将获得对要删除的节点和树根的引用。当您说removeNode = null;您将引用设置为 时null，您并没有删除该对象。这意味着树中的节点仍然引用该节点。
To remove the node from the tree you need to remove the references to the node. I don't now what methods you have available, but to send you in the right direction it should be something like this:
要从树中删除节点，您需要删除对节点的引用。我现在不知道您有哪些可用的方法，但要向您发送正确的方向，它应该是这样的：
public void deleteNode(TreeNode removeNode, TreeNode root)
{
TreeNode parent = removeNode.getParent(); //Find parent node to removeNode.
if(removeNode.Left==null && removeNode.Right==null) //0 children
{
if(parent.Left.equals(removeNode))
parent.Left = null; //Set the parents reference to null.
else
parent.Right = null;
}
else if(removeNode.Left==null)//1 child
{
if(parent.Left.equals(removeNode))
parent.Left = removeNode.Right; //Reassign the parents reference to the correct node.
else
parent.Right = removeNode.Right;
}
... //etc.
The point is you have to change the references in the treeand not your local reference. Hope this makes sense.
关键是您必须更改树中的引用而不是本地引用。希望这是有道理的。
