0

このツリーを効果的に解放するにはどうすればよいですか? そのアルゴリズムは、そのようなツリー内の任意のノードに対して機能するはずです。したがって、ノードへのポインタがあり、そのノードは「ルート」ノードになります。そして、そのノードの下にあるものをすべて解放したいと考えています。 ここに画像の説明を入力

ツリー内のすべてのノードは次の構造体です。

  typedef struct tag
  {
      struct tag* parent;
      struct tag* nextSibling;
      struct tag* previousSibling;
      struct tag* firstChild;
      struct tag* lastChild;     
      char* name;
      char* text;     
  }node;
4

3 に答える 3

1

標準のツリー トラバーサル メカニズムのいずれかを使用して、すべての要素を削除します。

http://en.wikipedia.org/wiki/Tree_traversal

于 2013-03-28T17:03:18.380 に答える
1

これでうまくいくと思います。しかし実際には、ダリウスは正しい。有効なツリー トラバーサルを使用し、各ノードで操作を実行するだけです。

質問が変更されました: そして、これをツリー内の任意のノードで操作したいので、最初にルートを見つけてください。ツリーを上ったり下ったりするよりも、一方向に進むツリー トラバーサルを書く方がはるかに簡単です。

質問をツリーの削除からツリーのサブセットの削除に変更しました。では、代わりにこうしましょう。最初にツリーから要素を削除します (remove_node)。そして、以前と同じフリーを実行します。

void remove_node(node *self) {
    if (self->previousSibling)
        self->previousSibling->nextSibling = self->nextSibling;
    if (self->nextSibling)
        self->nextSibling->previousSibling = self->previousSibling;
    if (self->parent && self->parent->firstChild == self)
        self->parent->firstChild = self->nextSibling;
    if (self->parent && self->parent->lastChild == self)
        self->parent->lastChild = self->previousSibling;
}

void free_node(node *self) {
    // Free one node. Perhaps this is:
    free(self->name);
    free(self->text);
    free(self);
}

void iterate_nodes(node *root, void op(node *self) ) {
    if (root == NULL)
        return;
    iterate_nodes(root->nextSibling, op);
    iterate_nodes(root->firstChild, op);
    op(root);
}

int main() {
    node *node = NULL; // Some node in the tree...
    remove_node(node);
    iterate_nodes(node, free_node);
}
于 2013-03-28T17:07:23.997 に答える
0

標準のポストオーダー ツリー トラバーサル アルゴリズムを使用して、ツリー全体を解放できます。任意のノードから機能させるには、すべての親リンクをルートにトラバースすることから始めます。例えば：

void free_tree(node *n)
{
    // Find the root node of the tree
    while(n->parent)
        n = n->parent;

    free_tree_helper(n);
}

void free_tree_helper(node *n)
{
    // Free all children of this node in post-order traversal
    node *child = n->firstChild;
    while(child)
    {
        // Save the next sibling pointer to avoid dangling pointers
        node *next = child->nextSibling;
        free_tree_helper(child);
        child = next;
    }

    // All the children have been freed, now free the parent
    free(n->name);
    free(n->text);
    free(n);
}

または、メモリ プールを使用してツリー ノードを割り当てる場合、すべてのノードが同じプールから取得され、プールに他のツリーのノードが含まれていない場合は、メモリ プール全体を一度に解放するだけで済みます。ツリー全体をトラバースします。これは、潜在的に大きなツリーでの多くのキャッシュ ミスを回避し、特定のメモリ フラグメンテーションの問題も回避するため、はるかに効率的です。

于 2013-03-28T17:07:34.340 に答える