Dada una array que representa un árbol de tal manera que los índices de la array son valores en los Nodes del árbol y los valores de la array dan el Node principal de ese índice (o Node) en particular. El valor del índice del Node raíz siempre sería -1 ya que no hay un padre para la raíz. Construya la representación vinculada estándar de un árbol binario dado a partir de esta representación dada.
Ejemplos:
Input: parent[] = {1, 5, 5, 2, 2, -1, 3} Output: root of below tree 5 / \ 1 2 / / \ 0 3 4 / 6 Explanation: Index of -1 is 5. So 5 is root. 5 is present at indexes 1 and 2. So 1 and 2 are children of 5. 1 is present at index 0, so 0 is child of 1. 2 is present at indexes 3 and 4. So 3 and 4 are children of 2. 3 is present at index 6, so 6 is child of 3. Input: parent[] = {-1, 0, 0, 1, 1, 3, 5}; Output: root of below tree 0 / \ 1 2 / \ 3 4 / 5 / 6
La complejidad de tiempo esperada es O(n) donde n es el número de elementos en una array dada.
Recomendamos encarecidamente minimizar su navegador y probarlo usted mismo primero.
Una solución simple para construir recursivamente buscando primero la raíz actual, luego recurriendo a los índices encontrados (puede haber como máximo dos índices) y convirtiéndolos en subárboles izquierdo y derecho de la raíz. Esta solución toma O(n 2 ) ya que tenemos que buscar linealmente cada Node.
Una solución eficiente puede resolver el problema anterior en tiempo O(n). La idea es utilizar espacio extra. Se utiliza una array created[0..n-1] para realizar un seguimiento de los Nodes creados.
crearÁrbol(padre[], n)
- Cree una array de punteros, digamos created[0..n-1]. El valor de created[i] es NULL si no se crea el Node para el índice i, de lo contrario, el valor es un puntero al Node creado.
- Haga lo siguiente para cada índice i de la array dada
createNode (padre, i, creado)
createNode(padre[], yo, creado[])
- Si created[i] no es NULL, entonces el Node ya está creado. Así que regresa.
- Cree un nuevo Node con el valor ‘i’.
- Si parent[i] es -1 (i es root), haga que el Node creado sea root y regrese.
- Compruebe si se crea el padre de ‘i’ (Podemos comprobar esto comprobando si created[parent[i]] es NULL o no.
- Si no se crea el padre, recurra para el padre y cree el padre primero.
- Deje que el puntero a padre sea p. Si p->left es NULL, entonces crea el nuevo Node como hijo izquierdo. De lo contrario, haga que el nuevo Node sea el hijo derecho del padre.
A continuación se muestra la implementación en C++ de la idea anterior.
C++14
// C++ program to construct a Binary Tree from parent array #include<bits/stdc++.h> using namespace std; // A tree node struct Node { int key; struct Node *left, *right; }; // Utility function to create new Node Node *newNode(int key) { Node *temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp); } // Creates a node with key as 'i'. If i is root, then it changes // root. If parent of i is not created, then it creates parent first void createNode(int parent[], int i, Node *created[], Node **root) { // If this node is already created if (created[i] != NULL) return; // Create a new node and set created[i] created[i] = newNode(i); // If 'i' is root, change root pointer and return if (parent[i] == -1) { *root = created[i]; return; } // If parent is not created, then create parent first if (created[parent[i]] == NULL) createNode(parent, parent[i], created, root); // Find parent pointer Node *p = created[parent[i]]; // If this is first child of parent if (p->left == NULL) p->left = created[i]; else // If second child p->right = created[i]; } // Creates tree from parent[0..n-1] and returns root of the created tree Node *createTree(int parent[], int n) { // Create an array created[] to keep track // of created nodes, initialize all entries // as NULL Node *created[n]; for (int i=0; i<n; i++) created[i] = NULL; Node *root = NULL; for (int i=0; i<n; i++) createNode(parent, i, created, &root); return root; } //For adding new line in a program inline void newLine(){ cout << "\n"; } // Utility function to do inorder traversal void inorder(Node *root) { if (root != NULL) { inorder(root->left); cout << root->key << " "; inorder(root->right); } } // Driver method int main() { int parent[] = {-1, 0, 0, 1, 1, 3, 5}; int n = sizeof parent / sizeof parent[0]; Node *root = createTree(parent, n); cout << "Inorder Traversal of constructed tree\n"; inorder(root); newLine(); }
Java
// Java program to construct a binary tree from parent array // A binary tree node class Node { int key; Node left, right; public Node(int key) { this.key = key; left = right = null; } } class BinaryTree { Node root; // Creates a node with key as 'i'. If i is root, then it changes // root. If parent of i is not created, then it creates parent first void createNode(int parent[], int i, Node created[]) { // If this node is already created if (created[i] != null) return; // Create a new node and set created[i] created[i] = new Node(i); // If 'i' is root, change root pointer and return if (parent[i] == -1) { root = created[i]; return; } // If parent is not created, then create parent first if (created[parent[i]] == null) createNode(parent, parent[i], created); // Find parent pointer Node p = created[parent[i]]; // If this is first child of parent if (p.left == null) p.left = created[i]; else // If second child p.right = created[i]; } /* Creates tree from parent[0..n-1] and returns root of the created tree */ Node createTree(int parent[], int n) { // Create an array created[] to keep track // of created nodes, initialize all entries // as NULL Node[] created = new Node[n]; for (int i = 0; i < n; i++) created[i] = null; for (int i = 0; i < n; i++) createNode(parent, i, created); return root; } //For adding new line in a program void newLine() { System.out.println(""); } // Utility function to do inorder traversal void inorder(Node node) { if (node != null) { inorder(node.left); System.out.print(node.key + " "); inorder(node.right); } } // Driver method public static void main(String[] args) { BinaryTree tree = new BinaryTree(); int parent[] = new int[]{-1, 0, 0, 1, 1, 3, 5}; int n = parent.length; Node node = tree.createTree(parent, n); System.out.println("Inorder traversal of constructed tree "); tree.inorder(node); tree.newLine(); } } // This code has been contributed by Mayank Jaiswal(mayank_24)
Python3
# Python implementation to construct a Binary Tree from # parent array # A node structure class Node: # A utility function to create a new node def __init__(self, key): self.key = key self.left = None self.right = None """ Creates a node with key as 'i'. If i is root,then it changes root. If parent of i is not created, then it creates parent first """ def createNode(parent, i, created, root): # If this node is already created if created[i] is not None: return # Create a new node and set created[i] created[i] = Node(i) # If 'i' is root, change root pointer and return if parent[i] == -1: root[0] = created[i] # root[0] denotes root of the tree return # If parent is not created, then create parent first if created[parent[i]] is None: createNode(parent, parent[i], created, root ) # Find parent pointer p = created[parent[i]] # If this is first child of parent if p.left is None: p.left = created[i] # If second child else: p.right = created[i] # Creates tree from parent[0..n-1] and returns root of the # created tree def createTree(parent): n = len(parent) # Create and array created[] to keep track # of created nodes, initialize all entries as None created = [None for i in range(n+1)] root = [None] for i in range(n): createNode(parent, i, created, root) return root[0] #Inorder traversal of tree def inorder(root): if root is not None: inorder(root.left) print (root.key,end=" ") inorder(root.right) # Driver Method parent = [-1, 0, 0, 1, 1, 3, 5] root = createTree(parent) print ("Inorder Traversal of constructed tree") inorder(root) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// C# program to construct a binary // tree from parent array using System; // A binary tree node public class Node { public int key; public Node left, right; public Node(int key) { this.key = key; left = right = null; } } class GFG { public Node root; // Creates a node with key as 'i'. // If i is root, then it changes // root. If parent of i is not created, // then it creates parent first public virtual void createNode(int[] parent, int i, Node[] created) { // If this node is already created if (created[i] != null) { return; } // Create a new node and set created[i] created[i] = new Node(i); // If 'i' is root, change root // pointer and return if (parent[i] == -1) { root = created[i]; return; } // If parent is not created, then // create parent first if (created[parent[i]] == null) { createNode(parent, parent[i], created); } // Find parent pointer Node p = created[parent[i]]; // If this is first child of parent if (p.left == null) { p.left = created[i]; } else // If second child { p.right = created[i]; } } /* Creates tree from parent[0..n-1] and returns root of the created tree */ public virtual Node createTree(int[] parent, int n) { // Create an array created[] to // keep track of created nodes, // initialize all entries as NULL Node[] created = new Node[n]; for (int i = 0; i < n; i++) { created[i] = null; } for (int i = 0; i < n; i++) { createNode(parent, i, created); } return root; } // For adding new line in a program public virtual void newLine() { Console.WriteLine(""); } // Utility function to do inorder traversal public virtual void inorder(Node node) { if (node != null) { inorder(node.left); Console.Write(node.key + " "); inorder(node.right); } } // Driver Code public static void Main(string[] args) { GFG tree = new GFG(); int[] parent = new int[]{-1, 0, 0, 1, 1, 3, 5}; int n = parent.Length; Node node = tree.createTree(parent, n); Console.WriteLine("Inorder traversal of " + "constructed tree "); tree.inorder(node); tree.newLine(); } } // This code is contributed by Shrikant13
Javascript
<script> // Javascript program to construct a binary // tree from parent array // A binary tree node class Node { constructor(key) { this.key = key; this.left = null; this.right = null; } } var root = null; // Creates a node with key as 'i'. // If i is root, then it changes // root. If parent of i is not created, // then it creates parent first function createNode(parent, i, created) { // If this node is already created if (created[i] != null) { return; } // Create a new node and set created[i] created[i] = new Node(i); // If 'i' is root, change root // pointer and return if (parent[i] == -1) { root = created[i]; return; } // If parent is not created, then // create parent first if (created[parent[i]] == null) { createNode(parent, parent[i], created); } // Find parent pointer var p = created[parent[i]]; // If this is first child of parent if (p.left == null) { p.left = created[i]; } else // If second child { p.right = created[i]; } } /* Creates tree from parent[0..n-1] and returns root of the created tree */ function createTree(parent, n) { // Create an array created[] to // keep track of created nodes, // initialize all entries as NULL var created = Array(n); for (var i = 0; i < n; i++) { created[i] = null; } for (var i = 0; i < n; i++) { createNode(parent, i, created); } return root; } // For adding new line in a program function newLine() { document.write(""); } // Utility function to do inorder traversal function inorder(node) { if (node != null) { inorder(node.left); document.write(node.key + " "); inorder(node.right); } } // Driver Code var parent = [-1, 0, 0, 1, 1, 3, 5]; var n = parent.length; var node = createTree(parent, n); document.write("Inorder traversal of " + "constructed tree<br>"); inorder(node); newLine(); // This code is contributed by rrrtnx. </script>
Inorder Traversal of constructed tree 6 5 3 1 4 0 2
Otra solución eficiente:
La idea es crear primero todos los n nuevos Nodes de árbol, cada uno con valores de 0 a n – 1 , donde n es el tamaño de la array principal , y almacenarlos en cualquier estructura de datos como mapa, array, etc. para realizar un seguimiento de qué Node es creado por qué valor. Luego recorra la array principal dada y construya el árbol estableciendo la relación padre-hijo.
A continuación se muestra la implementación en C++ de la idea anterior.
C++
// C++ program to construct a Binary Tree from parent array #include <bits/stdc++.h> using namespace std; struct Node { int data; struct Node* left = NULL; struct Node* right = NULL; Node() {} Node(int x) { data = x; } }; // Function to construct binary tree from parent array. Node* createTree(int parent[], int n) { // Create an array to store the reference // of all newly created nodes corresponding // to node value vector<Node*> ref; // This root represent the root of the // newly constructed tree Node* root = new Node(); // Create n new tree nodes, each having // a value from 0 to n-1, and store them // in ref for (int i = 0; i < n; i++) { Node* temp = new Node(i); ref.push_back(temp); } // Traverse the parent array and build the tree for (int i = 0; i < n; i++) { // If the parent is -1, set the root // to the current node having // the value i which is stored in ref[i] if (parent[i] == -1) { root = ref[i]; } else { // Check if the parent's left child // is NULL then map the left child // to its parent. if (ref[parent[i]]->left == NULL) ref[parent[i]]->left = ref[i]; else ref[parent[i]]->right = ref[i]; } } // Return the root of the newly constructed tree return root; } // Function for inorder traversal void inorder(Node* root) { if (root != NULL) { inorder(root->left); cout << root->data << " "; inorder(root->right); } } // Driver code int main() { int parent[] = { -1, 0, 0, 1, 1, 3, 5 }; int n = sizeof parent / sizeof parent[0]; Node* root = createTree(parent, n); cout << "Inorder Traversal of constructed tree\n"; inorder(root); return 0; }
Inorder Traversal of constructed tree 6 5 3 1 4 0 2
Complejidad de tiempo: O(n), donde n es el tamaño de la array principal
Espacio auxiliar: O(n)
Problema similar: encuentre la altura del árbol binario representado por la array principal.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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