基础实验 4-2.2 列出叶结点（25 分）

对于给定的二叉树，本题要求你按从上到下、从左到右的顺序输出其所有叶节点。

输入格式：

首先第一行给出一个正整数 N（≤10），为树中结点总数。树中的结点从 0 到 N−1 编号。随后 N 行，每行给出一个对应结点左右孩子的编号。如果某个孩子不存在，则在对应位置给出“-”。编号间以 1 个空格分隔。

输出格式：

在一行中按规定顺序输出叶节点的编号。编号间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

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

输出样例：

4 1 5

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int node,i,flag;
struct message{
	char left,right;
	int father=-1,id,rank;
}tree[16];
void makei(int index,int id){
	tree[index].id=id;
	if(tree[index].left!='-')makei(tree[index].left-'0',id*2);
	if(tree[index].right!='-')makei(tree[index].right-'0',id*2+1);
}
int compare(message first,message second){
	return first.id<second.id;
}
int main(){
	scanf("%d",&node);
	for(i=0;i<node;i++)scanf("\n%c %c",&tree[i].left,&tree[i].right);
	for(i=0;i<node;i++){
		if(tree[i].left!='-')tree[tree[i].left-'0'].father=i;
		if(tree[i].right!='-')tree[tree[i].right-'0'].father=i;
		tree[i].rank=i;
	}
	for(i=0;i<node;i++)if(tree[i].father<0){
		makei(i,1);
		break;
	}
	sort(tree,tree+node,compare);
	for(i=0;i<node;i++)if(tree[i].left=='-'&&tree[i].right=='-'){
		if(flag)printf(" ");
		flag=1;
		printf("%d",tree[i].rank);
	}
	return 0;
}

提交结果：