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