C：如何为生成树释放内存？

发布于 2024-10-25 08:49:54 字数 846 浏览 4 评论 0原文

我有一个只有父母和孩子的 n 元树结构。生成树本身只包含一个节点，即根节点。然后创建与其他节点或根链接的节点。每个节点（包括根）最多允许有 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

原文

I have a n-ary tree structure with only parents and children. The spantree itself holds only one node, the root. Then there are created nodes which are linked with other nodes or the root. Each node(root included) are allowed to have up to MAXCHILDREN children nodes.
Here's the structure:

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;

Visual picture:

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

After I have created my tree I want to deallocate the whole thing but I am unsure on which way to do it. I can't start deallocating from the root because then the tree will get broken. So I imagine that I have to start from the leaves and going up to the root?
But that means that I have to find the deepest leaves first, right? I feel quite confused on how to start.

I don't think it's neccesary but for insurance here's what I use everytime I need to make a new node:

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

指尖上得阳光 2024-11-01 08:49:54

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

    void free_node( node *n ) {
    if(n) { 
      for(int i=0; i<MAXCHILDREN; i++)
        free_node(n->children[i]);
      free(n);
      }
    }

You need to check if the node you're freeing has children, and free them first if it does.

    void free_node( node *n ) {
    if(n) { 
      for(int i=0; i<MAXCHILDREN; i++)
        free_node(n->children[i]);
      free(n);
      }
    }

回复收藏 0 原文

埖埖迣鎅 2024-11-01 08:49:54

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

void deleteNode(node * Node) {
  for (int i = 0; i < MAXCHILDREN; ++i) {
    if (node->children[i]) {
      deleteNode(node->children[i]);
      free(node->children[i]);
    }
  }
}

Recurse through the tree, call the recursive function first, then free memory.

void deleteNode(node * Node) {
  for (int i = 0; i < MAXCHILDREN; ++i) {
    if (node->children[i]) {
      deleteNode(node->children[i]);
      free(node->children[i]);
    }
  }
}

回复收藏 0 原文