Dado un árbol donde cada Node contiene un número variable de hijos, convierta el árbol en su espejo. El siguiente diagrama muestra un ejemplo.
C++
// C++ program to mirror an n-ary tree #include <bits/stdc++.h> using namespace std; // Represents a node of an n-ary tree struct Node { int key; vector<Node *>child; }; // Function to convert a tree to its mirror void mirrorTree(Node * root) { // Base case: Nothing to do if root is NULL if (root==NULL) return; // Number of children of root int n = root->child.size(); // If number of child is less than 2 i.e. // 0 or 1 we do not need to do anything if (n < 2) return; // Calling mirror function for each child for (int i=0; i<n; i++) mirrorTree(root->child[i]); // Reverse vector (variable sized array) of child // pointers reverse(root->child.begin(), root->child.end()); } // Utility function to create a new tree node Node *newNode(int key) { Node *temp = new Node; temp->key = key; return temp; } // Prints the n-ary tree level wise void printNodeLevelWise(Node * root) { if (root==NULL) return; // Create a queue and enqueue root to it queue<Node *>q; q.push(root); // Do level order traversal. Two loops are used // to make sure that different levels are printed // in different lines while (!q.empty()) { int n = q.size(); while (n>0) { // Dequeue an item from queue and print it Node * p = q.front(); q.pop(); cout << p->key << " "; // Enqueue all childrent of the dequeued item for (int i=0; i<p->child.size(); i++) q.push(p->child[i]); n--; } cout << endl; // Separator between levels } } // Driver program int main() { /* Let us create below tree * 10 * / / \ \ * 2 34 56 100 * | / | \ * 1 7 8 9 */ Node *root = newNode(10); (root->child).push_back(newNode(2)); (root->child).push_back(newNode(34)); (root->child).push_back(newNode(56)); (root->child).push_back(newNode(100)); (root->child[2]->child).push_back(newNode(1)); (root->child[3]->child).push_back(newNode(7)); (root->child[3]->child).push_back(newNode(8)); (root->child[3]->child).push_back(newNode(9)); cout << "Level order traversal Before Mirroring\n"; printNodeLevelWise(root); mirrorTree(root); cout << "\nLevel order traversal After Mirroring\n"; printNodeLevelWise(root); return 0; }
Python3
# Python program to mirror an n-ary tree # Represents a node of an n-ary tree class Node : # Utility function to create a new tree node def __init__(self ,key): self.key = key self.child = [] # Function to convert a tree to its mirror def mirrorTree(root): # Base Case : nothing to do if root is None if root is None: return # Number of children of root n = len(root.child) # If number of child is less than 2 i.e. # 0 or 1 we don't need to do anything if n <2 : return # Calling mirror function for each child for i in range(n): mirrorTree(root.child[i]); # Reverse variable sized array of child pointers root.child.reverse() # Prints the n-ary tree level wise def printNodeLevelWise(root): if root is None: return # create a queue and enqueue root to it queue = [] queue.append(root) # Do level order traversal. Two loops are used # to make sure that different levels are printed # in different lines while(len(queue) >0): n = len(queue) while(n > 0) : # Dequeue an item from queue and print it p = queue[0] queue.pop(0) print(p.key,end=" ") # Enqueue all children of the dequeued item for index, value in enumerate(p.child): queue.append(value) n -= 1 print() # Separator between levels # Driver Program """ Let us create below tree * 10 * / / \ \ * 2 34 56 100 * | / | \ * 1 7 8 9 """ root = Node(10) root.child.append(Node(2)) root.child.append(Node(34)) root.child.append(Node(56)) root.child.append(Node(100)) root.child[2].child.append(Node(1)) root.child[3].child.append(Node(7)) root.child[3].child.append(Node(8)) root.child[3].child.append(Node(9)) print ("Level order traversal Before Mirroring") printNodeLevelWise(root) mirrorTree(root) print ("\nLevel Order traversal After Mirroring") printNodeLevelWise(root)
Javascript
<script> // Javascript program to mirror an n-ary tree // Represents a node of an n-ary tree class Node { constructor() { this.key = 0; this.child = [] } }; // Function to convert a tree to its mirror function mirrorTree(root) { // Base case: Nothing to do if root is null if (root==null) return; // Number of children of root var n = root.child.length; // If number of child is less than 2 i.e. // 0 or 1 we do not need to do anything if (n < 2) return; // Calling mirror function for each child for(var i=0; i<n; i++) mirrorTree(root.child[i]); // Reverse vector (variable sized array) of child // pointers root.child.reverse(); } // Utility function to create a new tree node function newNode(key) { var temp = new Node; temp.key = key; return temp; } // Prints the n-ary tree level wise function printNodeLevelWise(root) { if (root==null) return; // Create a queue and enqueue root to it var q = []; q.push(root); // Do level order traversal. Two loops are used // to make sure that different levels are printed // in different lines while (q.length!=0) { var n = q.length; while (n>0) { // Dequeue an item from queue and print it var p = q[0]; q.shift(); document.write( p.key + " "); // Enqueue all childrent of the dequeued item for(var i=0; i<p.child.length; i++) q.push(p.child[i]); n--; } document.write("<br>") // Separator between levels } } // Driver program /* Let us create below tree * 10 * / / \ \ * 2 34 56 100 * | / | \ * 1 7 8 9 */ var root = newNode(10); (root.child).push(newNode(2)); (root.child).push(newNode(34)); (root.child).push(newNode(56)); (root.child).push(newNode(100)); (root.child[2].child).push(newNode(1)); (root.child[3].child).push(newNode(7)); (root.child[3].child).push(newNode(8)); (root.child[3].child).push(newNode(9)); document.write("Level order traversal Before Mirroring<br>"); printNodeLevelWise(root); mirrorTree(root); document.write("<br>Level order traversal After Mirroring<br>"); printNodeLevelWise(root); // This code is contributed by rrrtnx. </script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA