[数据结构 树] S-Trees UVa712

题目描述

给你一个深度为n$n$的满二叉树，每层代表一个01变量，取0时向左走，取1时向右走。现给出所有的子叶的值和一些查询值，求每个查询值到达的子叶的值。

题解

本题应用的是完全二叉树的性质。不用建立树，以0$0$到n−1$n-1$的顺序保存子叶的值。将查询值看做二进制，还原为十进制对应的就是子叶的值。

AC代码

#include <cstdio>
#include <cstring>
const int maxn = 10000;
int order[8];
char val[maxn];

int main(){
    int n, kase = 0;
    while(scanf("%d", &n) != EOF && n){
        char a[3], dex[8];
        for(int i = 0; i<n; i++){
            scanf("%s", a);
            order[a[1]-1-'0']=n-i-1;
        }
        scanf("%s", val);
        int m;
        scanf("%d", &m);
        printf("S-Tree #%d:\n", ++kase);
        while(m--){
            int index = 0;
            scanf("%s", dex);
            for(int i = 0; i<n; i++){
                index += (dex[i]-'0') * (1<<order[i]);
            }
            printf("%c", val[index]);
        }
        printf("\n\n");
    }
}