浙大数据结构的编程题——03-树2 List Leaves

树2. List Leaves 二叉树的层序遍历

Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤10) which is the total number of nodes in the tree – and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a “-” will be put at the position. Any pair of children are separated by a space.

Output Specification:

For each test case, print in one line all the leaves’ indices in the order of top down, and left to right. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.

Sample Input:

8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

Sample Output:

4 1 5

思路

输入的数是以静态链表表示的，我们以结构数组形式存储树的。以下是范例输入的数样子。 然后输出是从上往下，自左而右，故输出4 1 5.

解题思路为层序遍历，当遇到一个叶节点（没有子节点的结点）时，输出当前位置。直到遍历完整棵树。

层序遍历

队列实现：遍历从根结点开始，首先将根结点入队，然后开始执行循环：结点出队、访问该结点、其左右儿子入队。

C++中STL库中含有deque顺序容器结构可用， 另外STL中海油三个顺序容器适配器：stack、queue和priority_queue.其中stack、queue的默认基础容器为deque，priority_queue由于需要随机访问，其基础容器为vector。

Code

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <iterator>
#include <math.h>
#include <stack>
#include <queue>
using namespace std;



int main() {
	//begin:			end:
	ios::sync_with_stdio(false);
	struct Node
	{
		int left, right;
	};
	int N;
	cin >> N;
	vector<Node> tree(N);
	//built tree
	int sum = 0;
	for (int i = 0; i < N; i++) {
		string cl, cr;
		cin >> cl >> cr;
		if (cl != "-") {
			tree[i].left = stoi(cl);
			sum += tree[i].left;
		}
		else {
			tree[i].left = -1;
		}
		if (cr != "-") {
			tree[i].right = stoi(cr);
			sum += tree[i].right;
		}
		else {
			tree[i].right = -1;
		}
	}
	int root = (0 + N - 1)*N / 2 - sum;//树的根结点

	//接下去层序遍历
	queue<int> Q;
	vector<int> out;

	Q.push(root);
	
	while (!Q.empty()) {
		Node tmp = tree[Q.front()];
		if (tmp.left != -1) {
			Q.push(tmp.left);
		}
		if (tmp.right != -1) {
			Q.push(tmp.right);
		}
		if ((tmp.left == -1) && (tmp.right == -1)) {
			out.push_back(Q.front());
		}
		Q.pop();
	}

	//输出
	for(int i = 0; i < out.size()-1; i++) {
		printf("%d ", out.at(i));
	}
	printf("%d", out.back());

	return 0;
}