在二叉搜索树中删除

所以当我在二叉搜索树中删除时，我是否需要有7种不同的情况，即

1. 左叶;
2. 右叶;
3. 左孩子只有左孩子。 //即要删除的节点是它父节点的左子节点，它只剩下子节点。
4. 左孩子只有正确的孩子。
5. 只有左孩子的右孩子。
6. 没有合适孩子的正确孩子。
7. 要删除的节点包含两个子节点，即右侧和左侧。

现在，当这段代码使用if-else它变得非常讨厌..有没有其他方法可以做到这一点。

这是我的代码片段

 if(current->left==NULL && current->right==NULL && current->keykey) //left leaf prev->left=NULL; else if(current->left==NULL && current->right==NULL && current->key>prev->key) // right leaf prev->right=NULL; else if(current->left!=NULL && current->right==NULL && current->keykey) // left child with one child prev->left=current->left; else if(current->left==NULL && current->right!=NULL && current->keykey) prev->left=current->right; else if(current->left!=NULL && current->right==NULL && current->key>prev->key) prev->right=current->left; else if(current->left==NULL && current->right!=NULL && current->key>prev->key) prev->right=current->left; else if(current->left!=NULL && current->right!=NULL) { check=current->right; check1=check; while(check->left!=NULL) { check1=check; check=check->left; } *current=*check; check1->left=NULL; } 

Answer 1

您可以比它简单得多，并且在从BST（二叉搜索树）中删除节点时仅限于三种情况：

1. 没有孩子的节点（叶子）：只需删除它 – 没有什么特别需要做的
2. 具有一个子节点的节点：将其删除，并将子节点移动到其位置
3. 具有两个子节点的节点：将其与其有序前置任务或后续节点交换，然后将其删除

维基页面包含一个如何在代码中查看的示例。

或者作为C中的一个非常基本的例子：

 if (current->left==NULL && current->right==NULL) { /* leaf node */ bst_replace(current, NULL); } else if (current->left==NULL || current->right==NULL) { /* node with one child */ bst_replace(current, ((current->left) ? current->left : current->right)); } else { /* node with two children */ Node* successor = bst_next(current); current->data = successor->data; bst_replace(successor, successor->right); } 

Answer 2

我真的不明白这里用来删除的协议。 您似乎没有二进制“搜索”树（树中没有排序）。

但只是简单地使代码。 你可以这样做：

 bool b1 = (current->left == NULL); bool b2 = (current->right == NULL); bool b3 = (current->key > prev->key); int decision_case = b1 * 4 + b2 * 2 + b3; switch(decision_case) { case 0: // fill in code here break; ... ... case 7: // fill in code here break; } 

此外，您应该使用删除来避免内存泄漏。 希望有所帮助。

Answer 3

删除NULL指针没有任何不良影响。 所以，你应该能够做到这一点，没有特殊情况。 基本部分只是：

 delete current->left; delete current->right;