Level für Level Traversal des Elternarrays n-ary Baum?

Question

einen n-äre Baum gespeichert in einer Eltern-Arrays, wobei die in einem Array von Zeigern gespeichert Kinder Arrays, wobei der erste Wert die Anzahl von Kindern ist:

(childArray [2] [0] zeigt, dass der Knoten 2 hat 2 Kinder, childArray [2] [1] zeigt, dass ihr erstes Kind 5 usw.)

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

erzeugt einen Baum, der wie folgt aussieht:

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

eine Warteschlange verwenden, wie kann ich den Baum Level für Level wie folgt ausgeben:

Stufe 1: 3

Stufe 2: 0, 2, 4

Stufe 3: 1, 5, 6

Stufen 1 und 2 leicht, weil die Ebene 1 nur die Wurzel und Ebene 2 ist nur seine Kinder, aber danach kann ich nicht herausfinden, wie man es bekommt, um die Kinder der Kinder zu bekommen.

Answer 1

Eine Möglichkeit, dies zu tun wäre eine queue Datenstruktur zu verwenden.

Beginnen Sie mit einigen Queue q, und platzieren Sie im Index des (eindeutigen) Elements, dessen Eltern -1 ist. Nun, bei jedem Schritt, bis q leer ist,

• Perform v < - pop (q) (popping der Kopf)
• Druck aus v
• Für jedes Kind w von v, tun push (q, v) (Pushing ot der Schwanz)

Zum Beispiel sind hier die ersten Schritte für Ihren Fall:

• , zunächst q = [3] (3 ist der Index des Eintrags, deren Mutter -1).
• Wir pop q, drucken Sie 3, und drücken Sie 0, 2 und 4, also q = [0, 2, 4].
• Jetzt knallen wir q, drucken 0, und drücken 1, also q = [2, 4, 1].

fast definitions, da q von vorne aufgetaucht ist, und zu der Rückseite werden die Knoten Ebene für Ebene verarbeitet werden.

Die Komplexität ist linear in der Anzahl der Knoten.

Answer 2

Sie müssen eine BFS (Breathth First Search) auf dem Baum ausführen, während die Anzahl der Knoten in der nächsten Ebene beibehalten wird.Outline: 0 Level: 2: 2 können, etc. Sie speichern aktuelle Ebene Knoten in einer temporären Liste innerhalb der Schleife und drucken gegebenenfalls

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 

Natürlich ist dies die Ausgabe als Stufe 2 drucken.