c - ツリーを配列にフラット化する

Question

ツリーを配列に配置する最良の方法を探しています

アイデアは、この原則に従うことです：ツリーの配列実装です が、バイナリツリーを使用していないため、どのノードが子で、どのノードが同じレベルにあるかを知る方法に固執しています。

ASCII を格納する必要があるかもしれませんが、単純に 256 個のポインターの配列を許可することはできません。

どんなアイデアでも大歓迎です。

これの目的は、構造体を使用する代わりに、配列 (ツリー) を GPU に送信することです。

Answer 1

さて、これが私の考えですconverting tree into an array。

MAX_VALツリー内のノードの総数であるsize の配列を取得します。配列の型はノードの型と同じである必要がありますが、フィールドが 1 つ追加されます。親のインデックス値です。この方法で各ノードを保存します。ルート ノードを最初の位置に格納します。と言う1。これで、このノードの子ノードが追加のフィールドの保存と共に保存されます1(これはルートが保存されていたためです)。

この手順をすべてのノードに適用すると、完了です。各ノードでの単純な再帰呼び出しによって、ツリーを取り戻すことができます。

お役に立てれば。:) :)

Answer 2

Ahnentafel のリストは、ほぼ完全にバランスが取れていないとしても、非常に大きくなります。私の推測では、あなたのツリーはバランスが取れていないので、暗黙の親子ポインターの利点はコストを上回ります。非バイナリのアーネンタフェル リストは見たことがありませんが、可能だと思います (暗黙の方程式を求めていましたか?)。

各ノード (ASCII 文字 + ポインター/インデックス) の子ポインターの並べ替えられたリストを保持できますか? この場合、他の人が示唆しているように、ポインターを使用してツリーを構築し、子を成長させることが最善の方法かもしれません。次に、すべてのノードをリストにパックします。ノードを配置する順序を計算し、それらのオフセットのプレフィックス合計を配列に使用し、各ノードの位置インデックスを保存し、最後に子リストを配列にコピーします (子ポインターをインデックスのリストは、ポインターをたどって前のステップのインデックスをクエリすることで実行できます)。

CUDA での子へのトラバースは一定の時間ではありませんが、順序がわかっているため、二分探索を使用して高速化できます。