PAT 1004.Counting Leaves(30) A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.
输入格式:
Each input file contains one test case. Each case starts with a line containing 0<N<100, the number of nodes in a tree, and M (<N), the number of non-leaf nodes. Then M lines follow, each in the format:
ID K ID[1] ID[2] ... ID[K]
where ID
is a two-digit number representing a given non-leaf node, K
is the number of its children, followed by a sequence of two-digit ID's
of its children. For the sake of simplicity, let us fix the root ID to be 01
.
The input ends with N being 0. That case must NOT be processed.
输出格式:
For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.
The sample case represents a tree with only 2 nodes, where 01
is the root and 02
is its only child. Hence on the root 01
level, there is 0
leaf node; and on the next level, there is 1
leaf node. Then we should output 0 1
in a line.
输入样例:
2 1
01 1 02
输出样例:
0 1
题目分析:输出多叉树中每层中叶子节点的数目。可以使用dfs或bfs。由于题目中提示了节点编号,可以使用静态树结构,使用邻接表的方式存储每个节点的孩子节点的编号。其实也是一种hash的思想,hash[parentIndex] = {},只不过其对应的是一个集合。
使用bfs时,当前队列中的元素即为当前层上的所有节点,只需要枚举每个节点是否有孩子,如果有就将其所有孩子都继入队列,如果没有在则当前层的叶子节点个数+1。
AC代码(bfs):
#include <queue>
#include <vector>
using namespace std;
vector<int> tree[100];//邻接表存储树
int floor[100];//每层叶子节点的个数
int index=0;//根节点在第0层
void bfs(int root){
queue<int> q;
q.push();
while(!q.empty()){
int size = q.size();
//注意不能写成for(int i=0; i<q.size(); ++i)这样q.size()是会改变的
//因为每次枚举一个队首元素 都会出队 所以q.size() -= 1;
for(int i=0; i<size; ++i){
int front = q.front();q.pop();
if(!tree[front].size()){ //没有孩子节点 说明是叶子节点
floor[index] ++;
}
else{
//不是叶子节点 将其所有的孩子节点入队
for(int j=0; j<tree[front].size(); ++j){
q.push(tree[front][j]);
}
}
}
index ++;//下一层
}
}
int main(){
int n, m, k, p, c;
scanf("%d%d", &n, &m);
for(int i=0; i<m; ++i){
scanf("%d %d", &p, &k);
while(k --){
scanf("%d", &c);
tree[p].push_back(c);
}
}
bfs(1);
for(int i=0; i<index; ++i){
printf("%d", floor[i]);
if(i!=index-1)printf(" ");
}
return 0;
}
AC代码(dfs):
vector<int> tree[100];
int floor[100];
int maxDepth=-1;//这个变量用于确定该树有几层
//dfs需要传入的参数 当前节点的索引 当前节点所在的深度
void dfs(int p, int depth){
//递归出口
//没有孩子节点 说明找到一个叶子节点
if(!tree[p].size()){
floor[depth] ++;//当前层叶子节点个数+1
//更新最大的深度
maxDepth = max(depth, maxDepth);
return ;
}
else{
//不是叶子节点,枚举其所有孩子节点是否为叶子节点
for(int i=0; i<tree[p].size(); ++i)
dfs(tree[p][i], depth+1); //孩子节点的深度比当前节点的深度大1
}
}
int main(){
int n, m, k, p, c;
scanf("%d%d", &n, &m);
for(int i=0; i<m; ++i){
scanf("%d %d", &p, &k);
while(k --){
scanf("%d", &c);
tree[p].push_back(c);
}
}
dfs(1, 0);//根节点的索引为1 根节点所在层为0
for(int i=0; i<=maxDepth; ++i){
printf("%d", floor[i]);
if(i!=maxDepth)printf(" ");
}
return 0;
}