在 C 中释放二叉树结构

Question

我有一个链表，我猜一棵树看起来像这样：

-> grandma
    -> dad
        -> me
        -> sister
            -> niece
        -> brother
    -> uncle
        -> cousin

我有一个结构如下

struct Node{
    Node *parent;
    Node *next;
    Node *child;
}

我如何释放那个链表？
我的想法是进行深度优先搜索并释放每个节点？

Answer 1

递归深度搜索 (DFS)：你说得对，这是释放二叉树内存的好方法：

remove(node):
    if node is null: return

    //else
    remove(left node)
    remove(right node)

    free(node)

迭代求解： https://codegolf.stackexchange.com/questions/478/free-a-binary-tree
由于您不想使用任何递归解决方案，因此您可以在其中找到描述良好的迭代解决方案。

Answer 2

您可以使用递归解决方案

free(root)
{
    if (root->next == null)
    {
        free(node)
    }
    free(root->left)
    free(right->)
}

Answer 3

您可以优化树的 allocation/deallocation。

想象一下，您想创建一个有 20 或 30 个人的树。您可以分配 30 个 Node 结构的数组：

size_t currentArraySize = 30;
Node* nodes = (Node*)malloc(currentArraySize * sizeof(Node));
size_t nextFreeIndex = 0;

要添加新元素，您可以编写简单的函数：

Node* allocateNode()
{
    // Oops! There's not more memory in the buffer.
    // Lets increase its size.
    if (nextFreeIndex >= currentArraySize) {
        currentArraySize *= 2;
        Node* newNodes = (Node*)realloc(nodes, currentArraySize * sizeof(Node));

        // Should correct pointers (thanks to user3386109)
        if (newNodes != nodes) {
            for (size_t i = 0; i < nextFreeIndex; i++) {
                if (newNodes[i]->parent != NULL)
                    newNodes[i]->parent -= nodes += newNodes;
                if (newNodes[i]->next != NULL)
                    newNodes[i]->next -= nodes += newNodes;
                if (newNodes[i]->child != NULL)
                    newNodes[i]->child -= nodes += newNodes;
            }
        }
    }

    return nodes[nextFreeIndex++];
}

要释放所有节点，您可以 free 单个指针 nodes。

现在的代码看起来有点像 user3386109 写的那样可怕，所以我们可以稍微简化一下：

Node* allocateNode()
{
    // Oops! There's not more memory in the buffer.
    // Lets increase its size.
    if (nextFreeIndex >= currentArraySize) {
        currentArraySize *= 2;
        Node* newNodes = (Node*)realloc(nodes, currentArraySize * sizeof(Node));

        // Should correct pointers (thanks to user3386109)
        if (newNodes != nodes)
            correctPointers(newNodes, nodes);
    }

    return nodes[nextFreeIndex++];
}

#define correctPointer(pointer, oldOffset, newOffset) if (pointer != NULL) { \
                                                          pointer -= oldOffset; \
                                                          pointer += newOffset; \
                                                      }

void correctPointers(Node* newNodes, Node* nodes)
{
    for (size_t i = 0; i < nextFreeIndex; i++) {
        correntPointer(newNodes[i]->parent, nodes, newNodes);
        correntPointer(newNodes[i]->child, nodes, newNodes);
        correntPointer(newNodes[i]->next, nodes, newNodes);
    }
}

Answer 4

迭代版本，灵感来自 Day–Stout–Warren 算法：

void removetree(Node *node)
{
    while(node != NULL)
    {
        Node *temp = node;

        if(node->child != NULL)
        {
            node = node->child;
            temp->child = node->next;
            node->next = temp;
        }
        else
        {
            node = node->next;
            remove(temp);
        }
    }
}

这个算法有点像试图将树转换成一个列表 single-linked 与 next 指针，这很容易通过迭代取消 link 并销毁第一个来销毁物品。然而，它永远不会完成转换，因为它会尽快取消links 并删除头节点，尽管树的其余部分尚未转换。也就是说，它将 relink 步骤与 unlink-and-destroy 步骤交错。

我们用if指令测试第一个（头）节点是否有children。如果是这样，我们将它的 child 设为新的头部，当前节点成为新头部的 next 节点。这样我们在 first-level 列表中多了一个 next link。 'next' 到 now-head 节点变成了 child 到 previous-head 节点，现在是头部的第一个 next.

另一方面，如果头节点没有children，它可能会被删除，它的next成为一个新的头。

这两个步骤由while循环迭代，直到所有children都转换为兄弟姐妹并随后删除。

在 C 中释放二叉树结构

Deallocating binary-tree structure in C

c

algorithm

tree

binary-tree