0

我有一个只有父母和孩子的 n 叉树结构。spantree 本身只包含一个节点，即根。然后创建与其他节点或根链接的节点。每个节点（包括根）最多允许有 MAXCHILDREN 个子节点。这是结构：

typedef struct node{
    unsigned int id;                    //every node has different id
    struct node* parent;                //points to parent node
    struct node* children[MAXCHILDREN]; //pointers to all children of this node
}node;

typedef struct spantree{
    node root;                          //root node
}spantree;

视觉图：

        root
      ___O
     /  / \ 
    O  O   O 
          / \
         O   O

在我创建了我的树之后，我想释放整个事情，但我不确定用哪种方式去做。我不能从根开始解除分配，因为这样树就会被破坏。所以我想我必须从叶子开始，一直到根？但这意味着我必须先找到最深的叶子，对吧？我对如何开始感到很困惑。

我不认为这是必要的，但为了保险，这是我每次需要创建新节点时使用的：

node *newNode;
newNode=(node*)malloc(sizeof(node));
//then I modify it to my preferences
4

4 回答 4

4

您需要检查要释放的节点是否有子节点，如果有，请先释放它们。

    void free_node( node *n ) {
    if(n) { 
      for(int i=0; i<MAXCHILDREN; i++)
        free_node(n->children[i]);
      free(n);
      }
    }
于 2011-03-22T12:12:55.790 回答
3

遍历树，先调用递归函数，然后释放内存。

void deleteNode(node * Node) {
  for (int i = 0; i < MAXCHILDREN; ++i) {
    if (node->children[i]) {
      deleteNode(node->children[i]);
      free(node->children[i]);
    }
  }
}
于 2011-03-22T12:09:55.480 回答
1

你是对的，你需要使用你最喜欢的遍历函数来找到叶子，然后在释放父节点之前释放它们。一旦孩子们被释放，你基本上就可以释放另一个叶节点。

您需要使用递归。享受！

于 2011-03-22T12:11:16.167 回答
0

你听说过 POST-ORDER Traversing 吗？您使用相同的技术来删除所有节点。这会在删除所有子项后自动删除父项。

于 2011-03-22T12:12:20.177 回答