如何释放一棵树？

Question

一个递归函数来释放整棵树。一个参数可以从树中获取任何节点。每个节点都包含一个指向父节点和子节点的指针。没有辅助函数，也没有其他参数。

我有：

void freeTree(Node *node)
{
  int i, j;
  Node *parent = node->parent;
  for (i = j = 0; i < node->nChild; i++) {
    if (node->child[i]) {
      j++;
      freeTree(node->child[i]);
    }
  }
  if (j != 0 && parent != NULL) {
    freeTree(parent);
  } else {
    free(node);
  }
}

*** 错误：双重释放或损坏 (fasttop)：0x000000000XXXXXXX ****

Answer 1

将代码拆分成几个函数会更容易阅读和理解。

Node* findRoot(Node* node) {
    if (node->parent) {
        return findRoot(node->parent);
    }
    return node;
}

void freeNode(Node* node) {
    int i;
    for (i = 0; i < node->nChild; i++) {
        if (node->child[i]) {
            freeTree(node->child[i]);
        }
    }
    free(node);
}

void freeTree(Node* node) {
    freeNode(findRoot(node));
}

Answer 2

如果您使用的是根节点，那将很容易，只需为所有子节点递归调用该函数，然后释放您所在的节点。找到根很容易，只要递归调用父函数，如果有的话 return。一旦你到达一个没有父节点的节点，从所有子节点中删除父节点 link，这样它们就是它们自己树的根，为它们递归调用函数，然后释放你所在的节点。

    A
   / \
  B   C
     / \
    D   E

如果您使用 D 或 E 调用函数，它会为 C 和 return 调用自身。如果使用 B 或 C 调用，它将使用 A 和 return 调用自身。当调用 A 时，因为没有父级，它将从 B 和 C 中删除父级 link，为 B 和 [=14 调用自身=]、空闲节点 A 和 return。现在 B 没有父级，它将自行释放。由于 C 不再有父节点，它将从 D 和 E 中删除父节点 link，然后为这些节点调用自身，空闲节点 C 和return.

void freeTree(Node *node)
{
    int i;

    /* find root node */
    if (node->parent) {
        freeTree(node->parent);
        return;
    }

    for (i = 0; i < node->nChild; i++) {
        node->child[i]->parent = NULL; /* no parent so will free it and children */
        freeTree(node->child[i]);
    }
    free(node);
}

如何释放一棵树？

How to free a tree?

c

tree