数据结构实验之二叉树五：层序遍历

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

已知一个按先序输入的字符序列，如abd,,eg,,,cf,,,(其中,表示空结点)。请建立二叉树并求二叉树的层次遍历序列。

Input

输入数据有多行，第一行是一个整数t (t<1000)，代表有t行测试数据。每行是一个长度小于50个字符的字符串。

Output

输出二叉树的层次遍历序列。

Sample Input

2

abd,,eg,,,cf,,,

xnl,,i,,u,,

Sample Output

abcdefg

xnuli

PS：如果对二叉树的遍历没有了解的话请先看我的另一篇博客

#include 
    
     #include 
     
      #include 
      
       typedef struct tree{    char data;    struct tree *l,*r;}tree;int i;char s[55];tree *newtree(){    tree *t;    t = (tree*)malloc(sizeof(tree));    t->l = t->r = NULL;    return t;}tree *creat() //根据所给的遍历顺序建树{    tree *t = newtree();    if(s[i++]==',')        return NULL;    t->data = s[i-1];    t->l = creat();    t->r = creat();    return t;}void show(tree *t) //层序遍历{    tree *q[55],*t1;  //用q[]来模拟队列    int front,base;  //队列的首和尾    front = base = 0;    if(t)    {        q[base++] = t;    }    while(front!=base) //当队首与队尾相等时队伍为空    {        t1 = q[front++];        printf("%c",t1->data);        if(t1->l)            q[base++] = t1->l;        if(t1->r)            q[base++] = t1->r;    }}int main(){    tree *t;    int k;    scanf("%d",&k);    while(k--)    {        scanf("%s",s);        i = 0;        t = newtree();        t = creat();        show(t);        printf("\n");    }    return 0;}