Dado un Node x, encuentre el número de hijos de x (si existe) en el árbol n-ario dado.
C++
// C++ program to find number
// of children of given node
#include <bits/stdc++.h>
using namespace std;
// Represents a node of an n-ary tree
class Node {
public:
int key;
vector<Node*> child;
Node(int data)
{
key = data;
}
};
// Function to calculate number
// of children of given node
int numberOfChildren(Node* root, int x)
{
// initialize the numChildren as 0
int numChildren = 0;
if (root == NULL)
return 0;
// Creating a queue and pushing the root
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int n = q.size();
// If this node has children
while (n > 0) {
// Dequeue an item from queue and
// check if it is equal to x
// If YES, then return number of children
Node* p = q.front();
q.pop();
if (p->key == x) {
numChildren = numChildren + p->child.size();
return numChildren;
}
// Enqueue all children of the dequeued item
for (int i = 0; i < p->child.size(); i++)
q.push(p->child[i]);
n--;
}
}
return numChildren;
}
// Driver program
int main()
{
// Creating a generic tree
Node* root = new Node(20);
(root->child).push_back(new Node(2));
(root->child).push_back(new Node(34));
(root->child).push_back(new Node(50));
(root->child).push_back(new Node(60));
(root->child).push_back(new Node(70));
(root->child[0]->child).push_back(new Node(15));
(root->child[0]->child).push_back(new Node(20));
(root->child[1]->child).push_back(new Node(30));
(root->child[2]->child).push_back(new Node(40));
(root->child[2]->child).push_back(new Node(100));
(root->child[2]->child).push_back(new Node(20));
(root->child[0]->child[1]->child).push_back(new Node(25));
(root->child[0]->child[1]->child).push_back(new Node(50));
// Node whose number of
// children is to be calculated
int x = 50;
// Function calling
cout << numberOfChildren(root, x) << endl;
return 0;
}
Java
// Java program to find number
// of children of given node
import java.util.*;
class GFG
{
// Represents a node of an n-ary tree
static class Node
{
int key;
Vector<Node> child = new Vector<>();
Node(int data)
{
key = data;
}
};
// Function to calculate number
// of children of given node
static int numberOfChildren(Node root, int x)
{
// initialize the numChildren as 0
int numChildren = 0;
if (root == null)
return 0;
// Creating a queue and pushing the root
Queue<Node> q = new LinkedList<Node>();
q.add(root);
while (!q.isEmpty())
{
int n = q.size();
// If this node has children
while (n > 0)
{
// Dequeue an item from queue and
// check if it is equal to x
// If YES, then return number of children
Node p = q.peek();
q.remove();
if (p.key == x)
{
numChildren = numChildren +
p.child.size();
return numChildren;
}
// Enqueue all children of the dequeued item
for (int i = 0; i < p.child.size(); i++)
q.add(p.child.get(i));
n--;
}
}
return numChildren;
}
// Driver Code
public static void main(String[] args)
{
// Creating a generic tree
Node root = new Node(20);
(root.child).add(new Node(2));
(root.child).add(new Node(34));
(root.child).add(new Node(50));
(root.child).add(new Node(60));
(root.child).add(new Node(70));
(root.child.get(0).child).add(new Node(15));
(root.child.get(0).child).add(new Node(20));
(root.child.get(1).child).add(new Node(30));
(root.child.get(2).child).add(new Node(40));
(root.child.get(2).child).add(new Node(100));
(root.child.get(2).child).add(new Node(20));
(root.child.get(0).child.get(1).child).add(new Node(25));
(root.child.get(0).child.get(1).child).add(new Node(50));
// Node whose number of
// children is to be calculated
int x = 50;
// Function calling
System.out.println(numberOfChildren(root, x));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find number # of children of given node # Node of a linked list class Node: def __init__(self, data = None): self.key = data self.child = [] # Function to calculate number # of children of given node def numberOfChildren( root, x): # initialize the numChildren as 0 numChildren = 0 if (root == None): return 0 # Creating a queue and appending the root q = [] q.append(root) while (len(q) > 0) : n = len(q) # If this node has children while (n > 0): # Dequeue an item from queue and # check if it is equal to x # If YES, then return number of children p = q[0] q.pop(0) if (p.key == x) : numChildren = numChildren + len(p.child) return numChildren i = 0 # Enqueue all children of the dequeued item while ( i < len(p.child)): q.append(p.child[i]) i = i + 1 n = n - 1 return numChildren # Driver program # Creating a generic tree root = Node(20) (root.child).append(Node(2)) (root.child).append(Node(34)) (root.child).append(Node(50)) (root.child).append(Node(60)) (root.child).append(Node(70)) (root.child[0].child).append(Node(15)) (root.child[0].child).append(Node(20)) (root.child[1].child).append(Node(30)) (root.child[2].child).append(Node(40)) (root.child[2].child).append(Node(100)) (root.child[2].child).append(Node(20)) (root.child[0].child[1].child).append(Node(25)) (root.child[0].child[1].child).append(Node(50)) # Node whose number of # children is to be calculated x = 50 # Function calling print( numberOfChildren(root, x) ) # This code is contributed by Arnab Kundu
C#
// C# program to find number
// of children of given node
using System;
using System.Collections.Generic;
class GFG
{
// Represents a node of an n-ary tree
public class Node
{
public int key;
public List<Node> child = new List<Node>();
public Node(int data)
{
key = data;
}
};
// Function to calculate number
// of children of given node
static int numberOfChildren(Node root, int x)
{
// initialize the numChildren as 0
int numChildren = 0;
if (root == null)
return 0;
// Creating a queue and pushing the root
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
while (q.Count != 0)
{
int n = q.Count;
// If this node has children
while (n > 0)
{
// Dequeue an item from queue and
// check if it is equal to x
// If YES, then return number of children
Node p = q.Peek();
q.Dequeue();
if (p.key == x)
{
numChildren = numChildren +
p.child.Count;
return numChildren;
}
// Enqueue all children of the dequeued item
for (int i = 0; i < p.child.Count; i++)
q.Enqueue(p.child[i]);
n--;
}
}
return numChildren;
}
// Driver Code
public static void Main(String[] args)
{
// Creating a generic tree
Node root = new Node(20);
(root.child).Add(new Node(2));
(root.child).Add(new Node(34));
(root.child).Add(new Node(50));
(root.child).Add(new Node(60));
(root.child).Add(new Node(70));
(root.child[0].child).Add(new Node(15));
(root.child[0].child).Add(new Node(20));
(root.child[1].child).Add(new Node(30));
(root.child[2].child).Add(new Node(40));
(root.child[2].child).Add(new Node(100));
(root.child[2].child).Add(new Node(20));
(root.child[0].child[1].child).Add(new Node(25));
(root.child[0].child[1].child).Add(new Node(50));
// Node whose number of
// children is to be calculated
int x = 50;
// Function calling
Console.WriteLine(numberOfChildren(root, x));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program to find number
// of children of given node
// Represents a node of an n-ary tree
class Node
{
constructor(data)
{
this.key = data;
this.child = []
}
};
// Function to calculate number
// of children of given node
function numberOfChildren(root, x)
{
// initialize the numChildren as 0
var numChildren = 0;
if (root == null)
return 0;
// Creating a queue and pushing the root
var q = [];
q.push(root);
while (q.length != 0)
{
var n = q.length;
// If this node has children
while (n > 0)
{
// Dequeue an item from queue and
// check if it is equal to x
// If YES, then return number of children
var p = q[0];
q.shift();
if (p.key == x)
{
numChildren = numChildren +
p.child.length;
return numChildren;
}
// push all children of the dequeued item
for (var i = 0; i < p.child.length; i++)
q.push(p.child[i]);
n--;
}
}
return numChildren;
}
// Driver Code
// Creating a generic tree
var root = new Node(20);
(root.child).push(new Node(2));
(root.child).push(new Node(34));
(root.child).push(new Node(50));
(root.child).push(new Node(60));
(root.child).push(new Node(70));
(root.child[0].child).push(new Node(15));
(root.child[0].child).push(new Node(20));
(root.child[1].child).push(new Node(30));
(root.child[2].child).push(new Node(40));
(root.child[2].child).push(new Node(100));
(root.child[2].child).push(new Node(20));
(root.child[0].child[1].child).push(new Node(25));
(root.child[0].child[1].child).push(new Node(50));
// Node whose number of
// children is to be calculated
var x = 50;
// Function calling
document.write(numberOfChildren(root, x));
// This code is contributed by itsok.
</script>
Publicación traducida automáticamente
Artículo escrito por Sahil_Bansall y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA