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

Question

我正在用 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

Answer 1

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)。请注意，您还需要考虑如果找到的节点是树的顶部会发生什么（我没有解决这种情况）。

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

Delete function of a binary search tree does not delete leaf node

go

binary-search-tree