Dado un árbol n-ario que tiene N Nodes numerados del 1 al N, la tarea es imprimir una lista de Nodes que contengan 0, 1, 2, 3, . . ., n niños.
Nota: Un árbol n-ario es un árbol en el que los Nodes pueden tener como máximo n hijos.
Ejemplos :
Aporte:
Salida :
0 niño: 3, 5, 6, 7
1 niño: 4
2 niño: 2
3 niño: 1Aporte:
Salida :
0 niño: 15, 30, 40, 99, 22, 46, 56, 25, 90
1 niño: 34, 60, 70
2 niño: 12, 21
3 niño: 50
5 niño: 20
Enfoque: La idea de resolver el problema iterando el árbol utilizando el recorrido de orden de nivel .
Siga los pasos que se mencionan a continuación para resolver el problema:
- Travesía de i = 1 a N:
- Para cada Node, use el recorrido de orden de nivel para encontrar la ubicación de ese valor en el árbol.
- Al encontrar ese Node, use la lista de hijos y calcule la cantidad de hijos que tiene (digamos X ).
- Use un mapa para agregar el i-ésimo Node en la lista de Nodes que tienen X hijos.
- Iterar el mapa e imprimir los Nodes que tengan el número de hijos en el rango [0 a n].
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
// Node Class
class Node {
public:
int key_ele;
vector<Node*> child;
Node(int data_value)
{
key_ele = data_value;
}
};
// Function to find number of child
int numberOfChild(Node* root, int ele)
{
int num = 0;
if (root == NULL) {
return 0;
}
// Initializing queue data structure
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int n = q.size();
while (n > 0) {
Node* nn = q.front();
q.pop();
if (nn->key_ele == ele) {
num = num + nn->child.size();
return num;
}
for (int i = 0;
i < nn->child.size(); i++) {
q.push(nn->child[i]);
}
n--;
}
}
return num;
}
// Function to print the nodes
// having children in range [0, n]
void printTree(Node* root, vector<int> vec)
{
// map to store nodes
// with same number of children
map<int, vector<int> > mp;
int i = 0;
for (i = 0; i < vec.size(); i++) {
int temp;
temp = numberOfChild(root, vec[i]);
mp[temp].push_back(vec[i]);
}
map<string, int>::iterator iter;
for (auto& value : mp) {
cout << value.first << " child: ";
auto& list = value.second;
int len = list.size();
int s = 0;
for (auto& element : list) {
if (s < len - 1) {
cout << element << ", ";
}
else {
cout << element;
}
s++;
}
cout << endl;
}
}
// Driver Code
int main()
{
vector<int> vec = { 1, 2, 3, 4, 5, 6, 7 };
map<int, vector<int> > mp;
vector<int> v;
Node* root = new Node(1);
(root->child).push_back(new Node(2));
(root->child).push_back(new Node(3));
(root->child).push_back(new Node(4));
(root->child[0]->child).push_back(new Node(5));
(root->child[0]->child).push_back(new Node(6));
(root->child[2]->child).push_back(new Node(7));
// Function call
printTree(root, vec);
return 0;
}
Java
// Java code for the above approach:
import java.util.*;
public class Main {
static class Node {
int key_ele;
ArrayList <Node> child;
Node(int data_value)
{
key_ele = data_value;
child = new ArrayList <Node> ();
}
}
// Function to find number of child
static int numberOfChild(Node root, int ele)
{
int num = 0;
if (root == null) {
return 0;
}
// Initializing queue data structure
Queue <Node> q = new LinkedList <> ();
q.add(root);
while (!q.isEmpty()) {
int n = q.size();
while (n > 0) {
Node nn = q.peek();
q.remove();
if (nn.key_ele == ele) {
num = num + nn.child.size();
return num;
}
for (int i = 0;
i < nn.child.size(); i++) {
q.add(nn.child.get(i));
}
n--;
}
}
return num;
}
// Function to print the nodes
// having children in range [0, n]
static void printTree(Node root, int[] vec)
{
// HashMap to store nodes
// with same number of children
HashMap <Integer, ArrayList <Integer> > mp
= new HashMap <Integer,ArrayList <Integer>> ();
int i = 0;
for (i = 0; i < vec.length; i++) {
int temp;
temp = numberOfChild(root, vec[i]);
if(mp.containsKey(temp)){
mp.get(temp).add(vec[i]);
}
else{
mp.put(temp, new ArrayList <Integer> ());
mp.get(temp).add(vec[i]);
}
}
for (Map.Entry <Integer, ArrayList<Integer> > value : mp.entrySet()) {
System.out.print(value.getKey() + " child: ");
ArrayList <Integer> list = value.getValue();
int len = list.size();
for (i=0; i < len; i++) {
if (i < len - 1) {
System.out.print(list.get(i) + ", ");
}
else {
System.out.print(list.get(i));
}
}
System.out.print("\n");
}
}
public static void main(String args[]) {
int[] vec = { 1, 2, 3, 4, 5, 6, 7 };
HashMap <Integer, ArrayList <Integer> > mp;
ArrayList <Integer> v;
Node root = new Node(1);
(root.child).add(new Node(2));
(root.child).add(new Node(3));
(root.child).add(new Node(4));
(root.child.get(0).child).add(new Node(5));
(root.child.get(0).child).add(new Node(6));
(root.child.get(2).child).add(new Node(7));
// Function call
printTree(root, vec);
}
}
// This code has been contributed by Sachin Sahara (sachin801)
Producción
0 child: 3, 5, 6, 7 1 child: 4 2 child: 2 3 child: 1
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sahilsulakhe3 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA