List Leaves

原题链接

树（上）课后练习题2

解题思路

又是需要自己找根结点的问题（和之前的思路一样，不是任何结点的孩子那它就是根结点），利用了静态链表的思想，创建结构体数组在读入数据的时候记录每个结点的左右孩子的地址（用数组下标）。

然后进行层序遍历，用STL中的队列queue实现非常方便，这里要求只输出叶子结点，那只要在访问结点（这里访问就是输出其下标）时判断它是否有孩子，没有再输出，否则什么也不做。

PAT中的题目的普遍要求都是输出数据之间用空格分隔，最后不能多一个空格，要注意处理这一点。

代码实现

#include<iostream> //03-树2 
#include<queue>//实现层序遍历 
using namespace std;
const int maxn = 20;
int n; 
bool ischild[maxn];
struct node{
	//-1表示空 
	int lchild;
	int rchild;
}tree[maxn];
void levelOrderTraversal(int root){
	if(root == -1) return ;//空树 
	queue<int> q;
	q.push(root);
	bool first = true;
	while(!q.empty()){
		int top = q.front();
		q.pop();
		//如果是叶子结点输出
		if(tree[top].lchild == -1 && tree[top].rchild == -1){
			if(first){
				first = false;
			}
			else{
				printf(" ");
			} 
			printf("%d", top);
		} 
		if(tree[top].lchild != -1) q.push(tree[top].lchild);
		if(tree[top].rchild != -1) q.push(tree[top].rchild);
	}
}
int main(){
	//建树并且找到树根
	fill(ischild, ischild+maxn, false); 
	scanf("%d", &n);
	getchar();
	char a, b;
	for(int i=0; i<n; i++){
		scanf("%c %c", &a, &b);
		getchar();
		if(a == '-'){
			tree[i].lchild = -1;
		}
		else{
			tree[i].lchild = a-'0';
			ischild[tree[i].lchild] = true;
		}
		if(b == '-'){
			tree[i].rchild = -1;
		}
		else{
			tree[i].rchild = b-'0';
			ischild[tree[i].rchild] = true;
		}
	}
	//找树根
	int root = -1;
	for(int i=0; i<n; i++){
		if(!ischild[i]){
			root = i;
			break;
		} 
	} 
	//进行层序遍历 
	levelOrderTraversal(root);
	return 0; 
}