C: Как освободить память для связующего дерева?

Question

У меня 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

Answer 1

Вам нужно проверить, есть ли у освобождаемого узла дочерние элементы, и сначала освободить их, если он есть.

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

Answer 2

Выполнить рекурсивный поиск по дереву, сначала вызвать рекурсивную функцию, затем освободить память.

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

Answer 3

Вы правы, вам нужно использовать вашу любимую функцию обхода, чтобы найти листья, а затем освободить их, прежде чем освободить родительские узлы.После того, как дети были освобождены, у вас есть еще один листовой узел, который вы можете затем освободить.

Вам нужно будет использовать рекурсию.Наслаждайтесь!

Answer 4

Вы слышали что-нибудь о обходе POST-ORDER?Вы используете ту же технику, чтобы удалить все узлы.Это автоматически удаляет родителей после того, как все их дети удалены.