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>
Producción
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;
}
Producción
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