如何释放树，C占用的内存？

Question

我目前正在处理具有这种结构的通用树：

typedef struct NODE {

    //node's keys
    unsigned short *transboard;
    int depth;
    unsigned int i; 
    unsigned int j;
    int player;
    int value;


    struct NODE *leftchild; //points to the first child from the left
    struct NODE *rightbrothers; //linked list of brothers from the current node

}NODE;

static NODE *GameTree = NULL;

虽然分配不同节点的函数是（不要太在意键的值，基本上分配 children-nodes。如果没有新的 child向左 child，否则它会在列表末尾 "node->leftchild->rightbrothers"):

static int AllocateChildren(NODE **T, int depth, unsigned int i, unsigned int j, int player, unsigned short *transboard) {
NODE *tmp = NULL;

if ((*T)->leftchild == NULL) {
    if(  (tmp = (NODE*)malloc(sizeof(NODE))  )== NULL) return 0;
    else {
        tmp->i = i;
        tmp->j = j;
        tmp->depth = depth;
        (player == MAX ) ? (tmp->value = 2 ): (tmp->value = -2);
        tmp->player = player;
        tmp->transboard = transboard;

        tmp->leftchild = NULL;
        tmp->rightbrothers = NULL;

        (*T)->leftchild = tmp;
    }
}

else {
    NODE *scorri = (*T)->leftchild;
    while (scorri->rightbrothers != NULL)
        scorri = scorri->rightbrothers;

    if( ( tmp = (NODE*)malloc(sizeof(NODE)) )== NULL) return 0;
    else {
        tmp->i = i;
        tmp->j = j;
        tmp->depth = depth;
        (player == MAX) ? (tmp->value = 2) : (tmp->value = -2);
        tmp->player = player;
        tmp->transboard = transboard;

        tmp->leftchild = NULL;
        tmp->rightbrothers = NULL;
    }
    scorri->rightbrothers = tmp;


}

return 1;

}

我需要想出一个函数，可能是递归的，它会释放整个树，到目前为止我已经想出这个：

 void DeleteTree(NODE **T) {

 if((*T) != NULL) {
    NODE *tmp;
    for(tmp = (*T)->children; tmp->brother != NULL; tmp = tmp->brother) {
        DeleteTree(&tmp);
    }

    free(*T);

 }
}

但它似乎不起作用，它甚至没有释放单个内存节点。关于我错在哪里或如何实施的任何想法？ P.s。我从我老师的伪代码中得到了递归函数的概念。但是我不确定我是否用我的树在 C 语言中正确翻译了它。伪代码：

1: function DeleteTree(T)
2:    if T != NULL then
3:       for c ∈ Children(T) do
4:          DeleteTree(c)
5:       end for
6:       Delete(T)
7:    end if
8: end function

Answer 1

如果我要分配大量将同时消失的树节点，我喜欢做的一件事是在 'batches' 中分配它们。我 malloc 然后作为节点数组，并在保存指向数组的指针（在如下函数中）后从特殊的 nodealloc 函数中分发它们。要删除树，我只是确保我没有保留任何引用，然后调用免费例程（也如下所示）。

这也可以减少您分配的 RAM 量，如果您很幸运（或非常聪明）您的初始 malloc 或者可以相信 realloc 在您缩小块时不会移动它.

struct freecell { struct freecell * next; void * memp; } * saved_pointers = 0;

static void
save_ptr_for_free(void * memp)
{
    struct freecell * n = malloc(sizeof*n);
    if (!n) {perror("malloc"); return; }
    n->next = saved_pointers;
    n->memp = memp;
    saved_pointers = n;
}

static void
free_saved_memory(void)
{
    while(saved_pointers) {
        struct freecell * n = saved_pointers;
        saved_pointers = saved_pointers->next;
        free(n->memp);
        free(n);
    }
}

Answer 2

我刚刚意识到我在代码中犯了一个大错误，我会自己回答，因为没有人找到答案。

错误出在这段代码：

for(tmp = (*T)->children; tmp->brother != NULL; tmp = tmp->brother) {
    DeleteTree(&tmp);
}

首先，Ami Tavory 对 for 条件的看法是正确的，只要 tmp != NULL，我就需要继续基本上它不会工作，因为在 DeleteTree(&tmp) 之后，我无法再访问 tmp 中的内存，因为 它显然被删除了 ，所以在 for 结束的第一个循环之后我可以' t do tmp = tmp->rightbrother 移动到下一个要删除的节点，因为 tmp->rightbrother 不再存在，因为我刚刚删除了它。为了修复它，我只需要将 tmp->brother 保存在其他地方：

void DeleteTree(NODE **T) {

   if((*T) != NULL) {
       NODE *tmp, *deletenode, *nextbrother;

       for(tmp = (*T)->children; tmp != NULL; tmp = nextbrother) {
           nextbrother = tmp->rightbrother;
           DeleteTree(&tmp);

       }

   canc = (*T);
   free(*T);
   (*T) = NULL;
  }

}

Answer 3

为了完整起见，我想添加我的 DeleteTree 版本

void DeleteTree(NODE *T) {
  if(T != NULL) {
    DeleteTree(T->rightbrothers);
    DeleteTree(T->leftchild);
    free(T);
  }
}

我认为它不那么晦涩，也更容易阅读。它基本上解决了 DeleteTree 中的问题，但通过消除循环。

由于我们递归地释放节点，所以我们不妨递归地完成整个过程。

如何释放树，C占用的内存？

How to free memory occupied by a Tree, C?

c

free

tree