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