PTA 二叉树的层次遍历
阅读原文时间:2023年07月15日阅读:1

6-6 二叉树的层次遍历 (6 分)

本题要求实现给定的二叉树的层次遍历。

函数接口定义:

void Levelorder(BiTree T);

T是二叉树树根指针,Levelorder函数输出给定二叉树的层次遍历序列,格式为一个空格跟着一个字符。

其中BinTree结构定义如下:

typedef char ElemType;
typedef struct BiTNode
{
   ElemType data;
   struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

裁判测试程序样例:

#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;
typedef struct BiTNode
{
   ElemType data;
   struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

BiTree Create();/* 细节在此不表 */

void Levelorder(BiTree T);

int main()
{
   BiTree T = Create();
   printf("Levelorder:"); Levelorder(T); printf("\n");
   return 0;
}
/* 你的代码将被嵌在这里 */

输出样例(对于图中给出的树):

Levelorder: A B C D F G

void Levelorder(BiTree T){
int max=10;
BiTree a[max];
BiTree t=NULL;
int front=0,rear=0;
if(T!=NULL){
a[rear]=T;
rear=(rear+1)%max;
}
while(rear!=front){
t=a[front];
front=(front+1)%max;
printf(" %c",t->data);
if(t->lchild!=NULL){
a[rear]=t->lchild;
rear=(rear+1)%max;
}
if(t->rchild!=NULL){
a[rear]=t->rchild;
rear=(rear+1)%max;
}
}

}