List Leaves

description

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

思路

结构体数组存树，每个节点两个指针分别指向左右子节点的下标。输出按照层序遍历的方法，判断每个节点是否有左右结点，如果都没有，就输出。注意题中要求最后无空格。

代码

#include<iostream>
#include<queue>
using namespace std;

struct TreeNode											//结点 
{
	int data;
	int left,right;
}t[10];

int BuildTree(TreeNode t[])								//建树 
{
	int n,root=-1;										//根初始化为-1 
	int vis[10]={0};									//标记数组  注意初始化   我以为定义的是全局变量忘了初始，卡好久 
	char a,b;
	cin>>n;
	if(n)												//如果n是0，就是空树，根为-1 
	{
		for(int i=0;i<n;i++)
		{
			t[i].data=i;
			cin>>a>>b;						
			if(a=='-')									//如果没有子树，就将指向设为-1 
				t[i].left=-1;
			else
			{
				t[i].left=(int)(a-'0');					//转换 
				vis[t[i].left]=1;						//标记   
			}
			if(b=='-')
				t[i].right=-1;
			else
			{
				t[i].right=(int)(b-'0');
				vis[t[i].right]=1;
			}
		}
		int i;
		for(i=0;i<n;i++)
			if(!vis[i])									//最后没被标记的即为根节点 
				break;
		root=i;
	}
	return root;
}

void OutPutLeaves(int bt)								//输出叶节点 
{
	queue<int>q;
    queue<int>ans;										//存储叶节点 
	int b=bt;
	q.push(b);
	while(q.size())
	{
		b=q.front();
		q.pop();
		if(t[b].left==-1&&t[b].right==-1)
			ans.push(t[b].data);
		if(t[b].left!=-1)
			q.push(t[b].left);
		if(t[b].right!=-1)
			q.push(t[b].right);	
	}
    while(ans.size()>=2)								//题中要求最后无空格 单独输出 
    {
        int tmp=ans.front();
        ans.pop();
        cout<<tmp<<" ";
    }
    cout<<ans.front();
}

int main()
{
	int r=BuildTree(t);
	OutPutLeaves(r);
	return 0;
}