Recorrido iterativo de orden previo de un árbol N-ario

Dado un árbol K-ario. La tarea es escribir un programa iterativo para realizar el recorrido en orden previo del árbol n-ario dado.

Ejemplos:  

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

El recorrido de preorden de un árbol N-ario es similar al recorrido de preorden de un árbol de búsqueda binario o un árbol binario con la única diferencia de que todos los Nodes secundarios de un padre se recorren de izquierda a derecha en una secuencia.
Recorrido iterativo de orden previo del árbol binario .

Casos a manejar durante el recorrido: Se han atendido dos casos en este algoritmo iterativo de recorrido de preorden: 

1. Extraiga el Node superior de la pila: colóquelo en la parte superior de la pila e insértelo en la lista de Nodes visitados.
2. Empuje todos los Nodes secundarios de Top en la pila de derecha a izquierda, ya que el recorrido desde la pila se realizará en orden inverso. Como resultado, se logra un recorrido de orden previo correcto.

Nota : En la implementación de Python a continuación, se usa una «eliminación de la cola» para implementar la pila en lugar de una lista debido a sus operaciones de adición y extracción eficientes.

A continuación se muestra la implementación del enfoque anterior:  

// C++ program for Iterative Preorder
// Traversal of N-ary Tree.
// Preorder{ Root, print children
// from left to right.
#include <bits/stdc++.h>
using namespace std;
 
// Node Structure of K-ary Tree
class NewNode {
public:
    int key;
 
    // All children are stored in a list
    vector<NewNode*> child;
    NewNode(int val)
        : key(val)
    {
    }
};
 
// Utility function to print the
// preorder of the given K-Ary Tree
void preorderTraversal(NewNode* root)
{
    stack<NewNode*> Stack;
 
    // 'Preorder'-> contains all the
    // visited nodes
    vector<int> Preorder;
 
    Stack.push(root);
 
    while (!Stack.empty()) {
        NewNode* temp = Stack.top();
        Stack.pop();
        // store the key in preorder vector(visited list)
        Preorder.push_back(temp->key);
        // Push all of the child nodes of temp into
        // the stack from right to left.
        for (int i = temp->child.size() - 1; i >= 0; i--) {
            Stack.push(temp->child[i]);
        }
    }
    for (auto i : Preorder) {
        cout << i << " ";
    }
    cout << endl;
}
 
// Driver Code
int main()
{
 
    // input nodes
    /*
             1
          /  |  \
         /   |   \
        2    3    4
       / \      / | \
      /   \    7  8  9
     5     6
    /    / | \
   10   11 12 13
    */
 
    NewNode* root = new NewNode(1);
    root->child.push_back(new NewNode(2));
    root->child.push_back(new NewNode(3));
    root->child.push_back(new NewNode(4));
 
    root->child[0]->child.push_back(new NewNode(5));
    root->child[0]->child[0]->child.push_back(
        new NewNode(10));
    root->child[0]->child.push_back(new NewNode(6));
    root->child[0]->child[1]->child.push_back(
        new NewNode(11));
    root->child[0]->child[1]->child.push_back(
        new NewNode(12));
    root->child[0]->child[1]->child.push_back(
        new NewNode(13));
    root->child[2]->child.push_back(new NewNode(7));
    root->child[2]->child.push_back(new NewNode(8));
    root->child[2]->child.push_back(new NewNode(9));
 
    preorderTraversal(root);
}
 
// This code is contributed by sarangiswastika5

# Python3 program for Iterative Preorder
# Traversal of N-ary Tree.
# Preorder: Root, print children
# from left to right.
 
from collections import deque
 
# Node Structure of K-ary Tree
class NewNode():
 
    def __init__(self, val):
        self.key = val
        # all children are stored in a list
        self.child =[]
 
 
# Utility function to print the
# preorder of the given K-Ary Tree
def preorderTraversal(root):
 
    Stack = deque([])
    # 'Preorder'-> contains all the
    # visited nodes.
    Preorder =[]
    Preorder.append(root.key)
    Stack.append(root)
    while len(Stack)>0:
        # 'Flag' checks whether all the child
        # nodes have been visited.
        flag = 0
        # CASE 1- If Top of the stack is a leaf
        # node then remove it from the stack:
        if len((Stack[len(Stack)-1]).child)== 0:
            X = Stack.pop()
            # CASE 2- If Top of the stack is
            # Parent with children:
        else:
            Par = Stack[len(Stack)-1]
        # a)As soon as an unvisited child is
        # found(left to right sequence),
        # Push it to Stack and Store it in
        # Auxiliary List(Marked Visited)
        # Start Again from Case-1, to explore
        # this newly visited child
        for i in range(0, len(Par.child)):
            if Par.child[i].key not in Preorder:
                flag = 1
                Stack.append(Par.child[i])
                Preorder.append(Par.child[i].key)
                break;
                # b)If all Child nodes from left to right
                # of a Parent have been visited
                # then remove the parent from the stack.
        if flag == 0:
            Stack.pop()
    print(Preorder)
 
# Execution Start From here
if __name__=='__main__':
# input nodes
                '''
                 
                  1
               /  |  \
              /   |   \
             2    3    4
            / \      / | \
           /   \    7  8  9
          5     6   
         /    / | \
        10   11 12 13
         
                '''
                 
root = NewNode(1)
root.child.append(NewNode(2))
root.child.append(NewNode(3))
root.child.append(NewNode(4))
root.child[0].child.append(NewNode(5))
root.child[0].child[0].child.append(NewNode(10))
root.child[0].child.append(NewNode(6))
root.child[0].child[1].child.append(NewNode(11))
root.child[0].child[1].child.append(NewNode(12))
root.child[0].child[1].child.append(NewNode(13))
root.child[2].child.append(NewNode(7))
root.child[2].child.append(NewNode(8))
root.child[2].child.append(NewNode(9))
     
preorderTraversal(root)

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

Complejidad de tiempo: O(N), donde n es el número total de Nodes en el árbol dado.
Espacio Auxiliar: O(h), Donde h es la altura del árbol dado