親配列のn-aryツリーのレベルごとのトラバーサル？

Question

親配列に格納されたn個のツリーが与えられ、配列へのポインタの配列に格納された子が最初の値は子の数です。

（childArray [2] [0]どのように、キューを使用して

3 
/|\ 
0 2 4 
| |\ 
1 5 6 

：2 2人の子供を持って、childArray [2] [1]など、その最初の子が5であることを示している）

parentArray = {3, 0, 3, -1, 3, 2, 2}; 
childArray = {{1, 1}, {0}, {2, 5, 6}, {3, 0, 2, 4}, {0}, {0}, {0}}; 

は、次のようになります木を生成します次のようなレベルでツリーレベルを出力できますか：

レベル1：3

レベル2：0、2、4

レベル3：レベル1は単にルートであるため、1、5、6つの

レベル1及び2は、容易ですレベル2はちょうど子供ですが、その後は子供の子供を得る方法を理解できません。

Answer 1

これを行う1つの方法は、queueデータ構造を使用することです。

キューqから始まり、親が-1の（一意の）項目のインデックスに配置します。さて、各ステップで、Qまでは

• を実行し、空であるV < - ポップ（Q）（ポップヘッド）それぞれの子に対して
• 印刷アウトV
• ワットVの、プッシュ（Q、V）（OT尾部を押す）

01を行います例えば

は、ここにあなたのケースのための最初のステップである：

• まず、Q = [3]（3親-1項目の指標です）。
• qをポップし、3を出力し、0,2,4をプッシュするので、q = [0、2、4]です。
• ここで、qを表示し、0を出力し、1を押します。したがって、q = [2,4,7]です。定義によってほとんど

、Qは正面からポップし、背面に加え、ノードはレベルによってレベルを処理されるからです。

ノードの数は複雑です。

Answer 2

次のレベルにプッシュされるノードの数を維持しながら、ツリー上でBFS（幅優先検索）を実行する必要があります。概要：0レベル：2：2、などあなたがループ内の一時リスト内の現在のレベルのノードを格納し、必要に応じて印刷することができ

q.push(root); nodesInCurrentLevel = 1; nodesInNextLevel = 0; currentLevelIndex = 1; 
while q is not empty do: 
    u = q.pop() 
    print currentLevelIndex and u 
    decrement nodesInCurrentLevel 
    for every child v of u do: 
    increment nodesInNextLevel 
    q.push(v) 
    if nodesInCurrentLevel is 0 do: 
    nodesInCurrentLevel = nodesInNextLevel 
    nodesInNextLevel = 0 
    increment currentLevelIndex 

はもちろん、これはレベル2に出力を印刷します。