C++ 从二叉搜索树中删除一个节点
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/31715769/
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
C++ Delete a node from binary search tree
提问by ABCD
This is the place where I am trying to solve this particular problem: http://mycodeschool.com/work-outs/binary-search-trees/7
这是我试图解决这个特定问题的地方：http: //mycodeschool.com/work-outs/binary-search-trees/7
In case the node to be deleted has both children, the strategy to adopt is to replace that node with the maximum value in its left subtree (lets call it MAX_LEFT). Then you can simply delete the node MAX_LEFT. This strategy is also discussed in our video for this problem.
如果要删除的节点有两个孩子，则采用的策略是用其左子树中的最大值替换该节点（我们称之为 MAX_LEFT）。然后你可以简单地删除节点MAX_LEFT。我们的视频中也针对此问题讨论了此策略。
I am trying to solve this problem by below code. But there are some issues and I am not getting the expected output.
我试图通过下面的代码解决这个问题。但是有一些问题，我没有得到预期的输出。
struct Node
{
int data;
struct Node* left;
struct Node* right;
}
Node* FindMax(Node* root)
{
if(root==NULL)
return NULL;
while(root->right != NULL)
{
root = root->right;
}
return root;
}
Node* DeleteNodeInBST(Node* root,int data)
{
if(root==NULL) return root;
else if(data<=root->data)
root->left = DeleteNodeInBST(root->left, data);
else if (data> root->data)
root->right = DeleteNodeInBST(root->right, data);
else
{
//No child
if(root->right == NULL && root->left == NULL)
{
delete root;
root = NULL;
}
//One child
else if(root->right == NULL)
{
Node* temp = root;
root= root->left;
delete temp;
}
else if(root->left == NULL)
{
Node* temp = root;
root= root->right;
delete temp;
}
//two child
else
{
Node* temp = FindMax(root->left);
root->data = temp->data;
root->left = DeleteNodeInBST(root->left, temp->data);
}
}
return root;
}
回答by fatihk
In the code segment below, after 2 else ifstatement, final elsestatement is never executed, because there is no other possibility:
在下面的代码段中，在 2 个else if语句之后，永远不会执行最后的else语句，因为没有其他可能：
else if(data<=root->data)
root->left = DeleteNodeInBST(root->left, data);
else if (data> root->data)
root->right = DeleteNodeInBST(root->right, data);
else
....
回答by CiaPan
This part
这部分
if(data<=root->data)
root->left = DeleteNodeInBST(root->left, data);
else
...
will step down to the left subtree also when datais equalto the current node root. As a result you will neverget to the third else. Try replacing <=with <.
当等于当前节点时，data也会下级到左子树root。因此，您永远不会到达第三个else。尝试替换<=为<.
回答by ABCD
Got it. I have to remove "=" in "else if(data<=root->data)" and then it works.
知道了。我必须删除“else if(data<=root->data)”中的“=”，然后它就可以工作了。
