Inserción en árbol n-ario en orden dado y recorrido de orden de nivel

Dado un conjunto de Nodes principales donde el índice de la array es el elemento secundario de cada valor de Node, la tarea es insertar los Nodes como un bosque (múltiples árboles combinados) donde cada elemento principal podría tener más de dos elementos secundarios. Después de insertar los Nodes, imprima cada nivel en un formato ordenado.

Ejemplo:

Entrada: arr[] = {5, 3, -1, 2, 5, 3} 
Salida:
-1 
2
3
1 5
Entrada: arr[] = {-1, -1, -1, -1, -1, 1}
Salida:
-1
0 1 2 3 4
5
 

A continuación se muestra la explicación de los ejemplos anteriores:

• Ejemplo 1:
  • En esta array dada, los elementos de la array serán el Node principal y el índice de la array serán los Nodes secundarios.
     
  • Inicialmente, configuramos la raíz del bosque en -1 como referencia.
  • Ahora, al atravesar la array, insertamos los Nodes en la estructura del bosque.
  • Inicialmente identificamos las raíces de los árboles individuales en el bosque y los insertamos en la raíz del bosque.
     
  • El índice de -1 es 2. Imprima -1 y agregue 2 como Node secundario.
  • Ahora busque en la lista el valor de la lista como 2. El índice 3 tiene el valor 2. Por lo tanto, 3 se convierte en el hijo de 2.
     
  • Ahora los índices que tienen valor 3 son 1 y 5. Entonces 1 y 5 son los hijos de 3.
    • La lista no contiene 1, así que ignore 1.
    • Los índices que contienen 5 son 0 y 4. Entonces se convierten en el niño.

        -1 ---------- root of the forest
       /
      2    ---------- level (0) 
     /
    3       ---------- level (1)
   / \
  1   5     ---------- level (2)
 /     \
0       4       ---------- level (3)

Note: level (0) contains roots of each tree

• Ejemplo 2:
  • En este caso, el árbol tendrá el formato

     -1        -------- root of the forest
  / | | | \
 0  1 2 3  4   -------- level (0)
    |
    5          -------- level (1)
Note: level (0) contains roots of each tree

Requisito previo: Recorrido de orden de niveles .
Enfoque: La idea es insertar recursivamente Nodes en un árbol. Sin embargo, la estructura del árbol es bastante diferente, por lo general, en el caso del árbol binario, habrá un máximo de dos Nodes secundarios para cualquier Node, pero en este caso, el Node raíz puede tener un número N de Nodes secundarios. ‘-1’ se considera como el root y el índice de la raíz se considerarán como Nodes secundarios.

Ejemplo:
si -1 está presente en el índice 3, entonces 3 será el Node secundario de -1.

     -1
    / 
   3

Inserte -1 en la cola. Ahora, si la raíz está vacía, entonces -1 Node se convierte en la raíz. Ahora quite y ponga en cola los Nodes secundarios de -1. Cree Nodes y agréguelos con la raíz. Continúe hasta que se hayan insertado todos los Nodes secundarios.

Level order Traversal:
     -1
   3   5
 2 4 6   9
The output for level order traversal will be: -1 3 5 2 4 6 9

Se sigue el mismo enfoque de encolado y desencolado para atravesar por orden de nivel.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Node creation
class Node
{
    public:
        int val;
         
        // Since n children are possible for a root.
        // A list created to store all the children.
        vector<Node *> child;
         
        // Constructor
        Node(int data) : val(data) {}
};
 
// Function to insert
void insert(Node *root, int parent, Node *node)
{
     
    // Root is empty then the node wil
    // l become the root
    if (!root)
    {
        root = node;
    }
    else
    {
        if (root->val == parent)
        {
        root->child.push_back(node);
        }
        else
        {
            // Recursive approach to
            // insert the child
            int l = root->child.size();
             
            for(int i = 0; i < l; i++)
            {
                if (root->child[i]->val == parent)
                    insert(root->child[i], parent, node);
                else
                    insert(root->child[i], parent, node);
            }
        }
    }
}
 
// Function to perform level order traversal
void levelorder(vector<Node *> &prev_level)
{
    vector<Node *> cur_level;
    vector<int> print_data;
    int l = prev_level.size();
     
    if (l == 0)
    {
        exit(0);
    }
     
    for(int i = 0; i < l; i++)
    {
        int prev_level_len = prev_level[i]->child.size();
         
        for(int j = 0; j < prev_level_len; j++)
        {
             
            // enqueue all the children
            // into cur_level list
            cur_level.push_back(prev_level[i]->child[j]);
             
            // Copies the entire cur_level
            // list into prev_level
            print_data.push_back(prev_level[i]->child[j]->val);
        }
    }
     
    prev_level = cur_level;
    for(auto i : print_data)
    {
        cout << i << " ";
    }
    levelorder(prev_level);
}
 
// Function that calls levelorder method to
// perform level order traversal
void levelorder_root(Node *root)
{
    if (root)
    {
        vector<Node *> level;
        level.push_back(root);
        printf("%d\n", root->val);
        levelorder(level);
    }
}
 
// Driver code
int main(int argc, char const *argv[])
{
     
    // -1 is the root element
    int arr[] = {-1, -1, -1, -1, -1};
    Node *root = new Node(-1);
    int l = sizeof(arr) / sizeof(int);
    vector<int> que;
     
    // Inserting root element to the queue
    que.push_back(-1);
     
    while (true)
    {
        vector<int> temp;
        for(int i = 0; i < l; i++)
        {
            if (find(que.begin(),
                     que.end(), arr[i]) != que.end())
            {
                // Insert elements into the tree
                insert(root, arr[i], new Node(i));
                temp.push_back(i);
            }
        }
     
        // Append child nodes into the queue
        // and insert the child
        que = temp;
         
        if (que.size() == 0)
        {
            break;
        }
    }
    levelorder_root(root);
}
 
// This code is contributed by sanjeev2552

# Python3 implementation of the approach
 
# Node creation
class Node:
 
    # Constructor
    def __init__(self, data): 
         
        self.val = data
         
        # Since n children are possible for a root.
        # A list created to store all the children.
        self.child = []  
 
 
# Function to insert
def insert(root, parent, node):
     
    # Root is empty then the node will become the root
    if root is None:
        root = node              
 
    else:
        if root.val == parent:
            root.child.append(node)            
        else:
 
            # Recursive approach to
            # insert the child
            l = len(root.child)
             
            for i in range(l):
                if root.child[i].val == parent:
                    insert(root.child[i], parent, node)
                else:
                    insert(root.child[i], parent, node)
 
# Function that calls levelorder method to
# perform level order traversal
def levelorder_root(root):
    if root:
        level = []
        level.append(root)
        print(root.val)
        levelorder(level)
 
# Function to perform level order traversal
def levelorder(prev_level):
 
    cur_level = []
    print_data = []
    l = len(prev_level)
 
    if l == 0:
        exit()
 
    for i in range(l):   
        prev_level_len = len(prev_level[i].child)
 
        for j in range(prev_level_len):
             
            # enqueue all the children
            # into cur_level list
            cur_level.append(
                   prev_level[i].child[j]) 
 
            # Copies the entire cur_level
            # list into prev_level
            print_data.append(
                   prev_level[i].child[j].val)
 
    prev_level = cur_level[:]                
    print(*print_data)
    levelorder(prev_level)
 
 
# Driver code
 
# -1 is the root element   
arr = [-1, -1, -1, -1, -1]
root = Node(-1)
l = len(arr)
que = []
 
# Inserting root element to the queue
que.append(-1)
 
while 1:
    temp = []
    for i in range(l):
        if arr[i] in que:
             
            # Insert elements into the tree
            insert(root, arr[i], Node(i))
            temp.append(i)
 
    # Append child nodes into the queue
    # and insert the child
    que = temp[:]                     
     
    if len(que)== 0:
        break
 
levelorder_root(root)   

-1
0 1 2 3 4

Complejidad de tiempo: O(N^2). 
Espacio Auxiliar : O(N).