Прохождение уровня по уровню родительского массива n-арного дерева?

Question

Учитывая, п-ичных дерево, хранящуюся в родительском массиве, с детьми, хранящиеся в массив указателей на массивы, где первое значение является количество детей:

(childArray [2] [0] показывает, что узел 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}}; 

производит дерево, которое выглядит следующим образом:

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

Использование очереди, как могу ли я выводить уровень дерева по уровню следующим образом:

Уровень 1: 3

Уровень 2: 0, 2, 4

Уровень 3: 1, 5, 6

Уровни 1 и 2 просты, так как уровень 1 только корень и уровень 2 - это только его дети, но после этого я не могу понять, как получить его, чтобы получить детей от детей.

Answer 1

Одним из способов сделать это будет использование структуры данных queue.

Начните с очереди q и поместите в индекс (уникальный) элемент, родительский которого равен -1. Теперь на каждом шаге, пока д пуст,

• Выполните v < - поп (д) (выскакивают голова)
• Распечатайте v
• Для каждого ребенка ш из об, сделать толчок (д, v) (толкание ВЗ хвост)

Например, вот первые шаги для Вашего случая:

• Первоначально д = [3] (3 является индекс элемента, чей родитель равен -1).
• Мы выталкиваем q, распечатываем 3 и нажимаем 0, 2 и 4, поэтому q = [0, 2, 4].
• Теперь мы выталкиваем q, распечатываем 0 и нажимаем 1, поэтому q = [2, 4, 1].

Почти по определению, так как д выталкивается из передней и добавляют к задней части, узлы будут обрабатываться уровень за уровнем.

Сложность линейна по числу узлов.

Answer 2

Вам нужно будет выполнить BFS (Поиск по ширине первого) на дереве, сохраняя при этом количество узлов, находящихся на следующем уровне.Outline:

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: 0 Уровень 2: 2, и т.д. Вы можете сохранить текущие узлы уровня во временном списке внутри цикла и печати в зависимости от обстоятельств.