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

思路

用静态链表的方式，结构体数组。因为其左右子结点已经告诉我们，可以利用结构体数组创建出树来。

题目要求打印叶子结点，且必须是从上到下，从左到右，那么我们得先找到根结点。在静态链表当中，从sample input 可以看出，3没有出现过，即为根结点。为啥呢？？？因为出现过的结点都是孩子结点，题目说了。

按题目要求的顺序打印，我的第一想法就是用队列，把树的层序遍历改一下，就满足题目要求了。

代码

#include <iostream>
#include <queue>
using namespace std;
struct node{
    int left;
    int right;
};
int a[10];
int main(){
    int n,i,fir=1;
    cin>>n;
    node s[n];
    for(int i=0;i<n;i++){
        char sl,sr;
        cin>>sl>>sr;
        if(sl=='-')
            s[i].left=-1;
        else{
            s[i].left=sl-'0';
            a[s[i].left]=1;
        }
        if(sr=='-')
            s[i].right=-1;
        else{
            s[i].right=sr-'0';
            a[s[i].right]=1;
        }
    }
    for(i=0;i<n;i++)
        if(a[i]==0)
            break;
    queue<int> q;
    q.push(i);
    while(!q.empty()){
        if(s[q.front()].left==-1&&s[q.front()].right==-1){
            fir?cout<<q.front():cout<<' '<<q.front();
            fir=0;
        }
        if(s[q.front()].left!=-1)
            q.push(s[q.front()].left);
        if(s[q.front()].right!=-1)
            q.push(s[q.front()].right);
         q.pop();
    }
    return 0;
}