c - 你将如何在 C 中释放一个二叉树结构

Question

我有一个简单的树结构

  struct Node{
    struct node *l;
    struct node *r;
    int value;
  };

我应该如何释放这样一个结构，因为一个简单的 free(node) 不会工作，因为它内部有 2 个指针。我是否必须从给定的根开始横穿整棵树，然后释放它的左、右，最后释放它自己？这是我应该如何解决这个问题吗？

  void destroy_tree(struct Node *node){
    if(node->r != NULL){
      destroy_tree(node->r);
      free(node->r);
    }
    if(node->l != NULL){
      destroy_tree(node->l);
      free(node->l); 
    }
    free(node);
  }

Answer 1

您应该按照后序遍历的顺序删除节点。先删左节点/右节点，再删右节点/左节点，再删根。

void del(node *root)
{
  if(root)  // if(root!=NULL) checking if root is null
  {
    del(root->left);
    del(root->right);
    free(root);
  }
}

您的代码遵循相同的想法，但我展示了一种更简洁的方法。

void destroy_tree(struct Node *node){
    if(node->r != NULL){
      destroy_tree(node->r);
      free(node->r); ----> redundant
    }
    if(node->l != NULL){
      destroy_tree(node->l);
      free(node->l); -----> redundant. You have already deleted it.
    }
    free(node);
  }

您基本上遵循后序遍历。