03-树2 List Leaves

思路：通过队列进行数据处理。 #include <stdio.h> #include <stdlib.h> #define Maxsize 10 typedef struct tree* Tree; typedef struct node* Node; struct node{ int left; int right; }; struct tree{ int head; Node TREE; }; Tree Read(); void Find(Tree A); int main(void){ Find(Read()); return 0; } Tree Read(){ int N; scanf("%d",&N); getchar(); Tree A=(Tree)malloc(sizeof(struct tree)); A->TREE=(Node)malloc(N*sizeof(struct node)); if(N==0){ A->head=-1; return A; } int i,flag[N]; char chL,chR; for(i=0;i<N;i++){ scanf("%c %c",&chL,&chR); if(i!=N-1) getchar(); if(chL!='-'){ A->TREE[i].left=chL-'0'; flag[A->TREE[i].left]=1; } else A->TREE[i].left=-1; if(chR!='-'){ A->TREE[i].right=chR-'0'; flag[A->TREE[i].right]=1; } else A->TREE[i].right=-1; } for(i=0;i<N;i++){ if(flag[i]!=1){ A->head=i; break; } } return A; } typedef struct queue* Queue; struct queue{ int Front; int* QUEUE; int last; }; Queue CreateQ(){ Queue Q=(Queue)malloc(sizeof(struct queue)); Q->QUEUE=(int*)malloc(Maxsize*sizeof(int)); Q->Front=0; Q->last=0; return Q; } void Add(Queue Q, int num){ if(num==-1) return; Q->last=(Q->last+1)%Maxsize; Q->QUEUE[Q->last]=num; } int Delete(Queue Q){ Q->Front=(Q->Front+1)%Maxsize; return Q->QUEUE[Q->Front]; } void Find(Tree A){ if(A->head==-1) return; Queue Q=CreateQ(); int move=A->head; int flag=1; Add(Q,move); while(Q->Front!=Q->last){ move=Delete(Q); Add(Q,A->TREE[move].left); Add(Q,A->TREE[move].right); if(A->TREE[move].left==-1 && A->TREE[move].right==-1){ if(flag) flag=0; else printf(" "); printf("%d",move); } } }