03-树2 List Leaves（25 分）

03-树2 List Leaves（25 分）

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$ ($\le 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 <stdio.h>
#include <algorithm>
#include <stack>
using namespace std;
int n,m;
struct tree
{
    int right;              ///存放左儿子的值
    int left;

}tree[15];              ///数组下标作为结点
int check[15];
int main()
{
    for(int i=0; i<15; i++)
        check[i]=0;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        char l,r;
        cin>>l>>r;
        if(l=='-' && r=='-')  {              ///如果左孩子和右孩子都不存在的话
            tree[i].left=-1;
            tree[i].right=-1;
            continue;
        }
       if(l=='-')                   ///说明只有左孩子不存在
       {
           tree[i].left=-1;
           tree[i].right=r-'0';
           check[tree[i].right]=1;              ///说明这个结点出现过
           continue;
       }
       if(r=='-')                               ///说明只有右孩子不存在
       {
           tree[i].left=l-'0';
           tree[i].right=-1;
           check[tree[i].left]=-1;
           continue;
       }
       ///说明左右孩子都存在
       tree[i].left=l-'0';
       tree[i].right=r-'0';
       check[tree[i].left]=1;
       check[tree[i].right]=1;
    }
    ///开始寻找树根结点
    ///树根结点特征：该结点不是任何结点的儿子   我们用一个check数组进行标记
    int t;
    for(t=0; t<n; t++)
    {
        if(check[t]==0)
        {
            break;
        }
    }                           ///找到了根节点，开始层序遍历

    int leave=0;
    int rear=0,head=0;
    int que[15];
    que[rear++]=t;                  ///让根节点入队
    while(rear-head)
    {
        int node=que[head++];                   ///队首节点出队
        if(tree[node].left==-1 && tree[node].right==-1)     ///如果是叶子结点
        {
            if(leave)
                cout<<" ";
            cout<<node;
            leave++;
        }
        if(tree[node].left!=-1)
            que[rear++]=tree[node].left;
        if(tree[node].right!=-1)
            que[rear++]=tree[node].right;
    }


    return 0;
}