Dado un árbol N-ario representado como una lista de adyacencia, necesitamos escribir un programa para contar todos esos Nodes en este árbol que tiene más hijos que su padre.
Por ejemplo,
CPP
// C++ program to count number of nodes
// which has more children than its parent
#include<bits/stdc++.h>
using namespace std;
// function to count number of nodes
// which has more children than its parent
int countNodes(vector<int> adj[], int root)
{
int count = 0;
// queue for applying BFS
queue<int> q;
// BFS algorithm
q.push(root);
while (!q.empty())
{
int node = q.front();
q.pop();
// traverse children of node
for( int i=0;i<adj[node].size();i++)
{
// children of node
int children = adj[node][i];
// if number of childs of children
// is greater than number of childs
// of node, then increment count
if (adj[children].size() > adj[node].size())
count++;
q.push(children);
}
}
return count;
}
// Driver program to test above functions
int main()
{
// adjacency list for n-ary tree
vector<int> adj[10];
// construct n ary tree as shown
// in above diagram
adj[1].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
adj[2].push_back(5);
adj[2].push_back(6);
adj[3].push_back(9);
adj[5].push_back(7);
adj[5].push_back(8);
int root = 1;
cout << countNodes(adj, root);
return 0;
}
Java
// Java program to count number of nodes
// which has more children than its parent
import java.util.*;
class GFG
{
// function to count number of nodes
// which has more children than its parent
static int countNodes(Vector<Integer> adj[], int root)
{
int count = 0;
// queue for applying BFS
Queue<Integer> q = new LinkedList<>();
// BFS algorithm
q.add(root);
while (!q.isEmpty())
{
int node = q.peek();
q.remove();
// traverse children of node
for( int i=0;i<adj[node].size();i++)
{
// children of node
int children = adj[node].get(i);
// if number of childs of children
// is greater than number of childs
// of node, then increment count
if (adj[children].size() > adj[node].size())
count++;
q.add(children);
}
}
return count;
}
// Driver code
public static void main(String[] args)
{
// adjacency list for n-array tree
Vector<Integer> []adj = new Vector[10];
for(int i= 0; i < 10 ; i++) {
adj[i] = new Vector<>();
}
// conn array tree as shown
// in above diagram
adj[1].add(2);
adj[1].add(3);
adj[2].add(4);
adj[2].add(5);
adj[2].add(6);
adj[3].add(9);
adj[5].add(7);
adj[5].add(8);
int root = 1;
System.out.print(countNodes(adj, root));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to count number of nodes # which has more children than its parent from collections import deque adj = [[] for i in range(100)] # function to count number of nodes # which has more children than its parent def countNodes(root): count = 0 # queue for applying BFS q = deque() # BFS algorithm q.append(root) while len(q) > 0: node = q.popleft() # traverse children of node for i in adj[node]: # children of node children = i # if number of childs of children # is greater than number of childs # of node, then increment count if (len(adj[children]) > len(adj[node])): count += 1 q.append(children) return count # Driver program to test above functions # construct n ary tree as shown # in above diagram adj[1].append(2) adj[1].append(3) adj[2].append(4) adj[2].append(5) adj[2].append(6) adj[3].append(9) adj[5].append(7) adj[5].append(8) root = 1 print(countNodes(root)) # This code is contributed by mohit kumar 29
C#
// C# program to count number of nodes
// which has more children than its parent
using System;
using System.Collections.Generic;
class GFG
{
// function to count number of nodes
// which has more children than its parent
static int countNodes(List<int> []adj, int root)
{
int count = 0;
// queue for applying BFS
List<int> q = new List<int>();
// BFS algorithm
q.Add(root);
while (q.Count != 0)
{
int node = q[0];
q.RemoveAt(0);
// traverse children of node
for( int i = 0; i < adj[node].Count; i++)
{
// children of node
int children = adj[node][i];
// if number of childs of children
// is greater than number of childs
// of node, then increment count
if (adj[children].Count > adj[node].Count)
count++;
q.Add(children);
}
}
return count;
}
// Driver code
public static void Main(String[] args)
{
// adjacency list for n-array tree
List<int> []adj = new List<int>[10];
for(int i= 0; i < 10 ; i++) {
adj[i] = new List<int>();
}
// conn array tree as shown
// in above diagram
adj[1].Add(2);
adj[1].Add(3);
adj[2].Add(4);
adj[2].Add(5);
adj[2].Add(6);
adj[3].Add(9);
adj[5].Add(7);
adj[5].Add(8);
int root = 1;
Console.Write(countNodes(adj, root));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to count number of nodes
// which has more children than its parent
// function to count number of nodes
// which has more children than its parent
function countNodes(adj,root)
{
let count = 0;
// queue for applying BFS
let q = [];
// BFS algorithm
q.push(root);
while (q.length!=0)
{
let node = q[0];
q.shift();
// traverse children of node
for( let i=0;i<adj[node].length;i++)
{
// children of node
let children = adj[node][i];
// if number of childs of children
// is greater than number of childs
// of node, then increment count
if (adj[children].length > adj[node].length)
count++;
q.push(children);
}
}
return count;
}
// Driver code
// adjacency list for n-array tree
let adj = [];
for(let i= 0; i < 10 ; i++) {
adj[i] = [];
}
// conn array tree as shown
// in above diagram
adj[1].push(2);
adj[1].push(3);
adj[2].push(4);
adj[2].push(5);
adj[2].push(6);
adj[3].push(9);
adj[5].push(7);
adj[5].push(8);
let root = 1;
document.write(countNodes(adj, root));
// This code is contributed by patel2127
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA