PAT练习题03-树2 List Leaves (25 分)

题目来源PAT

03-树2 List Leaves (25 分)

Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤10) which is the total number of nodes in the tree -- and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a "-" will be put at the position. Any pair of children are separated by a space.
Output Specification:
For each test case, print in one line all the leaves' indices in the order of top down, and left to right. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.
Sample Input:

8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

Sample Output:

4 1 5

解题历程：
博主不知道c语言有没有外来的函数库，引入数据结构，拼题a似乎不支持引入非常用函数库，所以队列就要自己写；
本题的话看了一下，采用队列的数组实现
这里有几个坑博主踩了：

• 队列初始化init时候，忘记初始化头跟尾坐标，也就是front跟rear==-1

struct QNode{
    int front;
    int rear;
    int data[MAXSIZE];
};
typedef struct QNode* Queue;

Queue init(){
    Queue q=(Queue)malloc(sizeof(struct QNode));
    q->front=q->rear=-1;
    return q;
}

int isEmpty(Queue q){
    return (q->front==q->rear)?1:0;
} 

void AddQ(int c,Queue q){
    if((q->rear+1)%MAXSIZE==q->front){
        return;
    }else{
        q->rear=(q->rear+1)%MAXSIZE;
        q->data[q->rear]=c;
    }
}

int deleteQ(Queue q){
    if(isEmpty(q)){
        return -1;
    }else{
        q->front=(q->front+1)%MAXSIZE;
        return q->data[q->front];
    }
}

接下来是树的构造：由于题目指定N的大小，MAXSIZE也是确定的；

struct Node{
    int left; //左儿子
    int right;    //右儿子
};
struct Node Tree[MAXSIZE];

最后题目中输出是叶子结点，我这里就采用了队列进行层次遍历，输出叶子结点，这里注意题目说最后一个结点不能有空格and no extra space at the end of the line，（没留意这句话会导致格式错误...）
附带上完整代码

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10

struct Node{
    int left;
    int right;    
};
struct Node Tree[MAXSIZE];


struct QNode{
    int front;
    int rear;
    int data[MAXSIZE];
};
typedef struct QNode* Queue;

Queue init(){
    Queue q=(Queue)malloc(sizeof(struct QNode));
    q->front=q->rear=-1;
    return q;
}

int isEmpty(Queue q){
    return (q->front==q->rear)?1:0;
} 

void AddQ(int c,Queue q){
    if((q->rear+1)%MAXSIZE==q->front){
        return;
    }else{
        q->rear=(q->rear+1)%MAXSIZE;
        q->data[q->rear]=c;
    }
}

int deleteQ(Queue q){
    if(isEmpty(q)){
        return -1;
    }else{
        q->front=(q->front+1)%MAXSIZE;
        return q->data[q->front];
    }
}




int main(){
    int N;
    scanf("%d",&N);
    int mark[N];
    for(int i=0;i<N;i++){
        mark[i]=1;
    }
    int k=0;
    char cl,cr;
    for(int i=0;i<N;i++){
                getchar();
                scanf("%c %c",&cl,&cr);
                if(cl!='-'){
                    k=cl-'0';
                    Tree[i].left=k;
                    mark[k]=0;
                }else{
                    Tree[i].left=-1;
                }
                if(cr!='-'){
                    k=cr-'0';
                    Tree[i].right=k;
                    mark[k]=0;
            }else{
                Tree[i].right=-1;
            }
        }
    int root;
    for(int i=0;i<N;i++){
        if(mark[i]==1){
            root=i;
            break;
        }
    }
    Queue q=init();
    AddQ(root,q);
    int num=0; 
    while(!isEmpty(q)){
        num++;
        int e=deleteQ(q);
        if(Tree[e].left==-1&&Tree[e].right==-1){
            if(num!=N){
            printf("%d ",e);    
        }else{
                printf("%d",e);
        } 
    }
        if(Tree[e].left!=-1){
            AddQ(Tree[e].left,q);
        }
        if(Tree[e].right!=-1){
        AddQ(Tree[e].right,q);
        }

    }
    return 0;
}