PAT甲级1004 Counting Leaves (30分)：[C++题解]树、邻接表存储树、dfs遍历树

本文主要是介绍PAT甲级1004 Counting Leaves (30分)：[C++题解]树、邻接表存储树、dfs遍历树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 题目分析
- 题目链接

题目分析

在这里插入图片描述

题意重述：一棵树，求每一层的叶子节点数目。

分析构造树，使用邻接表来存（相当于存储有向图）。

需要一个头结点数组h[N]，然后每个头节点往外形成一个单链表e[],ne[];(用数组模拟)单链表中用来存该结点的孩子结点，用cnt[N]数组来记录每一层的叶子结点数。

使用深度优先遍历dfs来求每一层的叶子节点数，由于是邻接表式的存储，头结点数组中某结点值是-1，表示是叶子结点，这也就是dfs的退出的条件，此时如何退出呢？需要将该叶子结点所在层数的叶子数++，然后记得更新树的最大深度。

然后深度遍历该结点的孩子结点。

ac代码

#include<bits/stdc++.h>
using namespace std;const int N=110;
int n,m;
//用邻接表来存
int h[N], e[N],ne[N], idx; //idx默认初始化为0int cnt[N] ;// 每一层的叶子结点数int max_depth; //树的最大层数void add(int a, int b){ //使用头结点a的链表 h[a]//在a这个单链表内，插入结点b(头插法)//表示a有一个儿子b//e[ ] 存的是结点号b//ne [ ] 中存的是下一个结点序号idx，不是结点号e[idx] =b,ne[idx] =h[a],h[a]=idx++;//cout<< a<<' '<<b<<endl;
}void dfs(int u, int depth){if(h[u]==-1){ //说明u是叶子结点cnt[depth]++;//depth这一层的计数++max_depth=max(max_depth,depth);return;}//遍历头结点u对应的单链表h[u]for(int i =h[u]; i!=-1; i=ne[i]){dfs(e[i],depth+1);//}}int main(){cin>> n>> m;memset(h ,-1,sizeof h);for(int i=0;i<m;i++){int id ,k;cin>> id >> k;while(k--){int son;cin>>son;add(id , son);//构造邻接表}}dfs(1,0);  //结点号，层数cout<<cnt[0];for(int i=1;i<=max_depth;i++) cout<<" "<<cnt[i];}