题目:给你一棵全然二叉树,再给你一个xi1~xin-1的序列,相应从根到叶子上一层。
每层相应一个xi,叶子是0或1,如今给你一些路径,输出路径相应的叶子的值;
路径是01串。从更開始往下走,0表示左子树,1表示右子树,相应x1~xn-1的顺序。
分析:模拟。
直接安找路径走过去就好了,由于是二叉树,正好相应二进制数。
注意:路径的顺序要调整到和树一样在计算。
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int x[10],f[10];
int leaf[200];
int main()
{
int n,k,t = 1;
char buf[200];
while (~scanf("%d",&n) && n) {
for (int i = 0 ; i < n ; ++ i) {
scanf("%s",buf);
x[i] = atoi(&buf[1])-1;
}
scanf("%s",buf);
int m = 1<<n;
for (int i = 0 ; i < m ; ++ i)
leaf[i] = buf[i]-'0';
printf("S-Tree #%d:\n",t ++);
scanf("%d",&k);
for (int i = 0 ; i < k ; ++ i) {
scanf("%s",buf);
for (int j = 0 ; j < n ; ++ j)
f[x[j]] = buf[j]-'0';
int v = 0;
for (int j = 0 ; j < n ; ++ j)
v = 2*v+f[x[j]];
printf("%d",leaf[v]);
}
printf("\n\n");
}
return 0;
}