题目描述 编一个程序，读入用户输入的一串先序遍历字符串，根据输入建立一棵二叉树, 并输出该二叉树的层次遍历序列。层次遍历是指逐层访问，每一层又按从左到右的次序访问结点。 输入 输入包括1行字符串，长度不超过100。 输出 输出二叉树的层次遍历序列。每个结点先输出一个空格，然后再跟着输出结点的数据。 样例输入 Copy 12##3## 样例输出 Copy 1 2 3
#include <iostream> #include <cstdio> #include <malloc.h> using namespace std; #define MAXSIZE 100 typedef struct BiTnode { char data; struct BiTnode *lchild,*rchild; }BiTNode,*BiTree; typedef struct SQueue { BiTree data[MAXSIZE]; int front,rear; }SQueue,*Queue; BiTree creatTree(BiTree T) { char ch; T=(BiTree)malloc(sizeof(BiTNode)); scanf("%c",&ch); if(ch=='#') return 0; T->data=ch; T->lchild=creatTree(T->lchild); T->rchild=creatTree(T->rchild); return T; } void InitQueue(Queue Q) { Q -> front = Q -> rear = 0; } int IsEmptyQueue(Queue Q) { return Q -> rear == Q -> front?1:0; } void EnQueue(BiTree T,Queue Q) { if((Q -> rear+1) % MAXSIZE == Q -> front) { printf("Queue is fulled!\n"); return ; } Q->rear=(Q->rear+1)%MAXSIZE; Q->data[Q->rear]=T; } BiTree Gethead(Queue Q) { if(IsEmptyQueue(Q)) return 0; BiTree T; T=Q ->data[(Q ->front+1) % MAXSIZE]; Q ->front=(Q ->front+1) % MAXSIZE; return T; } void LevelOrder(BiTree T)//层次遍历 { SQueue Q ; BiTree S ; if(!T) return ; InitQueue(&Q); EnQueue(T,&Q); while(!IsEmptyQueue(&Q)) { S=Gethead(&Q); printf(" %c",S->data); if(S->lchild!=NULL) EnQueue(S->lchild,&Q); if(S->rchild!=NULL) EnQueue(S->rchild,&Q); } } int main() { BiTree tree; tree=creatTree(tree); LevelOrder(tree); return 0; }