Как распечатать все узлы дерева?

Question

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

У меня есть двоичное дерево, и я хочу напечатать все идентификаторы всех узлов в такойпорядок печати узлов одинаковой высоты: сначала печатается узел высотой 0, затем печатаются 2 узла высотой 1, затем печатаются 4 узла высотой 2 и т. д.Отцы и сыновья моего дерева связаны через указатели, узлы на одной высоте не связаны.Не у всех отцов есть 2 сына (у некоторых может быть только 1 сын).

Теоретически, как я могу напечатать это дерево?Это через рекурсию?

Answer 1

Вы должны сделать обход уровня порядка.Ваша проблема в точности здесь .

Answer 2

То, что вы ищете, вероятно, это поиск в ширину.Простой способ реализовать это - создать глобальную очередь и добавить к ней узлы для поиска по мере продвижения по дереву.При условии, что это конечное дерево, все будет готово, как только вы будете искать все узлы в очереди.