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++
// 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
// 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
# 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#
// 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
Javascript
<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>
Producción
5 6 2 7 3 1 4
Complejidad de tiempo: O(n)
Complejidad espacial: O(n)
Publicación traducida automáticamente
Artículo escrito por code_freak y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA