Recorrido en orden de un árbol N-ario

Dado un árbol N-ario que contiene, la tarea es imprimir el recorrido en orden del árbol.

Ejemplos: 

Entrada: N = 3 
 

Salida: 5 6 2 7 3 1 4
Entrada: N = 3 
 

Salida: 2 5 3 1 4 6 

Enfoque: El recorrido en orden de un árbol N-ario se define como visitar todos los hijos excepto el último, luego la raíz y finalmente el último hijo recursivamente. 

• Visita recursivamente al primer hijo.
• Visita recursivamente al segundo hijo.
• …..
• Visita recursivamente al penúltimo hijo.
• Imprime los datos en el Node.
• Visita recursivamente al último niño.
• Repita los pasos anteriores hasta que se visiten todos los Nodes.

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

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
// Class for the node of the tree
struct Node
{
    int data;
 
    // List of children
    struct Node **children;
     
    int length;
     
    Node()
    {
        length = 0;
        data = 0;
    }
 
    Node(int n, int data_)
    {
        children = new Node*();
        length = n;
        data = data_;
    }
};
 
// Function to print the inorder traversal
// of the n-ary tree
void inorder(Node *node)
{
    if (node == NULL)
        return;
 
    // Total children count
    int total = node->length;
     
    // All the children except the last
    for (int i = 0; i < total - 1; i++)
        inorder(node->children[i]);
 
    // Print the current node's data
    cout<< node->data << " ";
 
    // Last child
    inorder(node->children[total - 1]);
}
 
// Driver code
int main()
{
 
    /* Create the following tree
          1
        / | \
        2 3 4
        / | \
        5 6 7
    */
    int n = 3;
    Node* root = new Node(n, 1);
    root->children[0] = new Node(n, 2);
    root->children[1] = new Node(n, 3);
    root->children[2] = new Node(n, 4);
    root->children[0]->children[0] = new Node(n, 5);
    root->children[0]->children[1] = new Node(n, 6);
    root->children[0]->children[2] = new Node(n, 7);
 
    inorder(root);
    return 0;
}
 
// This code is Contributed by Arnab Kundu

// Java implementation of the approach
class GFG {
 
    // Class for the node of the tree
    static class Node {
        int data;
 
        // List of children
        Node children[];
 
        Node(int n, int data)
        {
            children = new Node[n];
            this.data = data;
        }
    }
 
    // Function to print the inorder traversal
    // of the n-ary tree
    static void inorder(Node node)
    {
        if (node == null)
            return;
 
        // Total children count
        int total = node.children.length;
        // All the children except the last
        for (int i = 0; i < total - 1; i++)
            inorder(node.children[i]);
 
        // Print the current node's data
        System.out.print("" + node.data + " ");
 
        // Last child
        inorder(node.children[total - 1]);
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        /* Create the following tree
                   1
                /  |  \
               2   3   4
             / | \
            5  6  7
        */
        int n = 3;
        Node root = new Node(n, 1);
        root.children[0] = new Node(n, 2);
        root.children[1] = new Node(n, 3);
        root.children[2] = new Node(n, 4);
        root.children[0].children[0] = new Node(n, 5);
        root.children[0].children[1] = new Node(n, 6);
        root.children[0].children[2] = new Node(n, 7);
 
        inorder(root);
    }
}

# Python3 implementation of the approach
class GFG:
     
    # Class for the node of the tree
    class Node:
        def __init__(self,n,data):
            # List of children
            self.children = [None]*n
            self.data = data
     
    # Function to print the inorder traversal
    # of the n-ary tree
    def inorder(self, node):
        if node == None:
            return
         
        # Total children count
        total = len(node.children)
         
        # All the children except the last
        for i in range(total-1):
            self.inorder(node.children[i])
         
        # Print the current node's data
        print(node.data,end=" ")
         
        # Last child
        self.inorder(node.children[total-1])
     
    # Driver code
    def main(self):
        # Create the following tree 
        #          1
        #       /  |  \
        #      2   3   4
        #    / | \
        #   5  6  7
         
        n = 3
        root = self.Node(n, 1)
        root.children[0] = self.Node(n, 2)
        root.children[1] = self.Node(n, 3)
        root.children[2] = self.Node(n, 4)
        root.children[0].children[0] = self.Node(n, 5)
        root.children[0].children[1] = self.Node(n, 6)
        root.children[0].children[2] = self.Node(n, 7)
         
        self.inorder(root)
         
ob = GFG() # Create class object
ob.main() # Call main function
 
# This code is contributed by Shivam Singh

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Class for the node of the tree
    public class Node
    {
        public int data;
 
        // List of children
        public Node []children;
 
        public Node(int n, int data)
        {
            children = new Node[n];
            this.data = data;
        }
    }
 
    // Function to print the inorder traversal
    // of the n-ary tree
    static void inorder(Node node)
    {
        if (node == null)
            return;
 
        // Total children count
        int total = node.children.Length;
         
        // All the children except the last
        for (int i = 0; i < total - 1; i++)
            inorder(node.children[i]);
 
        // Print the current node's data
        Console.Write("" + node.data + " ");
 
        // Last child
        inorder(node.children[total - 1]);
    }
 
    // Driver code
    public static void Main()
    {
 
        /* Create the following tree
                1
                / | \
            2 3 4
            / | \
            5 6 7
        */
        int n = 3;
        Node root = new Node(n, 1);
        root.children[0] = new Node(n, 2);
        root.children[1] = new Node(n, 3);
        root.children[2] = new Node(n, 4);
        root.children[0].children[0] = new Node(n, 5);
        root.children[0].children[1] = new Node(n, 6);
        root.children[0].children[2] = new Node(n, 7);
 
        inorder(root);
    }
}
 
// This code is contributed by AnkitRai01

<script>
  
// JavaScript implementation of the approach
// Class for the node of the tree
class Node
{
 
    constructor(n, data)
    {
        this.data = data;
        this.children = Array(n);
    }
}
// Function to print the inorder traversal
// of the n-ary tree
function inorder(node)
{
    if (node == null)
        return;
    // Total children count
    var total = node.children.length;
     
    // All the children except the last
    for (var i = 0; i < total - 1; i++)
        inorder(node.children[i]);
    // Print the current node's data
    document.write("" + node.data + " ");
    // Last child
    inorder(node.children[total - 1]);
}
 
// Driver code
/* Create the following tree
        1
        / | \
    2 3 4
    / | \
    5 6 7
*/
var n = 3;
var root = new Node(n, 1);
root.children[0] = new Node(n, 2);
root.children[1] = new Node(n, 3);
root.children[2] = new Node(n, 4);
root.children[0].children[0] = new Node(n, 5);
root.children[0].children[1] = new Node(n, 6);
root.children[0].children[2] = new Node(n, 7);
inorder(root);
 
</script>

5 6 2 7 3 1 4 

Complejidad de tiempo:   O(n)

Complejidad espacial:   O(n)