0

私は親と子だけのn-aryツリー構造を持っています。スパンツリー自体は、ルートという1つのノードのみを保持します。次に、他のノードまたはルートにリンクされたノードが作成されます。各ノード（ルートを含む）には、最大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トラバースについて何か聞いたことがありますか？同じ手法を使用して、すべてのノードを削除します。これにより、すべての子が削除された後、親が自動的に削除されます。

于 2011-03-22T12:12:20.177 に答える