Construya un árbol binario a partir de una representación de array principal dada

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) 

  1. 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.
  2. Haga lo siguiente para cada índice i de la array dada 
    createNode (padre, i, creado)

createNode(padre[], yo, creado[]) 

  1. Si created[i] no es NULL, entonces el Node ya está creado. Así que regresa.
  2. Cree un nuevo Node con el valor ‘i’.
  3. Si parent[i] es -1 (i es root), haga que el Node creado sea root y regrese.
  4. Compruebe si se crea el padre de ‘i’ (Podemos comprobar esto comprobando si created[parent[i]] es NULL o no.
  5. Si no se crea el padre, recurra para el padre y cree el padre primero.
  6. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *