03-树2 List Leaves

#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; //头指针进1 return 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 ); } }