gpt4 book ai didi

c++ - 二叉搜索树节点移除

转载 作者:太空狗 更新时间:2023-10-29 21:30:33 25 4
gpt4 key购买 nike

我一直在尝试为二叉搜索树实现删除功能,但无法让它在所有情况下都能正常工作。

这是我最近的尝试:

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

t 是一个节点,empty 只是一个没有任何内容的节点。

我只是想交换值,但出现运行时错误。有什么想法吗?

编辑:我将返回 temp 以便之后将其删除。

谢谢

最佳答案

首先,您的最后一个 else if 条件子句是多余的。用 else 子句替换它。

其次,如果您将指向要删除的节点的指针作为参数,我认为这会让事情变得更容易。您可以编写一个 find() 函数来查找给定键的节点。我当然假设您可以更改函数签名。如果可以将要删除的节点作为参数,则可以专注于删除节点,而不是添加用于查找节点的逻辑。否则,仍然编写 find() 函数并使用它来获取指向相关节点的指针。

当您删除二叉搜索树中的节点时,您必须保持顺序,这样树才不会失去完整性。回想一下,树中有一个特定的顺序支持元素的快速检索。所以,列举可能的情况:

  1. 要删除的节点没有子节点。这很简单:只需释放其资源即可。
  2. 该节点有一个子节点。这也相当简单。释放节点并用其子节点替换它,因此子节点保留已删除节点在树中的位置。
  3. 该节点有两个 child 。我们称节点为 D。找到 D 的左子树的最右边的 child 。我们称此节点为 R。将 R 的值赋给 D,并删除 R(如本算法中所述)。请注意,R 可以有零个或一个 child 。

第三种情况,如图所示:

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

关于c++ - 二叉搜索树节点移除,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2574041/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com