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

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: Accepted
Take time: 0ms
Take Memory: 168KB
Submit time: 2017-02-07 14:47:43
****************************************************/