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

Question

我试图理解二叉树中节点的删除.这是我从教程中找到的代码片段,它解释了相同的内容.

该节点如下所示:

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)不仅仅是释放叶子指针的内存吗？是不是所有节点仍然连接？清算是如何进行的？

Answer 1

你是对的。它正在从 C 的“分配内存”中回收内存，这很可能是堆。由于您要删除整个树，因此在树上递归时没有正确重建节点并不重要，因为它们也即将被销毁。

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

来自网站

下面显示的 destroy_tree 实际上会释放存储在节点 leaf: 树下的树中的所有节点。