List Leaves-----输出叶子节点-蒲公英云

7-1 List Leaves （30 point(s))

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 (≤) 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.

8 1 - - - 0 - 2 7 - - - - 5 - 4 6 4 1 5（最后没空格）

有必要先解释下题目的意思，输入n个结点，然后按顺序（0-n）输入每个结点的左右孩子，第二行是0的左右孩子，第三行是1的左右孩子，依次类推，-则为空。

首先先考虑大概的框架，确定主函数

方法：创建一棵树，接收输入的数据并转化为树结构，按层（这就得先找到第一层吧即根节点）遍历树输出叶子结点

int main()
{
    int root;
    root=createtree();  //创建即读入数据并转换为树结构接收根的下标 
    display(root);  //按层遍历并输出叶子结点 
    return 0;
}

main

定义一棵树的每个结点，创建一棵树

方法：每个结点包含了他们的左右孩子和父结点，这里会涉及到用什么类型，的把（为了下面找整棵树的根结点提供便利），用一个每个元素为结点类型的数组来当作一棵树，这里定义为全局变量也有它的好处

struct node
{  //定义树结点 
    int f,lchild,rchild;  //定义左右孩子及父 
    //char ---
}t[15]; //定义树结构体

tree node

细化接收数据+找根节点的函数createtree（）

方法：输出n个结点，为了能够找到父结点我们先把所有的结点的父结点赋值为-1，用for循环输入n个结点的信息，输入两个字符，逐一判断ch1如果不是-就成为t【i】的左孩子，并把ch1的父结点修改为i，否则的话就把i的左孩子赋值为-1（我们定义输入的是字符型的话如果结点内的元素用整型的话的话要注意把字符型的输入转换为整型数字），第二个字符ch2的判断也一样。接着用for循环通过判断每个结点的父结点是否为-1来判断根结点，如果为-1就跳出整个循环，只有根结点是没爸的，然后返回根结点的下标（数值），先输出检验一下。这里我因为粗心出了很多问题例如输入两个字符放在了循环外，如果某结点的父为-1就return i，没有用括号，这样为什么不行呢……

int createtree()
{  //输入数据转换为树结构并返回跟结点的下标 
    int n,root;
    cin>>n;  //输入结点个数 
    char ch1,ch2;
    //cin>>ch1>>ch2;
    for(int i=0;i<n;i++)
        t[i].f=-1;  //初始所有的根结点为-1 
    for(int i=0;i<n;i++)
    {  //按下标顺序（根结点的数据）输入数据并形成树 
        cin>>ch1>>ch2;
        if(ch1!='-')
        {  //如果当前的左孩子字符不为- 
            t[i].lchild=ch1-'0'; //输入为字符型应转化为整形 
            t[ch1-'0'].f=i;  //改变父（下标）的值 
        }
        else
        t[i].lchild=-1;  //如果左孩子为-就给值为-1 
        if(ch2!='-')
        {
            t[i].rchild=ch2-'0';
            t[ch2-'0'].f=i;
        }
        else
        t[i].rchild=-1;
    }    
    for(int i=0;i<n;i++)
        {  //找到整棵树的根结点，只有根结点是没有父的 
            if(t[i].f==-1)  
            {
                root=i;
                break;
            } 
            //if---
            //return i;
        }
        //cout<<root;
        return root;    
 }

createtree

细化转化数据+输出叶子结点的函数display（）

方法：先前我们是按照结点的数据（0-n）输入存入数组，现在按（树结构）层次遍历输出（有先后），我们就需要把输入的数据重新变成一棵二叉树（从根到最后），再按从上到下从左到右的遍历顺序输出叶子结点，那我们要用什么方式去转换呢，队列的特点就是先进先出，如果我们要把按顺序的数组转换为从根开始的二叉树（可以通过每个结点的左右孩子把原来的数组重新存入一个队列）先进队的叶子就先出队。按照（定义一个数组作为队）队列设置头尾指针，利用找到的根结点（入队作为第一个元素，队尾指针后移为最后元素的下一位）开始找他的左右孩子，如果左右孩子相等就输出（叶子=队头元素），若不相等但又存在（不等于-1）就左，右孩子就依次（队尾）入队，再找左孩子的左右孩子判断相等……以此类推，那我们就可以用一个循环来实现，条件（head小于rear）就是我们在循环体内改变的变量头尾指针（入队出队都会修改）。

void display(int k)
{  //输出叶子结点，按层次遍历实际为队列先进先出 
    int flag=1;  //为了格式正确 
    int head=0,rear=0;
    int a[15];  //用作队列 
    a[rear++]=k;  //第一个元素为根结点 
    while(head<rear)
    {  // 
        int num=a[head++];  //用一个num来代替每一个根结点 
        if(t[num].lchild==-1 && t[num].rchild==-1)
        {  //如果当前根结点的左右孩子为空就输出这个叶子结点 
            if(flag)
            cout<<num;
            else
            cout<<" "<<num;
            flag=0;  //为了实现输出格式 
        }
        if(t[num].lchild!=-1)
        {  //如果当前根结点的左孩子不为空就从队尾入队 
            a[rear++]=t[num].lchild;
        }
        if(t[num].rchild!=-1)
        {  //如果当前根结点的右孩子不为空就从队尾入队 
            a[rear++]=t[num].rchild;
        }
    }
}

display

最后还有一个格式问题（最后没有空格），这个就用老师讲的方法，用一个flag标记第一个输出只输出数据并修改flag的值，之后就输出数据+空格。

刚学习树，这道题刚开始我做的时候真的是一脸懵逼，首先要怎么把树的知识用上（接收数据并转换为树结构），怎么找到并输出叶子，参考了网上的代码一步步理解，看见说是用队列的思想我也是不太理解，就自己一步步在草稿纸上推发现代码上的好像还真是队列的特点，我的感受就是不理解的千万不要一昧地跟着别人的代码copy，要慢慢来今天不会明天就可能能懂了。

老师讲了题之后我们可以用stl来直接使用队列

#include <iostream>
#include <queue>
using namespace std;
typedef struct
{
    int lchild,rchild;
}node;
int input(node t[])
{
    char ch1,ch2;
    int n;
    cin>>n;
    bool test[n]={
        false};
    for(int i=0;i<n;i++)
    {
        cin>>ch1>>ch2;
        if(ch1!='-')
        {
            t[i].lchild=ch1-'0';
            test[ t[i].lchild ]=true;
        }
        else t[i].lchild=-1;
        if(ch2!='-')
        {
            t[i].rchild=ch2-'0';
            test[ t[i].rchild ]=true;
        }
        else t[i].rchild=-1;
    }
    for(int j=0;j<n;j++)
    {
        if(!test[j])
        return j;
    }
}
void display(node t[],int r)
{
    queue<int> q;
    int temp,flag=1;
    q.push(r);
    while(!q.empty())
    {
        temp=q.front();
        q.pop();
        if(temp!=-1)
        {
            if(t[temp].lchild==-1 && t[temp].rchild==-1)
            {
                if(flag)
                cout<<temp;
                else
                cout<<" "<<temp;
                flag=0;
            }
            if(t[temp].lchild!=-1)
            q.push(t[temp].lchild);
            if(t[temp].rchild!=-1)
            q.push(t[temp].rchild);
        }
    }
}
int main()
{
    node t[15];
    int root;
    root=input(t);
    display(t,root);
    return 0;
 }