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

Description

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

Input

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

Output

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

Sample

Input

2
abd,,eg,,,cf,,,
xnl,,i,,u,,

Output

abcdefg
xnuli

Hint

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
char st[50];
int i;
struct Tnode
{
    char d;
    Tnode *l,*r;
};
Tnode *CreatTree()
{
    Tnode *p;
    if(st[i++]==',')
        p= NULL;
    else
    {
        p=new Tnode;
        p->d=st[i-1];
        p->l=CreatTree();
        p->r=CreatTree();
    }
    return p;
}
void level_order(Tnode *p)
{
    queue<Tnode *>q;
    if(p)
        q.push(p);
    while(!q.empty())
    {
        Tnode *k=q.front();
        cout<<k->d;
        if(k->l)
            q.push(k->l);
        if(k->r)
            q.push(k->r);
        q.pop();
    }
}
int main()
{
    int t;
    while(cin>>t)
    {
        while(t--)
        {
            i=0;
            cin>>st;
            Tnode *root=CreatTree();
            level_order(root);
            cout<<endl;
        }
    }
    return 0;
}

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3  
 4 typedef struct node
 5 {
 6     char data;
 7     struct node *lc;
 8     struct node *rc;
 9 } BiTree;
10  
11 int i;
12  
13 BiTree *Creat(char s[])
14 {
15     BiTree *T;
16     if(s[++i] != ',')
17     {
18         T = (BiTree*)malloc(sizeof(BiTree));
19         T->data = s[i];
20         T->lc = Creat(s);
21         T->rc = Creat(s);
22     }
23     else
24         T = NULL;
25     return T;
26 }
27 /*建立数组，先存入根节点，输出根节点的同时存入左右孩子。如此循环直到遍历完成*/
28 void Travel(BiTree *T)
29 {
30     BiTree *temp[100];
31     int in = 0, out = 0;
32     temp[in++] = T;
33     while(in > out)
34     {
35         if(temp[out])
36         {
37             printf("%c", temp[out]->data);
38             temp[in++] = temp[out]->lc;
39             temp[in++] = temp[out]->rc;
40         }
41         out++;
42     }
43 }
44  
45 int main()
46 {
47     int t;
48     BiTree *T;
49     char s[100];
50     scanf("%d", &t);
51     while(t--)
52     {
53         scanf("%s", s);
54         i = -1;
55         T = Creat(s);
56         Travel(T);
57         printf("
");
58     }
59     return 0;
60 }