释放为树分配的内存 - C

Question

我有一个定义如下的树，

struct tree {
    char label[MAX_LENGTH];
    char value[MAX_LENGTH];
    struct tree *child;
    struct tree *next;
};

现在我需要释放这棵树分配的内存。我写了下面的代码。

unsigned int tree_free(struct tree *root)
{
    struct tree *current = NULL, *next = NULL, *child = NULL;
    unsigned int freecnt = 0;

    current = root;
    while(current != NULL)
    {
        next = current->next;
        child = current->child;      
        xfree(current);
        freecnt += tree_free(child) + 1;
        current = next;
    }
    return freecnt;
}

此方法返回它释放的项目数，以便我可以根据所做的分配数对其进行验证。这段代码有效。但我不确定这是正确的做事方式。

这是后缀树的实现。对于项目 s，stack，over，overflow，stackoverflow 树看起来像

root
-s
--stack
---stackoverflow
-over
--overflow

欢迎任何改进代码的建议。

Answer 1

如果你需要释放一棵树，你需要步行它，所以我认为代码是正确的。我会以同样的方式完成它（递归地遍历树，沿途释放对象）。我唯一要做的不同就是在递归之后运行 xfree（即交换 xfree(current); 和 freecnt += tree_free(child) + 1; ）。因为现在你先删除一个节点，然后再删除它的子节点，但我觉得最好先删除子节点，然后再删除父节点。

另外，您可以删除 child 变量，因为您只在真正需要时使用它一次。每次递归将为您节省 sizeof(pointer) 堆栈空间；-)

Answer 2

这是一个相当好的解决方案。您对子级使用递归（不会太深），但对兄弟级使用迭代（如果使用递归，会深入）。作为纯递归解决方案，您的代码当然可以更优雅（为 child 和 next 调用 tree_free），但堆栈溢出的风险会大大增加，所以我认为你在那里做出了正确的选择。

话虽如此，如果您重新安排操作顺序，则根本不需要 child：

unsigned int tree_free (struct tree *root) {
    struct tree *current = NULL, *next = NULL;
    unsigned int freecnt = 0;

    current = root;
    while(current != NULL)
    {
        freecnt += tree_free (current->child) + 1;
        next = current->next;
        xfree (current);
        current = next;
    }
    return freecnt;
}

如果您认为同级列表的长度不会那么大，您可以尝试优雅的解决方案：

unsigned int tree_free (struct tree *root) {
    unsigned int freecnt;

    if (root == NULL) return 0;
    freecnt = tree_free (root->child) + tree_free (root->next);
    xfree (root);
    return freecnt + 1;
}

它未经测试，因此我没有做出任何保证或适用性声明，特别是因为它对于大量同级链接的特定情况可能是危险的。我将其更多地包含在内是为了表明递归的可能性。我的建议是使用第一个。