0

ANSI C (*) でツリーをどのように実装しますか?

struct Element
{
    ...
    struct Element *pChildElements; // Use dynamic array?
};

(*) 木 (二分木ではない) の最も一般的な定義を意味します。

4

2 に答える 2

3

最適な実装方法 (および多くの方法があります) は、特定のアプリケーションによって異なる場合があります。たとえば、子ノードまたは子ポインタを配列に格納することは、一部のアプリケーションでは望ましい場合がありますが、他のアプリケーションではまったく不要です。子へのインデックスベースのランダムアクセスが実際に必要ですか? その場合は、配列を使用してください。

任意のツリーを実装するための古典的な非配列アプローチは、各ノードに 2 つのポインターを格納することです。つまり、最初の子へのポインターと次の兄弟へのポインターです。

struct Element
{
  ...
  struct Element *p_first_child;
  struct Element *p_next_sibling;
};

つまり、各ノードには基本的に、その子のリストへのポインタが含まれています。

たとえば、3 つの子を持つノードは、次のリンク構造で表されます。

    Node
     |
  (first child)
     |
     V
   Child1 --(next sibling)--> Child2 --(next sibling)--> Child3

この実装では、各ノードで 2 つのポインターのみを使用して任意のツリーを格納できます。追加の配列は必要ありません。子ノードはリストに格納されるため、順番にしかアクセスできません。

このアプローチから得られる興味深い観察結果は、結果として得られるデータ構造はバイナリツリーと見なすことができるということです。つまり、任意のツリーは同等のバイナリ ツリーで表すことができます。

于 2012-08-13T22:09:28.870 に答える
0

要素構造の実装はうまくいきましたが、バイナリ ツリーまたは B-Tree を使用して、動的な割り当て/割り当て解除を回避してください。

また、ツリーを挿入/削除/初期化/検索/ソート/列挙する一連の関数を提供します。

AddToMyBTree(ツリー ヘッドへのポインタ、新しい要素) のような名前を思い付くことができます。

必要に応じて、通常の操作よりも多くの機能を考え出すことができます。

私はあなたの質問を誤解していると思います:ツリー要素を列挙したい場合は、間違いなく再帰を使用します。また、子要素リストを null オブジェクトで終了するか、子要素を含む要素を追加する必要があります。

ProcessNode(element* pElement)
{
    element* pChild = pElement.pChildElements;

    // process the element here


    // then begin to process the child elements.
    while (pChild)
    {
        ProcessNode(pChild);
        pChild++;
    }
}

要素を処理する関数にポインターを渡すことができるので、この列挙子をツリーのジェネリックにすることができることに注意してください。

于 2012-08-13T21:59:25.487 に答える