logo标签列表

如何在C语言中删除二叉树中的元素？

cpointersbinary-treefree
5
我可以帮您翻译成中文。这是一篇关于二叉树节点删除的文章。以下是教程中提供的代码片段。

该节点如下所示：

struct node
{
  int key_value;
  struct node *left;
  struct node *right;
};

来源: http://www.cprogramming.com/tutorial/c/lesson18.html

    void destroy_tree(struct node *leaf)
    {
      if( leaf != 0 )
      {
          destroy_tree(leaf->left);
          destroy_tree(leaf->right);
          free( leaf );
      }
    }

我对free(leaf)部分有疑问。作者声称这将递归删除从左下角最底部开始的所有节点。但是，free(leaf)不仅仅只是释放叶子指针的内存吗？难道所有节点都还连接在一起吗？清除是如何进行的？

1
如何删除二叉树中的元素？一次只能删除一个。 - Kerrek SB
树已完全销毁，因此无需断开叶子节点。你可以将它们断开，但这是无用的。为什么不试一下呢？ - Jabberwocky
1
我建议你在纸上画出这个小图，然后尝试使用这个算法来解决它，以便更好地掌握它。对于所有涉及树的事情，我都建议使用这种方法。 - Aleksandar Makragić
你确定你正确地阅读了这段文本吗？清除发生是因为你调用了清除每个分支的方法。 - anon
我认为这会删除树但会导致错误。第一个未删除的节点的左右指针将不为空，但将指向一个自由内存地址...这会导致段错误，对吗？ - gbtimmon
7个回答
3
我正在以图形方式向您展示树会如何变化： 起始状态：
                  10
               /      \
              6        14
             / \       /  \
            free 8    11    18

                  10
               /      \
              6           14
             /   \       /  \
            free free  11    18


                  10
               /       \
              free        14
             /   \       /  \
            free  free  11  18


                   10
                /       \
              free         14
             /   \       /    \
            free  free  free  18

                   10
                 /       \
              free         14
             /   \       /     \
            free  free  free  free

                     10
                 /       \
              free         free
             /   \       /     \
            free  free  free  free

                    free
                 /       \
              free         free
             /   \       /     \
            free  free  free  free

当然，最终这些节点将不再连接，它们也将不存在。我只是用图片展示了这个算法的过程中它们如何改变。如果你有任何进一步的问题，请随时问我。
我强烈建议你，在无法理解树形递归工作原理时，可以在纸上画一张图，然后按照我上面写的算法来进行理解。
2
它以递归方式删除叶子及其分支。我为你画了一个示例。圆圈中的数字表示被释放的叶子的顺序。线条显示代码执行的顺序。

enter image description here

2
在您发布的链接中，作者有一棵树，看起来像这样： 
                         10
                       /    \
                      6      14
                     / \    /  \
                    5   8  11  18
递归删除函数的工作方式是先遍历到最左边，然后再遍历到最右边，最后删除该节点。因此，在上述示例中，以下操作将发生（从包含10的节点开始）：
Node 10 -> leaf!=null -> destroy_leaf(leaf->left)
  Node 6 -> leaf!=null -> destroy_leaf(leaf->left)
    Node 5 -> leaf!=null -> destroy_leaf(leaf->left)
      null -> do nothing and return back to Node 5
    Node 5 - destroy_leaf(leaf->right)
      null -> do nothing and return back to Node 5
    free(Node 5) and return back to Node 6
  Node 6 -> destroy->leaf(leaf->right)
    Node 8 -> leaf!=null -> destroy_leaf(leaf->left)
      null -> do nothing and return back to Node 8
    Node 8 -> destroy_leaf(leaf->right)
      null -> do nothing and return back to Node 8
    free(node 8) and return back to Node 6
  free(node 6) and return back to Node 10
Node 10 -> destroy_left(leaf->right)

上面的内容展示了函数将从节点10递归向左侧的过程。当节点被释放时，它们的父节点会指向已释放的内存，但这没问题，因为当递归解开并释放父节点时，您最终会丢弃父节点。
1
你是正确的。它正在从C的“已分配内存”中回收内存，这很可能是堆栈。由于您正在删除整个树，因此在向上递归树时未正确重建节点并不重要，因为它们即将被销毁。

此代码不是从树中删除或“移除”元素，而是在给定叶节点的情况下销毁整个树。

来自网站的内容

destroy_tree如下所示，实际上将释放存储在节点叶子：tree下的树中所有节点。

1

但是，free(leaf)只是返回叶子指针的内存，对吗？

是的。但这还不是全部。在调用free之前，你看到了什么被调用了吗？

所有节点仍然连接着，不是吗？

无所谓，因为……

清除是如何进行的？

destroy_tree的递归调用向左和向右下降，这将反过来进行递归销毁，最后它会释放并返回给调用者，然后释放等等。最终整个树都被释放了。

1
free(leaf)调用释放被指针leaf所指向的变量分配的内存。这里，它释放了一个struct node类型变量占用的所有12个字节 - 即int value占用的4个字节、node *left指针占用的4个字节和node *right指针占用的4个字节。

通过调用destroy_tree(left)，您正在删除由left指向的子树。您可以将其视为从叶子节点开始燃烧整棵树，先烧左侧分支，再烧右侧分支。
1
让我们从这段代码中尝试理解它：
void delete(struct node* node)
{
if(node==NULL)
return;
delete(node->left);
delete(node->right);
free(node)
}

在这段代码中，控制流将首先转到最左侧的叶子节点，然后从那里开始删除（因为在删除父节点之前，我们必须先删除其子节点）以树为例。
     1
    / \
   2    3
  / \
 4   5

首先，节点4的内存将被释放，然后是节点5，由于free不返回任何值（内存引用被删除），因此父节点也将指向NULL，所以在5之后2将被删除。 希望这可以帮到你。
但是，第一个未释放节点的指针仍然指向一个已释放的节点，这将导致段错误，除非还有另一层我们在这里看不到的东西，对吧？我不完全确定，但似乎是这样--如果是这种情况，我绝对理解海报的观点。 - gbtimmon
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接