题目

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

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.

题解

• 首先理解题意
• 题目的意思是给你一棵树，让你输出每层的叶子节点个数
• 那很明显就是广度优先遍历了

数据结构

• members 列表记录所有成员
• 下标是成员id
• 值是一个列表，包含这个成员的所有孩子的id
• level 列表记录每层的叶子节点个数
• 下标是层数
• 值是叶子节点个数
• temp_num是计算这层的叶子结点的中间变量

算法

• 详细讲讲广度优先遍历的内容
• 广度优先遍历要配合先入先出的队列，队列初始化为拥有一个根节点。队列存放的所有节点都拥有相同的层数。
• 当队列不为空的时候
• 记录现在队列的长度
• temp_num 清零
• 遍历现在这个队列
• 遍历队列里每一项的所有孩子
• 如果孩子是没有孩子的，temp_num + 1
• 否则，添加到队列中
• level添加temp_num项
• 最后输出level即可
• 注意只有一个节点的特殊情况！