PAT_A1004#Counting Leaves

小鱼儿 2021-12-20 06:34 177阅读 0赞

### Source: ###

> [PAT A1004 Counting Leaves (30 分)][PAT A1004_Counting Leaves_30]

### Description: ###

> A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.

### Input Specification: ###

> Each input file contains one test case. Each case starts with a line containing 0, the number of nodes in a tree, and M (<), 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.

### Output Specification: ###

> 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.

### Sample Input: ###

>     2 1
>     01 1 02

### Sample Output: ###

>     0 1

### Keys: ###

*  [二叉树的建立和遍历][Link 1]

### Code: ###

1 /*
     2 time: 2019-06-28 16:47:33
     3 problem: PAT_A1004#Counting Leaves
     4 AC: 16:22
     5 
     6 题目大意：
     7 统计各层的叶子结点个数
     8 输入：
     9 第一行给出，结点数N<100，分支结点数M
    10 接下来M行，结点id，孩子数k，孩子id（1~n，root==1）
    11 多组输入样例
    12 
    13 基本思路：
    14 遍历并记录各层叶子结点数即可
    15 */
    16 #include<cstdio>
    17 #include<vector>
    18 using namespace std;
    19 const int M=110;
    20 vector<int> tree[M];
    21 int leaf[M],level=0;
    22 
    23 void Travel(int root, int hight)
    24 {
    25     if(tree[root].size()==0)
    26     {
    27         if(hight > level)
    28             level = hight;
    29         leaf[hight]++;
    30         return;
    31     }
    32     for(int i=0; i<tree[root].size(); i++)
    33         Travel(tree[root][i],hight+1);
    34 }
    35 
    36 int main()
    37 {
    38 #ifdef ONLINE_JUDGE
    39 #else
    40     freopen("Test.txt", "r", stdin);
    41 #endif // ONLINE_JUDGE
    42 
    43     int n,m;
    44     while(~scanf("%d", &n))
    45     {
    46         level=0;
    47         for(int i=1; i<=n; i++){
    48             tree[i].clear();
    49             leaf[i]=0;
    50         }
    51         scanf("%d", &m);
    52         for(int i=0; i<m; i++)
    53         {
    54             int id,k,kid;
    55             scanf("%d%d", &id,&k);
    56             for(int j=0; j<k; j++)
    57             {
    58                 scanf("%d", &kid);
    59                 tree[id].push_back(kid);
    60             }
    61         }
    62         Travel(1,0);
    63         for(int i=0; i<=level; i++)
    64             printf("%d%c", leaf[i], i==level?'\n':' ');
    65 
    66     }
    67 
    68     return 0;
    69 }

转载于:https://www.cnblogs.com/blue-lin/p/11103632.html

[PAT A1004_Counting Leaves_30]: https://pintia.cn/problem-sets/994805342720868352/problems/994805521431773184
[Link 1]: https://www.cnblogs.com/blue-lin/p/11102341.html