PAT 1004 Counting Leaves

  1. 1. Counting Leaves
  2. 2. 思路

Counting Leaves

1004 Counting Leaves

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:

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:

1
2
2 1
01 1 02

Sample Output:

1
0 1

题目大意: 给定一颗树,从根节点开始依次输出当前层中叶子节点的个数.树的根节点是01

思路

每个成员的孩子个数不确定,不能简单用二叉树实现.

考虑一般树的表示方法

  1. 孩子兄弟表示法
  2. 双亲表示法
  3. 孩子表示法

题目直接给出的是父子关系,孩子兄弟表示法不太合适,排除. 双亲表示法由孩子找双亲比较方便,孩子表示法由双亲找孩子比较方便,所以采用孩子表示法.

采用数组来表示节点的孩子,那么所有的节点可以用一个二维数组表示.因为N<100,所以开个int[101][101]就够用了.我就偷个懒,使用STL的vector

接下来需要找出一层中叶节点的个数.假设已经有了当前层节点的下标,叶子节点的个数可以由遍历很容易的统计.一轮遍历完成后会得到下一层节点的下标.这样就可以一直持续下去了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> TriversalTree(vector<vector<int>> tree, vector<int> parents, int& leaf)
{
	vector<int> result;
	leaf = 0;
	for (int i = 0; i < parents.size(); i++)
	{
		int index = parents[i];
		auto node = tree[index];
		if (node.size() == 0)
		{
			leaf++;
		}
		else 
		{
			for (auto it = node.begin(); it != node.end(); it++)
			{
				result.push_back(*it);
			}
		}
	}
	return result;
}

给出第一层的下标即可开始遍历了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> TriversalTree(vector<vector<int>> tree, vector<int> parents, int& leaf)
{
	vector<int> result;
	leaf = 0;
	for (int i = 0; i < parents.size(); i++)
	{
		int index = parents[i];
		auto node = tree[index];
		if (node.size() == 0)
		{
			leaf++;
		}
		else 
		{
			for (auto it = node.begin(); it != node.end(); it++)
			{
				result.push_back(*it);
			}
		}
	}
	return result;
}
int main()
{
	int n;
	cin >> n;
	if (n == 0)
	{
		return 0;
	}
	vector<vector<int>> tree = vector<vector<int>>(n + 1);
	int non_leaf;
	cin >> non_leaf;
	for (int i = 0; i < non_leaf; i++)
	{
		int root;
		int num;
		int child;
		cin >> root;
		cin >> num;
		for (int j = 0; j < num; j++)
		{
			cin >> child;
			tree[root].push_back(child);
		}
	}
	vector<int> layer;
	layer.push_back(1);
	int leaf = 0;
	layer = TriversalTree(tree, layer, leaf);
	printf("%d", leaf);
	while (layer.size() > 0) {
		layer = TriversalTree(tree, layer, leaf);
		printf(" %d", leaf);
	};
	printf("\n");
	return 0;
}
PAT
prev： next：