Dada una raíz de árbol de array N y un número entero K , la tarea es imprimir todos los primos del Node K.
Nota: dos Nodes se consideran primos si tienen la misma profundidad (están en el mismo nivel) y tienen diferentes padres.
Ejemplos:
Considere el siguiente árbol:
Entrada: K = 39
Salida: 88 98 61 74 17 72 19Entrada: K = 17
Salida: 88 98 61 74 39Entrada: K = 90
Salida: NA
Enfoque: La idea es hacer un recorrido por orden de niveles . Durante el recorrido, si encontramos un Node cuyo hijo es igual al elemento dado, entonces no empujaremos a los hijos de este Node. Empujaremos a los hijos de los otros Nodes y el bucle interno terminará cuando se atraviesen todos los elementos de ese nivel. Siga los pasos a continuación para resolver el problema:
- Si root es igual a nulo, entonces regresa.
- Inicialice la cola q[] y envíe root a la cola q[].
- Inicialice la variable booleana encontrada como falsa.
- Inicialice las variables qsize como 0 y node temp.
- Repita el ciclo while hasta que q[] no esté vacío y no se encuentre el Node y realice las siguientes tareas:
- Establezca el tamaño qsize como el tamaño de la cola q[].
- Itere sobre el bucle while hasta que qsize sea mayor que 0 y realice las siguientes tareas:
- Establezca tempp como el frente de la cola q[].
- De la cola de la cola q[].
- Si se encuentra igual a verdadero, entonces empuje todos sus hijos a la cola q[].
- Iterar sobre el rango [0, temp->child.size()) usando la variable i y realizar las siguientes tareas:
- Si el elemento secundario no es nulo y su clave es igual al valor, establezca el valor de encontrado como verdadero.
- Si encontrado es falso, entonces empuje todos sus hijos a la cola q[].
- Disminuya el valor de qsize en 1.
- Si el resultado es falso, escriba «No es posible».
- De lo contrario, inicialice las variables qsize como el tamaño de la cola q[].
- Si qsize es igual a 0 , imprima «Sin primos».
- De lo contrario, imprime todos los elementos de la cola q[].
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a node of N-ary tree
struct Node {
int key;
vector<Node*> child;
};
// New node creation
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
return temp;
}
// Function to find the cousins of a
// given node in an N-array tree
void printCousins(Node* root, int value)
{
// Base case
if (root == NULL)
return;
queue<Node*> q;
q.push(root);
// If we find the node
// with value as the key
bool found = false;
int qsize = 0;
Node* tempp;
while (!q.empty() && !found) {
qsize = q.size();
while (qsize) {
// Storing the current node
tempp = q.front();
q.pop();
// If we have already found
// the value as child of a node,
// we need to insert children of other
// node of same level in the queue
if (found == true) {
for (int i = 0; i < tempp->child.size();
i++) {
if (tempp->child[i] != NULL)
q.push(tempp->child[i]);
}
}
// If value is child of tempp node
for (int i = 0; i < tempp->child.size(); i++)
if (tempp->child[i] != NULL
&& tempp->child[i]->key == value)
found = true;
// If value is not the child of tempp node
// then insert all the children
// of the tempp node
if (found == false) {
for (int i = 0; i < tempp->child.size();
i++) {
if (tempp->child[i] != NULL)
q.push(tempp->child[i]);
}
}
qsize--;
}
}
if (found) {
// Queue will contain the cousins
qsize = q.size();
if (qsize == 0)
cout << "NA";
for (int i = 0; i < qsize; i++) {
tempp = q.front();
q.pop();
cout << tempp->key << " ";
}
}
else {
// When value is not in the tree
cout << "Not Possible";
}
cout << "\n";
return;
}
// Driver Code
int main()
{
Node* root = newNode(10);
(root->child).push_back(newNode(77));
(root->child).push_back(newNode(90));
(root->child).push_back(newNode(35));
(root->child).push_back(newNode(19));
(root->child[0]->child).push_back(newNode(88));
(root->child[0]->child).push_back(newNode(98));
(root->child[0]->child[1]->child)
.push_back(newNode(76));
(root->child[0]->child[1]->child)
.push_back(newNode(20));
(root->child[1]->child).push_back(newNode(61));
(root->child[1]->child).push_back(newNode(74));
(root->child[2]->child).push_back(newNode(39));
(root->child[3]->child).push_back(newNode(17));
(root->child[3]->child).push_back(newNode(72));
(root->child[3]->child).push_back(newNode(19));
// Find the cousins of value
int value = 39;
printCousins(root, value);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Structure of a node of N-ary tree
static class Node {
int key;
Vector<Node> child = new Vector<Node>();
};
// New node creation
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
return temp;
}
// Function to find the cousins of a
// given node in an N-array tree
static void printCousins(Node root, int value)
{
// Base case
if (root == null)
return;
Queue<Node> q = new LinkedList<GFG.Node>();
q.add(root);
// If we find the node
// with value as the key
boolean found = false;
int qsize = 0;
Node tempp;
while (!q.isEmpty() && !found) {
qsize = q.size();
while (qsize > 0) {
// Storing the current node
tempp = q.peek();
q.remove();
// If we have already found
// the value as child of a node,
// we need to insert children of other
// node of same level in the queue
if (found == true) {
for (int i = 0; i < tempp.child.size();
i++) {
if (tempp.child.get(i) != null)
q.add(tempp.child.get(i));
}
}
// If value is child of tempp node
for (int i = 0; i < tempp.child.size(); i++)
if (tempp.child.get(i) != null
&& tempp.child.get(i).key == value)
found = true;
// If value is not the child of tempp node
// then insert all the children
// of the tempp node
if (found == false) {
for (int i = 0; i < tempp.child.size();
i++) {
if (tempp.child.get(i) != null)
q.add(tempp.child.get(i));
}
}
qsize--;
}
}
if (found) {
// Queue will contain the cousins
qsize = q.size();
if (qsize == 0)
System.out.print("NA");
for (int i = 0; i < qsize; i++) {
tempp = q.peek();
q.remove();
System.out.print(tempp.key+ " ");
}
}
else {
// When value is not in the tree
System.out.print("Not Possible");
}
System.out.print("\n");
return;
}
// Driver Code
public static void main(String[] args)
{
Node root = newNode(10);
(root.child).add(newNode(77));
(root.child).add(newNode(90));
(root.child).add(newNode(35));
(root.child).add(newNode(19));
(root.child.get(0).child).add(newNode(88));
(root.child.get(0).child).add(newNode(98));
(root.child.get(0).child.get(1).child)
.add(newNode(76));
(root.child.get(0).child.get(1).child)
.add(newNode(20));
(root.child.get(1).child).add(newNode(61));
(root.child.get(1).child).add(newNode(74));
(root.child.get(2).child).add(newNode(39));
(root.child.get(3).child).add(newNode(17));
(root.child.get(3).child).add(newNode(72));
(root.child.get(3).child).add(newNode(19));
// Find the cousins of value
int value = 39;
printCousins(root, value);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python code for the above approach
# Structure of a node of N-ary tree
class Node:
def __init__ (self, k):
self.key = k;
self.child = [];
# node creation
# Function to find the cousins of a
# given node in an N-array tree
def printCousins(root, value):
# Base case
if (root == None):
return;
q = [];
q.append(root);
# If we find the node
# with value as the key
found = False;
qsize = 0;
tempp = None
while (len(q) != 0 and found != 1):
qsize = len(q);
while (qsize != 0):
# Storing the current node
tempp = q[0];
q.pop(0);
# If we have already found
# the value as child of a node,
# we need to insert children of other
# node of same level in the queue
if (found == True):
for i in range(len(tempp.child)):
if (tempp.child[i] != None):
q.append(tempp.child[i]);
# If value is child of tempp node
for i in range(len(tempp.child)):
if (tempp.child[i] != None and tempp.child[i].key == value):
found = True;
# If value is not the child of tempp node
# then insert all the children
# of the tempp node
if (found == False):
for i in range(len(tempp.child)):
if (tempp.child[i] != None):
q.append(tempp.child[i]);
qsize -= 1
if (found):
# Queue will contain the cousins
qsize = len(q);
if (qsize == 0):
print("NA");
for i in range(qsize):
tempp = q[0];
q.pop(0);
print(tempp.key, end= " ");
else:
# When value is not in the tree
print("Not Possible");
print('')
return;
# Driver Code
root = Node(10);
root.child.append(Node(77));
root.child.append(Node(90));
root.child.append(Node(35));
root.child.append(Node(19));
root.child[0].child.append(Node(88));
root.child[0].child.append(Node(98));
root.child[0].child[1].child.append(Node(76));
root.child[0].child[1].child.append(Node(20));
root.child[1].child.append(Node(61));
root.child[1].child.append(Node(74));
root.child[2].child.append(Node(39));
root.child[3].child.append(Node(17));
root.child[3].child.append(Node(72));
root.child[3].child.append(Node(19));
# Find the cousins of value
value = 39;
printCousins(root, value);
# This code is contributed by gfgking
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
// Structure of a node of N-ary tree
class Node {
public int key;
public List<Node> child = new List<Node>();
};
// New node creation
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
return temp;
}
// Function to find the cousins of a
// given node in an N-array tree
static void printCousins(Node root, int value)
{
// Base case
if (root == null)
return;
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
// If we find the node
// with value as the key
bool found = false;
int qsize = 0;
Node tempp;
while (q.Count!=0 && !found) {
qsize = q.Count;
while (qsize > 0) {
// Storing the current node
tempp = q.Peek();
q.Dequeue();
// If we have already found
// the value as child of a node,
// we need to insert children of other
// node of same level in the queue
if (found == true) {
for (int i = 0; i < tempp.child.Count;
i++) {
if (tempp.child[i] != null)
q.Enqueue(tempp.child[i]);
}
}
// If value is child of tempp node
for (int i = 0; i < tempp.child.Count; i++)
if (tempp.child[i] != null
&& tempp.child[i].key == value)
found = true;
// If value is not the child of tempp node
// then insert all the children
// of the tempp node
if (found == false) {
for (int i = 0; i < tempp.child.Count;
i++) {
if (tempp.child[i] != null)
q.Enqueue(tempp.child[i]);
}
}
qsize--;
}
}
if (found) {
// Queue will contain the cousins
qsize = q.Count;
if (qsize == 0)
Console.Write("NA");
for (int i = 0; i < qsize; i++) {
tempp = q.Peek();
q.Dequeue();
Console.Write(tempp.key+ " ");
}
}
else {
// When value is not in the tree
Console.Write("Not Possible");
}
Console.Write("\n");
return;
}
// Driver Code
public static void Main(String[] args)
{
Node root = newNode(10);
(root.child).Add(newNode(77));
(root.child).Add(newNode(90));
(root.child).Add(newNode(35));
(root.child).Add(newNode(19));
(root.child[0].child).Add(newNode(88));
(root.child[0].child).Add(newNode(98));
(root.child[0].child[1].child)
.Add(newNode(76));
(root.child[0].child[1].child)
.Add(newNode(20));
(root.child[1].child).Add(newNode(61));
(root.child[1].child).Add(newNode(74));
(root.child[2].child).Add(newNode(39));
(root.child[3].child).Add(newNode(17));
(root.child[3].child).Add(newNode(72));
(root.child[3].child).Add(newNode(19));
// Find the cousins of value
int value = 39;
printCousins(root, value);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript code for the above approach
// Structure of a node of N-ary tree
class Node {
constructor(k) {
this.key = k;
this.child = [];
}
};
// New node creation
// Function to find the cousins of a
// given node in an N-array tree
function printCousins(root, value) {
// Base case
if (root == null)
return;
let q = [];
q.push(root);
// If we find the node
// with value as the key
let found = false;
let qsize = 0;
let tempp;
while (q.length != 0 && found != 1) {
qsize = q.length;
while (qsize != 0) {
// Storing the current node
tempp = q[0];
q.shift();
// If we have already found
// the value as child of a node,
// we need to insert children of other
// node of same level in the queue
if (found == true) {
for (let i = 0; i < tempp.child.length;
i++) {
if (tempp.child[i] != null)
q.push(tempp.child[i]);
}
}
// If value is child of tempp node
for (let i = 0; i < tempp.child.length; i++)
if (tempp.child[i] != null
&& tempp.child[i].key == value)
found = true;
// If value is not the child of tempp node
// then insert all the children
// of the tempp node
if (found == false) {
for (let i = 0; i < tempp.child.length;
i++) {
if (tempp.child[i] != null)
q.push(tempp.child[i]);
}
}
qsize--;
}
}
if (found) {
// Queue will contain the cousins
qsize = q.length;
if (qsize == 0)
document.write("NA");
for (let i = 0; i < qsize; i++) {
tempp = q[0];
q.shift();
document.write(tempp.key + " ");
}
}
else {
// When value is not in the tree
document.write("Not Possible");
}
document.write('<br>')
return;
}
// Driver Code
let root = new Node(10);
root.child.push(new Node(77));
root.child.push(new Node(90));
root.child.push(new Node(35));
root.child.push(new Node(19));
root.child[0].child.push(new Node(88));
root.child[0].child.push(new Node(98));
root.child[0].child[1].child
.push(new Node(76));
root.child[0].child[1].child
.push(new Node(20));
root.child[1].child.push(new Node(61));
root.child[1].child.push(new Node(74));
root.child[2].child.push(new Node(39));
root.child[3].child.push(new Node(17));
root.child[3].child.push(new Node(72));
root.child[3].child.push(new Node(19));
// Find the cousins of value
let value = 39;
printCousins(root, value);
// This code is contributed by Potta Lokesh
</script>
Producción
Cousins for the element 39: 88 98 61 74 17 72 19
Complejidad temporal: O(N)
Espacio auxiliar: O(N)