给定一棵用邻接表表示的N元树，我们需要编写一个程序来计算这棵树中所有这样的节点，因为这棵树的子节点比父节点多。 例如
null
![图片[1]-给定一棵n元树，计算子节点数多于父节点数的节点数-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/n-ary-tree.png)
在上面的树中，计数将为1，因为只有一个这样的节点是“2”，其子节点数比其父节点数多。2有三个孩子（4、5和6），而其父母1只有两个孩子（2和3）。
我们可以用这两种方法来解决这个问题 BFS 和 DFS 算法。我们将在这里详细解释如何使用BFS算法解决这个问题。 因为树是用邻接列表表示的。因此，对于任何一个节点，比如’u’，这个节点的子节点的数量可以表示为adj[u]。大小（）。 现在的想法是在给定的树上应用BFS，在遍历节点“u”的子节点时，我们只需检查is adj[v]。大小（）>adj[u]。大小（）。 以下是上述理念的实施：
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> |
输出：
1
时间复杂性 ：O（n），其中n是树中的节点数。
本文由 严酷的阿加瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
