c - 如何有效地释放树

Question

我怎样才能有效地释放这棵树？该算法应该适用于此类树中的任何给定节点。所以我会有指向节点的指针，那个节点将是“根”节点。我想释放该节点下的所有内容。

树中的每个节点都是这个结构：

  typedef struct tag
  {
      struct tag* parent;
      struct tag* nextSibling;
      struct tag* previousSibling;
      struct tag* firstChild;
      struct tag* lastChild;     
      char* name;
      char* text;     
  }node;

Answer 1

使用任何标准的树遍历机制并删除所有元素。

http://en.wikipedia.org/wiki/Tree_traversal

Answer 2

我想这会奏效。但实际上，大流士是正确的。您只需使用有效的树遍历，并在每个节点上执行您的操作。

问题变了： 既然您希望它在树中的任何节点上运行，只需先找到根。编写一个在一个方向上进行的树遍历比在树上上下移动要容易得多。

您已将问题从删除树更改为删除树的子集。所以，相反，让我们这样做。首先从树中删除元素（remove_node）。然后执行与我们之前相同的自由操作。

void remove_node(node *self) {
    if (self->previousSibling)
        self->previousSibling->nextSibling = self->nextSibling;
    if (self->nextSibling)
        self->nextSibling->previousSibling = self->previousSibling;
    if (self->parent && self->parent->firstChild == self)
        self->parent->firstChild = self->nextSibling;
    if (self->parent && self->parent->lastChild == self)
        self->parent->lastChild = self->previousSibling;
}

void free_node(node *self) {
    // Free one node. Perhaps this is:
    free(self->name);
    free(self->text);
    free(self);
}

void iterate_nodes(node *root, void op(node *self) ) {
    if (root == NULL)
        return;
    iterate_nodes(root->nextSibling, op);
    iterate_nodes(root->firstChild, op);
    op(root);
}

int main() {
    node *node = NULL; // Some node in the tree...
    remove_node(node);
    iterate_nodes(node, free_node);
}

Answer 3

您可以使用标准的后序树遍历算法来释放整棵树。要使其在任何给定节点上工作，只需从遍历所有父链接到根节点开始。例如：

void free_tree(node *n)
{
    // Find the root node of the tree
    while(n->parent)
        n = n->parent;

    free_tree_helper(n);
}

void free_tree_helper(node *n)
{
    // Free all children of this node in post-order traversal
    node *child = n->firstChild;
    while(child)
    {
        // Save the next sibling pointer to avoid dangling pointers
        node *next = child->nextSibling;
        free_tree_helper(child);
        child = next;
    }

    // All the children have been freed, now free the parent
    free(n->name);
    free(n->text);
    free(n);
}

或者，如果您使用内存池来分配树节点，所有节点都来自同一个池，并且该池不包含其他树的节点，您可以一次释放整个内存池，而不必遍历整棵树。这将更加有效，因为它避免了潜在大树中的大量缓存未命中，并且还避免了某些内存碎片问题。