3

バイナリ ヒープのように、現在のインデックスから父と子のインデックスを簡単に計算できるようにしながら、ツリーを配列に格納したいと考えています。ツリーには、レベル 0 の単一のルート ノードがあります。ツリーには N レベルがあり、レベル i の各ノードには n(i) 個の子があります。

これはできますか？どのように？

編集：

明確化: (完全な) 二分木を格納できます。つまり、インデックスを明示的に格納しなくても、単一の配列にヒープを格納できます。ルートは 0 で、位置 i のノードの子は 2i+1 と 2i+2 になります。したがって、実際にインデックスを保存する必要なく、親ノードのインデックスから子を計算できます。データ構造はデータ内で暗黙的です。http://en.wikipedia.org/wiki/Binary_heap#Heap_implementationを参照してください。

私の質問: 上で詳述したように、これをより一般的なツリーに一般化できますか。

4

1 に答える 1

2

あなたが言いたいことを理解していれば（レベル i の各ノードには n(i) 個の子がある）、非常に単純です。最初の数字は、ルートの子である n(0) 個の要素が続くルートです。これらの n(0) ノードは、n(1) ノードすべてにうなずきます。n(0) = 3 の場合、最初に n(1) 個のうなずきを配置し、その後に 2 番目のうなずきの場合はすべての n(1) 個のうなずきを配置し、それらの後に 3 番目のうなずきに n(1) 個のうなずきを配置します。うなずく

1 -> 2, 5, 3 ( 1 is the root, and has 2, 5, 3 as children)
2 -> 4, 10
3 -> 45, 35
5-> 12, 31
n(0) = 3, n(1) = 2 , n(2) = 0
Then You should have: {1,  2, 5, 3,  4, 10,   45, 35,  12, 31}

適切なインデックスを作成するには、別の配列を親の位置で保持し、別の配列を最初の子のインデックスで保持する必要があります。または、本当に配列を 1 つだけ保持したい場合は、次のようにする必要があります。
要素ごとに、親のインデックスと最初の子のインデックスの 3 つを保持します。 . 子供が次から次へと生まれるので、常にすべての子供にアクセスでき、常に父親がいます。(ルートの父に -1 を付けます) 次に、次のようにする必要があります。

{1,-1, 3,   2, 0,12,   5, 0, x,    3, 0,  x,     4,  3,  x,  ... } 
{0, 1, 2,   3, 4, 5,   6, 7, 8,    9, 10, 11,    12, 13, 14, ... }
-1 is the father of 1 and 3 is the start of his child
0 is the father of 1 and 12 is the start of his child ( 4 in this case)

「ヒープ」構造が必要な場合は、最大数の子 Mx = ( max(n(i)), 1<=i<=N を見つけて、ステップ MX でヒープを実行する必要があります。各要素は、 pos*MX、pos*MX + 1、..pos*MX + n(k)、および pos/MX の父で、pos はノードのインデックスです。
多くの空きスペースがありますが、ヒープのような構造
お役に立てば幸いです。

于 2012-06-24T18:46:19.567 に答える