#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MaxSize 10
#define Null -1
#define Tree int//树
struct TreeNode {int data;int left;int right;
} T[MaxSize];   //树的结构数组，树的静态链表表示
typedef struct TreeNode TNode;//队列
typedef struct TreeQueue { //循环队列，用于层序遍历int *queue; //存放结构数组的下标，数组指针int front, rear;
} TQueue;
typedef struct TreeQueue *PtrQueue;//创建队列
PtrQueue CreatQueue() {PtrQueue q=(PtrQueue)malloc(sizeof(TNode)); //声明指向队列的结构指针q->queue=(int*)malloc(MaxSize*sizeof(int)); //创建数组队列q->front=q->rear=0; //声明头尾return q;
}//判空
bool isEmpty(PtrQueue q) {if(q->front==q->rear) {return 1;} else {return 0;}
}//判满
bool isFull(PtrQueue q) {if((q->rear+1)%MaxSize==q->front) {return 1;} else {return 0;}
}//入队
void EnQueue(PtrQueue q, int x) {if(isFull(q))return;else {q->queue[q->rear]=x; //入队q->rear=(q->rear+1)%MaxSize; //尾指针进1}
}//出队
int DeQueue(PtrQueue q) {if(isEmpty(q))return -1;else {int x=q->queue[q->front]; //出队q->front=(q->front+1)%MaxSize; //头指针进1return x;}
}Tree BuildTree(TNode T[], int N);//建树
void LevelOrderTraversal (TNode T[], Tree Root, int N);//层序遍历int main() {int N=0;scanf("%d",&N);//建树Tree Root; //根节点，T[]数组下标Root=BuildTree(T,N);//层序遍历LevelOrderTraversal (T,Root,N);return 0;
}Tree BuildTree(TNode treeNode[], int N) { //建树关键就是找根节点在数组中的位置char cl,cr;Tree Root=Null;if(N) { //如果树非空int check[MaxSize];int i;for(i=0; i<N; i++) {check[i]=0;}for(i=0; i<N; i++) {treeNode[i].data=i;   //data即树的静态链表中data的位置scanf("\n%c %c",&cl,&cr);if(cl!='-') {      //读入左指针treeNode[i].left=cl-'0';check[treeNode[i].left]=1;} else {treeNode[i].left=Null;}if(cr!='-') {      //读入右指针treeNode[i].right=cr-'0';check[treeNode[i].right]=1;} else {treeNode[i].right=Null;}}for(i=0; i<N; i++) {if(!check[i])break; //找根结点在结构数组中的位置}Root=i;}return Root;
}void LevelOrderTraversal (TNode treeNode[], Tree Root, int N) {PtrQueue Q;int t;int num=0;if (Root==-1)return; /* 若是空树则直接返回 */Q = CreatQueue(); /* 创建空队列Q */EnQueue( Q, Root );while ( !isEmpty(Q) ) {num++;t = DeQueue( Q );if((treeNode[t].left==Null)&&(treeNode[t].right==Null)){printf("%d",t);if(num!=N){printf(" ");}}if ( treeNode[t].left!=Null )            //把出队的结点的左右孩子入队EnQueue( Q, treeNode[t].left );if ( treeNode[t].right!=Null )EnQueue( Q, treeNode[t].right );}
}