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

题目描述

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

输入

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

输出

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

示例输入

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

示例输出

abcdefg xnuli #include <stdio.h> #include <stdlib.h> #include <string.h> typedef char telemtype; typedef char status; typedef struct BiTNode {     telemtype data;     struct BiTNode *lchild, *rchild; }*BiTree; typedef BiTree QElemType;//注意此类型应定义为BiTree  typedef char Status;  typedef struct QNode；  {      QElemType data;      QNode *next;  } QNode, *Queueptr; typedef struct//定义队列  {      Queueptr  front;      Queueptr  rear;  } LinkQueue; char str[55]; int i; status create(BiTree &T)//生成树； {     if(str[i++]==',') T=NULL;     else     {         T = (BiTNode *) malloc (sizeof(BiTNode));         if(!T) exit(0);         T->data = str[i-1];         create(T->lchild);         create(T->rchild);     }     return 1; } Status InitQueue (LinkQueue &Q)//队的初始化；‘  {      Q.front = Q.rear = (Queueptr)malloc(sizeof(QNode));      if (!Q.front) exit (0);      Q.front->next = NULL;      return 1;  } Status EnQueue (LinkQueue &Q, QElemType e)//进队；  {      Queueptr p;      p = (Queueptr) malloc (sizeof (QNode));      if (!p)  exit (0);      p->data = e;      p->next = NULL;      Q.rear->next = p;      Q.rear = p;      return 1;  } Status DeQueue (LinkQueue &Q,   QElemType &e)//出队；  {      Queueptr p;      if (Q.front == Q.rear)          return 0;      p = Q.front->next;      e = p->data;      Q.front->next = p->next;      if (Q.rear == p)          Q.rear = Q.front;      free (p);      return 1;  } Status QueueEmpty(LinkQueue Q)//判断是否为空队；  {      if(Q.front==Q.rear)          return 1;      else          return 0;  } void Traverse(BiTree T)//二叉树的层次遍历序列； {     LinkQueue Q;     //BiTree p;     //p=T;     InitQueue(Q);     if(T)         EnQueue(Q, T);     while(!QueueEmpty(Q))     {         DeQueue(Q,T);         printf("%c", T->data);         if(T->lchild)             EnQueue(Q, T->lchild);         if(T->rchild)             EnQueue(Q, T->rchild);     } } int main() {     BiTree T;     int t;     scanf("%d",&t);     for(int j=0;j<t;j++)     {         scanf("%s",str);         i=0;         create(T);//树的建立；         Traverse(T);//二叉树的层次遍历序列；         printf("\n");     } } #include<iostream> #include<cstring> #include<queue> #include<cstdio> #include<algorithm> using namespace std; typedef struct Bnode {      char data;      Bnode *rchild,*lchild; }*BiTree,Bnode; char str[55]; int i; void create(BiTree &T) {       if(str[i++]==',') T=NULL;       else       {             T=new Bnode;              if(!T) exit(0);              T->data=str[i-1];              create(T->lchild);              create(T->rchild);       } } void  cengci(BiTree &T) {      int out=0,in=0;      BiTree q[100];//存树的队列;      if(T)      q[in++]=T;      while(in>out)      {           if(q[out])           {                printf("%c",q[out]->data);                q[in++]=q[out]->lchild;                q[in++]=q[out]->rchild;           }           out++;      } } void Traverse(BiTree T) {      queue<BiTree> q;      BiTree p=NULL;      if(T)      {          q.push(T);      }      while(!q.empty())      {           p=q.front();           q.pop();           cout<<p->data;           if(p->lchild)             q.push(p->lchild);           if(p->rchild)             q.push(p->rchild);      } } int main() {     BiTree T;     int t;     while(cin>>t)     {           for(int j=0;j<t;j++)     {          scanf("%s",str);          T=NULL;           i=0;           create(T);           //cengci(T);           Traverse(T);           cout<<endl;     }     }   return 0; }