Предзаказ обхода N-арного дерева

Дано N-арное дерево. Задача состоит в том, чтобы написать программу для обхода заданного n-арного дерева в прямом порядке.

Примеры:

Input: 3-Array Tree  
                   1
                 / | 
                /  |   
              2    3     4
             /        / | 
            5    6    7  8  9
           /   / |  
          10  11 12 13

Output: 1 2 5 10 6 11 12 13 3 4 7 8 9

Input:  3-Array Tree
                   1
                 / | 
                /  |   
              2    3     4
             /        / | 
            5    6    7  8  9

Output: 1 2 5 6 3 4 7 8 9

Обход в прямом порядке для N-арного дерева аналогичен обходу в прямом порядке для двоичного дерева поиска или двоичного дерева с той лишь разницей, что все дочерние узлы родителя проходятся слева направо в последовательности.
Итеративный предварительный обход бинарного дерева.

Случаи, которые необходимо обрабатывать во время обхода: в этом итеративном алгоритме обхода с предварительным порядком учтены два случая:

1. Извлеките верхний узел из стека — Top из стека и вставьте его в список посещенных узлов.
2. Протолкните все дочерние узлы Top в стек справа налево, так как обход стека будет осуществляться в обратном порядке. В результате достигается правильный обход предварительного порядка.

Примечание . В приведенной ниже реализации Python «удаление очереди» используется для реализации стека вместо списка из-за его эффективных операций добавления и извлечения.

Ниже приведена реализация вышеуказанного подхода:

Анализ сложности:

• Временная сложность: O(N), где n — общее количество узлов в данном дереве.
• Вспомогательное пространство: O(h), где h — высота данного дерева.

Использование рекурсии:

Подход:

• Создайте вектор, который используется для хранения обхода предварительного порядка N-арного дерева.
• При посещении узла сохраните значение узла в созданном векторе и вызовите рекурсивную функцию для его дочерних элементов.

Ниже приведена реализация вышеуказанного алгоритма:

Анализ сложности:

Временная сложность: O(N), где n — общее количество узлов в данном дереве.
Вспомогательное пространство: O(h), где h — высота данного дерева, если учитывать вспомогательное пространство стека рекурсии.