c - 在 C 中释放一棵树

Question

所以我得到了树的结构，其中每个节点最多有 2 个子节点:

typedef struct one_node_t one_node_t;

typedef struct two_nodes_t two_nodes_t;

typedef struct my_tree_t {
  int numberOfNodes; //== 1 || numberOfNodes == 2

   // If the node is a leaf, it is represented by (*oneNode==NULL && numberOfNodes == 1)
    union {
       one_node_t* one;
       two_nodes_t* two;
    } nodeC;
} my_tree_t;

struct one_node_t {
  one_node_t* child;
};

struct two_node_t {
  my_tree_t children[2];
};

现在我试图编写一个函数 void freeMyTree(my_tree_t* myTree) ，它应该释放 myTree 指向的树的分配空间:

void freeMyTree(my_tree_t* myTree) {
  if(myTree->numberOfNodes == 2){
      freeMyTree(myTree->nodeC.two->children);
      freeMyTree(&myTree->nodeC.two->children[1]);
      free(myTree->nodeC.two);
      myTree->nodeC.two = NULL;
  }else{
      if(myTree->nodeC.one->child != NULL)
          freeMyTree(myTree->nodeC.one->child);
      free(myTree->nodeC.one);
      myTree->nodeC.one = NULL;
  }
}

但似乎没有空间被释放。我想我自己对如何释放空间一定有某种误解，但谷歌搜索并没有帮助我理解它。

我认为空间没有释放，因为我使用带有 -fsanitize=leak 选项的 gcc 创建文件。

如果我之前创建了一个 my_tree_t* a = calloc(1, sizeof(my_tree_t)) ，leak sanitizer 会告诉我是否没有释放它。然而，在调用 freeMyTree(a) 之后，它仍然会告诉我同样的事情。

编辑: 错误消息明确指出一/二未释放。因为它们指向如下行:

my_tree_t t;
t.nodeC.two = calloc(1, sizeof(two_nodes_t)); //<== POINTING TO THIS LINE

Answer 1

这不是一个每个节点最多有 2 个子节点的树。这是一棵树，其中每个节点要么正好有两个子节点，要么根本没有子节点，并且有一个关联的以 1 为基数的自然数。确实，

struct one_node_t {
   one_node_t* child;
};

不包含子树。它是一个链表，节点中没有任何信息。这样的列表携带的唯一信息是它的长度。所以这是一些自然数的低效表示。 (我们忽略循环链表的可能性)。

释放此类列表的正确方法类似于

one = myTree->one;
while (one) {
  tmp = one->child;
  free(one);
  one = tmp;
}