在二叉搜索树中删除-Java 学习之路

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

左叶;
右叶;
只有左孩子的左孩子 . //i.e要删除的节点是它父节点的左子节点，它只剩下子节点 .
只有正确孩子的左孩子 .
只有左孩子的右孩子 .
只有正确孩子的正确孩子 .
要删除的节点包含两个子节点，即右侧和左侧 .

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

这是我的代码片段

if(current->left==NULL && current->right==NULL && current->key<prev->key)   //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->key<prev->key) // left     child with one child
prev->left=current->left;
else if(current->left==NULL && current->right!=NULL && current->key<prev->key)
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;
}

3 回答

1
您可以比它简单得多，并且在从BST（二叉搜索树）中删除节点时仅限于三种情况：
- 没有孩子的节点（叶子）：只需删除它 - 没有什么特别需要做的
- 包含一个子节点的节点：将其删除，并将子节点移动到位
- 具有两个子节点的节点：将其与其有序前置任务或后继节点交换，然后将其删除
wiki page包含了一个如何在代码中查看的示例 .

或者作为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);
}
```
回复于 2024-05-03T21:23:47+08:00

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

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

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;
}

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

回复于 2024-05-03T21:23:47+08:00

2
删除NULL指针没有任何不良影响 . 所以，你应该能够做到这一点，没有特殊情况 . 基本部分只是：
```
delete current->left;
delete current->right;
```
回复于 2024-05-03T21:23:47+08:00

在二叉搜索树中删除

3 回答

相关问题