首页 > 代码库 > The Falling Leaves UVA 699

The Falling Leaves UVA 699

说说:

这道题非常简单,本质上就是二叉树的先序遍历。只需要建立一个数组,然后将初始位置放在数组中心。然后进入左子树的根节点,向数组左侧移动一位,添加当前节点所含的值,同理进入右子树的根节点,向数组右侧移动一位,添加当前节点所含的值。并标记好到达过的数组的左右边界,最后将边界内数组的值输出即可。

源代码:

#include <stdio.h>
#include <string.h>
#define MAXN 200

int piles[MAXN];
int leftmost,rightmost;

void tree(int pos);

int main(){
  int val,T=1,i,mid;
  char c;
 //freopen("data","r",stdin);
  while(1){
   scanf("%d%c",&val,&c);
   if(val==-1&&c==' '){//空树,但并未结束
    while(scanf("%d%c",&val,&c)&&c!='\n');
    continue;
    }
   else if(val==-1)//测试结束
     break;
   
   memset(piles,0,sizeof(piles));
   leftmost=rightmost=mid=100;//从数组的中间开始

   piles[mid]=val;
   
   tree(mid-1);//遍历左子树
   tree(mid+1);
   
   printf("Case %d:\n",T++);
   for(i=leftmost;i<=rightmost;i++)
     printf("%d%c",piles[i],i==rightmost?'\n':' ');

   putchar('\n');
  }
  
  return 0;
}

void tree(int pos){
  int val;

  scanf("%d",&val);
  if(val==-1)
    return;
  else{
   piles[pos]+=val;
   leftmost=pos<leftmost?pos:leftmost;//更新左边界
   rightmost=pos>rightmost?pos:rightmost;
  }
  
  tree(pos-1);
  tree(pos+1);

  return ;
}


The Falling Leaves UVA 699