7-6 层次遍历
给定二叉树的包含虚结点的先序遍历序列信息,按层次顺序给出遍历的结果。
输入格式:
首先输入一个整数T,表示测试数据的组数,然后是T组测试数据。每组测试数据在一行中输入一个字符串(不含空格且长度不超过80),表示二叉树的先序遍历序列(其中@表示虚结点)。
输出格式:
对于每组测试,输出层次遍历的结果。
输入样例:
1
ABD@@EG@@@C@F@@
输出样例:
ABCDEFG
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
```c
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef char TElemType;
const int MAXSIZES = 50;
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
typedef BiTree QElemType;
typedef struct {
QElemType data[MAXSIZES];
int front;
int rear;
}SqQueue;
void CreateBiTree(BiTree *T)
{
TElemType ch;
scanf("%c", &ch);
if (ch == '@')
{
*T = NULL;
}
else
{
*T = (BiTree) malloc(sizeof(BiTNode));
if (!T)
{
exit(0);
}
(*T)->data = ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
void InitQueue(SqQueue *Q)
{
Q->front = Q->rear = 0;
}
void EnQueue(SqQueue *Q, QElemType q)
{
if ((Q->rear + 1) % MAXSIZES == Q->front)
return;
Q->data[Q->rear] = q;
Q->rear = (Q->rear + 1) % MAXSIZES;
}
void DeQueue(SqQueue *Q, QElemType *q)
{
if (Q->front == Q->rear)
return;
*q = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXSIZES;
}
void LevelOrder(BiTree T)
{
SqQueue Q;
InitQueue(&Q);
BiTree p;
EnQueue(&Q, T);
while(Q.front != Q.rear)
{
DeQueue(&Q, &p);
printf("%c", p->data);
if (p->lchild != NULL)
{
EnQueue(&Q, p->lchild);
}
if (p->rchild != NULL)
{
EnQueue(&Q, p->rchild);
}
}
}
int main()
{
int n;
scanf ("%d", &n);
while (n--)
{
BiTree t;
CreateBiTree(&t);
LevelOrder(t);
}
return 0;
}
```