Reemplace cada Node con profundidad en N-ary Generic Tree

Dada una array arr[] que representa un árbol genérico (N-ario) . La tarea es reemplazar los datos del Node con la profundidad (nivel) del Node. Suponga que el nivel de la raíz es 0.
 

Representación de array : el árbol N-ario se serializa en la array arr[] utilizando un recorrido de orden de nivel como se describe a continuación: 
 

  • La entrada se proporciona como un recorrido de orden de nivel de N-ary Tree .
  • El primer elemento de la array arr[] es el Node raíz.
  • Luego, seguido de un número N, que denota el número de hijos del Node anterior. El valor cero indica un Node nulo.

Ejemplos: 
 

Entrada: arr[] = { 10, 3, 20, 30, 40, 2, 40, 50, 0, 0, 0, 0 } 
A continuación se muestra el árbol N-ario del recorrido de orden de nivel de array anterior: 
 

Salida: 
A continuación se muestra la representación de la salida anterior: 
 

Entrada: arr[] = {1, 3, 2, 3, 4, 2, 5, 6, 0, 0, 2, 8, 9} 
A continuación se muestra el árbol N-ario del recorrido de orden de nivel de array anterior: 
 

Salida: 
A continuación se muestra la representación de la salida anterior: 
 

 

Acercarse: 
 

  • Atraviesa el árbol comenzando desde la raíz.
  • Mientras atraviesa, pase la profundidad del Node como parámetro.
  • Realice un seguimiento de la profundidad pasándola como 0 para raíz y (1 + nivel actual) para niños.

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

CPP

// C++ program to implement node with
// it's depth value
#include <bits/stdc++.h>
using namespace std;
 
// Treenode class using template
template <typename T>
class TreeNode {
public:
    // To store node value
    T data;
 
    // Pointer to TreeNode to store
    // the child node
    vector<TreeNode<T>*> children;
 
    // Constructor to assign data
    // to node
    TreeNode(T data)
    {
        this->data = data;
    }
 
    // Destructors to delete a node
    ~TreeNode()
    {
        for (int i = 0;
             i < children.size(); i++) {
            delete children[i];
        }
    }
};
 
// Function to take input level wise
// i.e., in level order traversal
TreeNode<int>* takeInputLevelWise(int arr[])
{
    int idx = 1;
 
    // Input root
    int rootData = arr[0];
 
    // Initialize tree with a root node
    TreeNode<int>* root
        = new TreeNode<int>(rootData);
 
    // Initialise queue for appending
    // node as a child of parent in
    // N-ary tree
    queue<TreeNode<int>*> pendingNodes;
 
    // Push the root node in queue
    pendingNodes.push(root);
 
    // While queue is not empty append
    // child to the root
    while (pendingNodes.size() != 0) {
 
        // Take the first node
        TreeNode<int>* front
            = pendingNodes.front();
        pendingNodes.pop();
 
        // Input number of child
        int numChild = arr[idx];
        idx++;
 
        for (int i = 0; i < numChild; i++) {
 
            int childData = arr[idx];
            idx++;
 
            // Make child Node
            TreeNode<int>* child
                = new TreeNode<int>(childData);
 
            // Append child node to
            // it's parent
            front->children.push_back(child);
            pendingNodes.push(child);
        }
    }
    return root;
}
 
// Function to print each node data
// in level order
void printLevelATNewLine(TreeNode<int>* root)
{
    queue<TreeNode<int>*> q;
    q.push(root);
    q.push(NULL);
    while (!q.empty()) {
 
        TreeNode<int>* first = q.front();
        q.pop();
 
        if (first == NULL) {
            if (q.empty()) {
                break;
            }
            cout << endl;
            q.push(NULL);
            continue;
        }
 
        cout << first->data << " ";
 
        for (int i = 0;
             i < first->children.size(); i++) {
            q.push(first->children[i]);
        }
    }
}
 
// Helper function to replace the
// node data with their level value
void helper(TreeNode<int>* root,
            int depth)
{
 
    // Replace the node data with
    // it's depth
    root->data = depth;
    for (int i = 0;
         i < root->children.size(); i++) {
 
        helper(root->children[i], depth + 1);
    }
}
 
// Function to replace with depth
void replaceWithDepthValue(TreeNode<int>* root)
{
    helper(root, 0);
}
 
// Driver Code
int main()
{
 
    // Given level order traversal in
    // the array arr[]
    int arr[] = { 10, 3, 20, 30, 40, 2,
                  40, 50, 0, 0, 0, 0 };
 
    // Initialise Tree
    TreeNode<int>* root;
    root = takeInputLevelWise(arr);
 
    // Function call to replace with
    // depth value
    replaceWithDepthValue(root);
 
    // Function call to print
    // in level order
    printLevelATNewLine(root);
    return 0;
}

Java

// Java program to replace node with
// it's depth value
 
// Importing classes and interface
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 
class GFG {
    // TreeNode class
    static class TreeNode<T> {
        // To store node value
        T data;
 
        // List of TreeNode to store
        // the child nodes
        ArrayList<TreeNode<T> > children;
 
        // Constructor to assign data to node
        TreeNode(T data)
        {
            this.data = data;
            children = new ArrayList<TreeNode<T> >();
        }
    }
 
    // Function to take input level wise
    // i.e., in level order traversal
    static TreeNode<Integer> takeInputLevelWise(int arr[])
    {
        int idx = 1;
 
        // Input root
        int rootData = arr[0];
 
        // Initialize tree with a root node
        TreeNode<Integer> root
            = new TreeNode<Integer>(rootData);
 
        // Initialize queue for appending
        // node as a child of parent in
        // N-ary tree
        Queue<TreeNode<Integer> > pendingNodes
            = new LinkedList<TreeNode<Integer> >();
 
        // Push the root node in queue
        pendingNodes.add(root);
 
        // While queue is not empty append
        // child to the node
        while (pendingNodes.size() != 0) {
 
            // Take the first node
            TreeNode<Integer> front = pendingNodes.peek();
            pendingNodes.poll();
 
            // Input number of its child
            int numChild = arr[idx];
            idx++;
 
            for (int i = 0; i < numChild; i++) {
                int childData = arr[idx];
                idx++;
 
                // Make child Node
                TreeNode<Integer> child
                    = new TreeNode<Integer>(childData);
 
                // Append child node to
                // it's parent
                front.children.add(child);
                pendingNodes.add(child);
            }
        }
        return root;
    }
 
    // Function to print each node data
    // in level order
    static void printLevelATNewLine(TreeNode<Integer> root)
    {
        Queue<TreeNode<Integer> > q
            = new LinkedList<TreeNode<Integer> >();
        q.add(root);
        q.add(null);
        while (!q.isEmpty()) {
            TreeNode<Integer> first = q.peek();
            q.poll();
 
            if (first == null) {
                // If there is no more nodes
                if (q.isEmpty()) {
                    break;
                }
                // All the nodes of current level are
                // visited
                System.out.println();
                q.add(null);
                continue;
            }
 
            System.out.print(first.data + " ");
 
            // Append current node's child to queue
            for (int i = 0; i < first.children.size();
                 i++) {
                q.add(first.children.get(i));
            }
        }
    }
 
    // Helper function to replace the
    // node data with their level value
    static void helper(TreeNode<Integer> root, int depth)
    {
        // Replace the node data with
        // it's depth
        root.data = depth;
        for (int i = 0; i < root.children.size(); i++) {
            helper(root.children.get(i), depth + 1);
        }
    }
 
    // Function to replace with depth
    static void
    replaceWithDepthValue(TreeNode<Integer> root)
    {
        helper(root, 0);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given level order traversal in
        // the array arr[]
        int arr[]
            = { 10, 3, 20, 30, 40, 2, 40, 50, 0, 0, 0, 0 };
 
        // Initialise Tree
        TreeNode<Integer> root;
        root = takeInputLevelWise(arr);
 
        // Function call to replace with
        // depth value
        replaceWithDepthValue(root);
 
        // Function call to print
        // in level order
        printLevelATNewLine(root);
    }
}
 
// This code is contributed by jainlovely450
Producción

0 
1 1 1 
2 2 

Complejidad de tiempo: O(N), donde N es el número de Nodes en el árbol. 
Espacio Auxiliar: O(N), donde N es el número de Nodes en el Árbol.
 

Otro enfoque: también podemos reemplazar el valor del Node con su profundidad al crear el árbol. Estamos atravesando el nivel de array, lo que significa que los Nodes actualmente presentes en la cola tienen la misma profundidad. A medida que agreguemos sus Nodes secundarios a la cola, estarán presentes en el siguiente nivel. Podemos inicializar una variable como profundidad actual igual a 1 y cuando creamos un Node secundario podemos asignar su valor al nivel de profundidad actual. Después de atravesar todos los Nodes presentes en el nivel actual, incrementaremos el nivel de profundidad actual en 1.

C++

// C++ program to implement node with
// it's depth value
#include <bits/stdc++.h>
using namespace std;
 
// Treenode class using template
template <typename T> class TreeNode {
public:
    // To store node value
    T data;
 
    // Pointer to TreeNode to store
    // the child node
    vector<TreeNode<T>*> children;
 
    // Constructor to assign data
    // to node
    TreeNode(T data) { this->data = data; }
 
    // Destructors to delete a node
    ~TreeNode()
    {
        for (int i = 0; i < children.size(); i++) {
            delete children[i];
        }
    }
};
 
// Function to take input level wise
// i.e., in level order traversal
TreeNode<int>* takeInputLevelWise(int arr[])
{
    int idx = 1;
    int depthLevel = 1;
 
    // Initialize tree with a root node
    // with depth 0
    TreeNode<int>* root = new TreeNode<int>(0);
 
    // Initialise queue for appending
    // node as a child of parent in
    // N-ary tree
    queue<TreeNode<int>*> pendingNodes;
 
    // Push the root node in queue
    pendingNodes.push(root);
 
    // While queue is not empty append
    // child to the node
    while (pendingNodes.size() != 0) {
        // Number of nodes present in the current level
        int size = pendingNodes.size();
 
        while (size > 0) {
            // Take the first node
            TreeNode<int>* front = pendingNodes.front();
            pendingNodes.pop();
 
            // Input number of its child
            int numChild = arr[idx];
            idx++;
 
            for (int i = 0; i < numChild; i++) {
                idx++;
                // Make child Node and assign its data
                // value equal to depthLevel
                TreeNode<int>* child
                    = new TreeNode<int>(depthLevel);
 
                // Append child node to
                // it's parent
                front->children.push_back(child);
                pendingNodes.push(child);
            }
            size--;
        }
        // Increment depth level
        depthLevel++;
    }
    return root;
}
 
// Function to print each node data
// in level order
void printLevelATNewLine(TreeNode<int>* root)
{
    queue<TreeNode<int>*> q;
    q.push(root);
    q.push(NULL);
    while (!q.empty()) {
        TreeNode<int>* first = q.front();
        q.pop();
 
        if (first == NULL) {
            // If there is no more nodes to visit
            if (q.empty()) {
                break;
            }
            // All the nodes of current level are visited
            cout << endl;
            q.push(NULL);
            continue;
        }
 
        cout << first->data << " ";
        // Append current node's child to queue
        for (int i = 0; i < first->children.size(); i++) {
            q.push(first->children[i]);
        }
    }
}
 
// Driver Code
int main()
{
    // Given level order traversal in
    // the array arr[]
    int arr[]
        = { 10, 3, 20, 30, 40, 2, 40, 50, 0, 0, 0, 0 };
 
    // Initialise Tree
    TreeNode<int>* root;
    root = takeInputLevelWise(arr);
 
    // Function call to print
    // in level order
    printLevelATNewLine(root);
    return 0;
}
 
// This code is contributed by jainlovely450

Java

// Java program to implement node with
// it's depth value
 
// Importing classes and interface
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 
public class GFG {
 
    // TreeNode class
    static class TreeNode<T> {
        // To store node value
        T data;
 
        // List of TreeNode to store
        // the child nodes
        ArrayList<TreeNode<T> > children;
 
        // Constructor to assign data to node
        TreeNode(T data)
        {
            this.data = data;
            children = new ArrayList<TreeNode<T> >();
        }
    }
 
    // Function to take input level wise
    // i.e., in level order traversal and
    // assign value of node equal to its depth
    static TreeNode<Integer> takeInputLevelWise(int arr[])
    {
        int idx = 1;
        int depthLevel = 1;
         
      // Initialize tree with a root node
        // with depth 0
        TreeNode<Integer> root = new TreeNode<Integer>(0);
        
        // Initialize queue for appending
        // node as a child of parent in
        // N-ary tree
        Queue<TreeNode<Integer> > pendingNodes
            = new LinkedList<TreeNode<Integer> >();
 
        // Push the root node in queue
        pendingNodes.add(root);
 
        // While queue is not empty append
        // child to the node
        while (!pendingNodes.isEmpty()) {
            // Number of nodes present in the current level
            int size = pendingNodes.size();
 
            while (size > 0) {
                TreeNode<Integer> front
                    = pendingNodes.peek();
                pendingNodes.poll();
 
                // Input number of child
                int numChild = arr[idx];
                idx++;
                for (int i = 0; i < numChild; i++) {
                    idx++;
 
                    // Make child Node and assign its data
                    // value equal to depthLevel
                    TreeNode<Integer> child
                        = new TreeNode<Integer>(depthLevel);
 
                    // Append child node to
                    // it's parent
                    front.children.add(child);
                    pendingNodes.add(child);
                }
                size--;
            }
            // Increment depth level
            depthLevel++;
        }
        return root;
    }
 
    // Function to print each node data
    // in level order
    static void printLevelATNewLine(TreeNode<Integer> root)
    {
        Queue<TreeNode<Integer> > q
            = new LinkedList<TreeNode<Integer> >();
        q.add(root);
        q.add(null);
        while (!q.isEmpty()) {
            TreeNode<Integer> first = q.peek();
            q.poll();
            if (first == null) {
                // If there is no more nodes to visit
                if (q.isEmpty()) {
                    break;
                }
                // All the nodes of current level are
                // visited
                System.out.println();
                q.add(null);
                continue;
            }
 
            System.out.print(first.data + " ");
 
            // Append current node's child to queue
            for (int i = 0; i < first.children.size();
                 i++) {
                q.add(first.children.get(i));
            }
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given level order traversal in
        // the array arr[]
        int arr[]
            = { 10, 3, 20, 30, 40, 2, 40, 50, 0, 0, 0, 0 };
 
        // Initialize Tree
        TreeNode<Integer> root;
        root = takeInputLevelWise(arr);
 
        // Function call to print
        // in level order
        printLevelATNewLine(root);
    }
}
 
// This code is contributed by jainlovely450
Producción

0 
1 1 1 
2 2 

Publicación traducida automáticamente

Artículo escrito por priyanshu21101997 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 *