删除叶子节点的二叉搜索树删除函数

在实现 Go 语言中的二叉搜索树时，遇到了删除叶子节点的问题。当要删除的值 8 时，预期输出中应删除包含 8 的节点，但实际输出中仍包含该节点。

我正在 go 中实现二叉搜索树。 到目前为止，我成功实现了以下功能：

• 搜索
• 插入
• 按顺序遍历

我唯一未能成功实现的功能是删除功能。 当要删除的节点是叶子时，不会被删除。

当我尝试删除包含值 8 的节点时，我期待以下输出：

{10 <nil> 0xc00009a060}
{12 <nil> <nil>}
{15 0xc00009a018 0xc00009a030}
{18 <nil> <nil>}
{20 0xc00009a078 0xc00009a090}
{25 <nil> <nil>}

但是，我得到以下输出：

{8 <nil> <nil>}
{10 0xc00009a048 0xc00009a060}
{12 <nil> <nil>}
{15 0xc00009a018 0xc00009a030}
{18 <nil> <nil>}
{20 0xc00009a078 0xc00009a090}
{25 <nil> <nil>}

您可以在这里找到我的源代码：https://play.golang.org/p/oacyegct-qi

正确答案

if value < tree.data {
    *parent = *tree
    tree = tree.left
} else if value > tree.data {
    *parent = *tree
    tree = tree.right
} 

在本节中，*parent = *tree 正在获取节点的副本。稍后您可以使用 parent.right = nil 来修改副本（而不是树中从上方链接的节点）。因此，将 *parent = *tree 更改为 parent = tree 可以解决该问题 (playground)。请注意，您还需要考虑如果找到的节点是树的顶部会发生什么（我没有解决这种情况）。

理论要掌握，实操不能落！以上关于《删除叶子节点的二叉搜索树删除函数》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！