首页 > 代码库 > S-Trees UVA 712

S-Trees UVA 712

说说:


先来说一下题意,题意感觉挺难描述的。有如下这样一棵树:

每一层都有一个变量描述,如左树,从根节点到倒数第二层为x1,x2,x3,而右树为x3,x1,x2,这在开始的时候会给定的。然后题目也会给你从左到右叶子节点所代表的数值,只可能是0或1.最后,会给你一串01数字,代表的是x1,x2,x3...的数值。相当于告诉你从树的根到叶子节点行走的路径。比如右树,从根到倒数第二层的变量依次为x3,x1,x2,如果题目给你它们的值为110(这是按顺序的,即x1=1,x2=1,x3=0)。那么我们的行走路径为(0代表进入左子树,1反之)左,右,右,即如图所示。

        我的解法是先用一个数字标记变量的所在的层数。那样通过这个数组的间接操作,我们就能找到每一层的变量的值了。然后其实我们可以将树的叶子节点从做到右编号,将所有叶子保存在一个字符数组中。接着初始一个变量ans为0,若进入左子树,仅将ans右移一位,反之,则ans右移一位且+1。最后我们到达叶子节点后,ans保存的就是叶子所在的序号,输出结果即可。可能描述地不太清楚,看代码也许会更明白一点^_^


源代码:

#include <stdio.h>
#define MAX 7+5

int main(){
  int order[MAX];//保存每层的变量序号
  char terminal[1000],x[3],test[MAX];
  int n,m,T=1,i,ans;
 // freopen("data","r",stdin);
  while(scanf("%d",&n)&&n){
    for(i=0;i<n;i++){
      scanf("%s",x);
      order[i]=x[1]-'1';
    }

    scanf("%s",terminal);//叶子节点
    scanf("%d",&m);
    printf("S-Tree #%d:\n",T++);
    while(m--){
      scanf("%s",test);
      ans=0;
      for(i=0;i<n;i++)//通过每层变量的序号,找到该变量并判断
        if(test[order[i]]=='0')//进入左子树
	  ans=ans<<1;
	else
	  ans=(ans<<1)+1;//进入右子树

         putchar(terminal[ans]);
    }
    
    printf("\n\n");
  }

  return 0;
}


S-Trees UVA 712