二叉搜索树节点删除

Question

我一直在尝试实现二叉搜索树的删除功能，但是还没有能够使其在所有情况下正常工作。

这是我最新的尝试：

Node* RBT::BST_remove(int c)
{
    Node* t = get_node(c);
    Node* temp = t;

    if(t->get_left() == empty)
        *t = *t->get_left();
    else if(t->get_right() == empty)
        *t = *t->get_right();
    else if((t->get_left() != empty) && (t->get_right() != empty))
    {
        Node* node = new Node(t->get_data(), t->get_parent(), t->get_colour(), t->get_left(), t->get_right());
        *t = *node;
    }

    return temp;
}

Node* RBT::get_node(int c)
{
    Node* pos = root;

    while(pos != empty)
    {
        if(c < pos->get_data())
            pos = pos->get_left();
        else if(c == pos->get_data())
            return pos;
        else
            pos = pos->get_right();
    }

    return NULL;
}

节点是一个元素，空节点是一个没有任何内容的元素。

我只是想交换这些值，但是我遇到了运行时错误。有什么想法吗？

编辑：我将temp返回以便稍后删除它。

谢谢

- doc

---

如果问题是作业问题，请将其标记为作业。 - wilhelmtell

我以为我在制作二叉搜索树，所以不太确定，但是这棵树上的每个节点最多只能有两个子节点。 - doc

请问您能否完整地发布remove()函数的代码？ - wilhelmtell

谢谢迄今为止的回复，我已经更新了一些信息。我正在remove()中返回temp，并在之后使用delete。 - doc

Answer 1

首先，你的最后一个 else if 条件语句是多余的。将它与一个 else 语句交换。

其次，如果您将节点指针作为参数传入，会更容易处理。您可以编写一个 find() 函数，根据键查找节点。当然我假设您可以更改函数签名。如果您可以将要删除的节点作为参数传入，则可以专注于删除节点而不是添加查找节点的逻辑。否则，仍需编写 find() 函数并用它获取指向相关节点的指针。

在二叉搜索树中删除节点时，必须维护排序，以保持树的完整性。请注意，树中存在支持快速检索元素的特定顺序。因此，请枚举可能出现的情况：

1. 要删除的节点没有子节点。那很容易：释放它的资源即可。

2. 该节点有一个单一的子节点。这也相当简单。释放节点并用其子节点替换它，使子节点占据树中已移除节点的位置。

3. 该节点有两个子节点。我们将该节点称为 D。找到 D 左子树中最右侧的子节点。我们将此节点称为 R。将 R 的值分配给 D，并删除 R（按照该算法的描述）。请注意，R 可能具有零个或一个子节点。

第三种情况的示意图：

         .
        .
       .
      /
     D
    / \
   /\  .
  /  \
 /    \
+------+
        \
         R
        /
       ?

- wilhelmtell

---

谢谢，我现在已经解决了所有问题。现在我只需要担心如何将其转换为红黑树删除操作。 - doc