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

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

TimeLimit: 1000MS Memory Limit: 65536KB

SubmitStatistic

PRoblem Description

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

Input

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

Output

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

Example Input

2

abd,,eg,,,cf,,,

xnl,,i,,u,,

Example Output

abcdefg

xnuli

Hint

Author

 xam

#include<string.h>#include<stdio.h>#include<stdlib.h>#include<algorithm>#include<queue>#include<iostream>using namespace std;typedef struct node{   char data;   struct node*l;   struct node*r;}tree;tree *creat(char *&ss){   if(*ss==',')   {   ss++;   return NULL;   }  tree*p;  p = (tree*)malloc(sizeof(tree));  p->data = *ss++;  p->l = creat(ss);  p->r = creat(ss);  return p;}void lastout(tree*p){   if(p)   {       lastout(p->l);       lastout(p->r);       printf("%c",p->data);   }}void inout (tree*p){   if(p)   {     inout(p->l);     printf("%c",p->data);     inout(p->r);   }}int num;void sumyz(tree*p){   if(p)   {     if(p->l==NULL&&p->r==NULL)     {        num++;     }     sumyz(p->l);     sumyz(p->r);   }}int deep(tree*p){     if(!p)     return 0;     else     {        return (max(deep(p->l),deep(p->r))+1);     }}void ccout(tree*root){   queue<tree *>q;   tree* p = NULL;   if(root)   {      q.push(root);   }   while(!q.empty())   {      p = q.front();      q.pop();      cout<<p->data;      if(p->l)      {         q.push(p->l);      }      if(p->r)      {         q.push(p->r);      }   }}int main(){   char ss[52],*p;   int o;   cin>>o;   while(o--)   {     scanf("%s",ss);     p = ss;     tree* root;     root = creat(p);     ccout(root);     cout<<endl;   }}/***************************************************User name: jk160505徐红博Result: AcceptedTake time: 0msTake Memory: 168KBSubmit time: 2017-02-07 14:47:43****************************************************/