[数据结构与算法]列出叶结点

本题难点在于找根，根节点不是任何节点的子节点，故，根节点不会再0~N-1行中出现,找到根后建树，利用队列对树层序遍历找叶节点，找根是重点！！！！！！！
对于给定的二叉树，本题要求你按从上到下、从左到右的顺序输出其所有叶节点。

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

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

输入样例：
8
1 -

0 -
2 7

5 -

4 6
结尾无空行

输出样例：
4 1 5
结尾无空行

#include <bits/stdc++.h>
using namespace std;
typedef int elemtype;
int n,root,i;
int Node[100],L_Rchild[100][2];//node数组下标为树节点，值标记是否为根节点，根节点为0，否为1.
typedef struct BiTNode
{
    elemtype data;
    BiTNode *Lchild;
    BiTNode *Rchild;
}BiTNode,*BiTree;
void FindRoot()//存储左右孩子并且找到根节点放入root中。
{              //找出根节点的值，根节点不是任何节点的子节点，故，根节点不会再0-N行中出现
    char thL,thR;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>thL>>thR;
        if(thL=='-') L_Rchild[i][0]=-1;
        else L_Rchild[i][0]=thL-'0';
        if(thR=='-') L_Rchild[i][1]=-1;
        else L_Rchild[i][1]=thR-'0';
        Node[thL-'0']=1,Node[thR-'0']=1;
    }
    for(i=0;i<n;i++)//找根
        if(!Node[i]) break;
    root=i;
}
BiTree creatTree(int Root)//先序递归建树。
{
    if(Root==-1) return NULL;
    BiTree T=(BiTree)malloc(sizeof(BiTNode));
    T->data=Root;
    T->Lchild=creatTree(L_Rchild[Root][0]);
    T->Rchild=creatTree(L_Rchild[Root][1]);
    return T;
}
void LevelVist(BiTree T)//层序遍历树，输出叶节点。
{
    int j=0;
    queue<BiTree> Q;
    Q.push(T);
    while(!Q.empty())
    {
        BiTree t=Q.front();
        if(t->Lchild) Q.push(t->Lchild);
        if(t->Rchild) Q.push(t->Rchild);
        if(t->Lchild==NULL&&t->Rchild==NULL&&j==0) {cout<<t->data;j++;}
        else if(t->Lchild==NULL&&t->Rchild==NULL) cout<<" "<<t->data;
        Q.pop();
    }
}
int main()
{
    FindRoot();
    BiTree T=creatTree(root);
    LevelVist(T);
    return 0;
}