# 中国大学MOOC-陈越、何钦铭-数据结构-2017秋 03-树2 List Leaves（25 point(s)）

xiaoxiao2021-02-28  6

#include <stdio.h> #include <stdlib.h> struct BinTree{ int left; int right; }; typedef struct BinTree *Tree; void addq(int queue[],int K,int *top,int *rear,int size); int deleteq(int queue[],int *top,int *rear,int size); int main(){ int i,j; int size; scanf("%d",&size); int orderSum=0,numSum=0; int root; char left[2],right[2]; Tree T = (Tree)malloc(size*sizeof(struct BinTree)); for(i=0;i<size;i++){ scanf("%s %s",&left,&right); if(left[0]=='-')(T+i)->left = -1;else (T+i)->left = atoi(left),numSum+= atoi(left); if(right[0]=='-')(T+i)->right = -1;else (T+i)->right = atoi(right),numSum+= atoi(right); orderSum+=i; } //构建队列 int queue[size+1]; int top=-1,rear=-1; int element; root = orderSum -numSum; addq(queue,root,&top,&rear,size); i=0; while(1){ element = deleteq(queue,&top,&rear,size); if(element==-1)break; if((T+queue[element])->left!=-1)addq(queue,(T+queue[element])->left,&top,&rear,size); if((T+queue[element])->right!=-1)addq(queue,(T+queue[element])->right,&top,&rear,size); if((T+queue[element])->right==-1&&(T+queue[element])->left==-1){ if(i!=0)printf(" "); printf("%d",queue[element]); i++; } } } void addq(int queue[],int K,int *top,int *rear,int size){ *rear = (*rear+1)%size; queue[*rear] = K; } int deleteq(int queue[],int *top,int *rear,int size){ if(*top==*rear)return -1; *top = (*top+1)%size; return *top; }