前言

从左到右输出叶子结点，挺简单的，用层序遍历就可以了

题目

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

输入格式

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.

输出格式

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.

样例

输入样例

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

输出样例

4 1 5

思路

挺简单的...用数组存储，建立队列层序输出。

实现

代码

#include<iostream>
using namespace std;

const int MaxSize = 10;

void myInput(int a[][2], int n) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 2; j++) {
			char temp;
			cin >> temp;
			if (temp >= ‘0‘ && temp <= ‘9‘)
				a[i][j] = temp - ‘0‘;
			else
				a[i][j] = -1;
		}
	}
}

int myFindRoot(int a[][2], int n) {
	int flag[MaxSize] = { 0, };
	for (int i = 0; i < n; i++) {
		if (a[i][0] != -1)
			flag[a[i][0]] = 1;
		if (a[i][1] != -1)
			flag[a[i][1]] = 1;
	}
	int res;
	for (int i = 0; i < n; i++)
		if (flag[i] == 0)
			res = i;
	return res;
}

int main() {
	int child[MaxSize][2];
	int num;
	cin >> num;
	myInput(child, num);
	int root = myFindRoot(child, num);

	int  queue[MaxSize];				//够大就不用按照循环列表处理了
	int front, rear;
	front = rear = 0;				//队空条件
	queue[rear++] = root;			        //第一个元素入队
	int input_flag = 0;                             //为了输出格式要求
	while (front != rear) {			        //层序遍历
		if (child[queue[front]][0] == -1 && child[queue[front]][1] == -1) {        //判定叶结点，如果是叶结点，输出
			if (input_flag == 1)
				cout << " ";
			cout << queue[front];
			input_flag = 1;
		}
		if (child[queue[front]][0] != -1)       //左孩子入队
			queue[rear++] = child[queue[front]][0];
		if (child[queue[front]][1] != -1)       //有孩子出队
			queue[rear++] = child[queue[front]][1];
		front++;		                //出队
	}
	return 0;
}

List Leaves

原文：https://www.cnblogs.com/Za-Ya-Hoo/p/12714893.html