算法标签：

模拟

题解：

可以按照树的遍历去做，这样思路直接。但是可以看到最后遍历树只需要知道走到哪一个叶子节点即可。

二分思路来源在于：走左子树，则最终结果一定不在叶子节点的右半侧，走右子树，最终结果一定不在叶子节点的左半侧，如此设定start，end指定搜索下标的范围，不断缩小范围，同时需要配上手工先行验证想法。

深度为n的树，叶子节点有2 n 2^n2 n 个，用数组char terminal_node[150]存储，只需要找到遍历最后的下标index即可。设叶子节点数组下标从1开始存放数字，且start=1，end=2 n 2^n2 n ，mid=(start+end)/2。对于给定的VVA，遍历前n-1个VVA的值，如果某个变量为0，走左子树，那么最终的值不可能在mid右边，那么修改end=mid，mid=(start+end)/2，如果变量为1同理，不可能在mid左边，修改start=mid，mid=(start+end)/2，按照这个步骤最终遍历完n-1个VVA，如果第n个VVA的值为0，则index = mid即为最终结果在叶子节点的下标，如果VVA=1，则index = mid+1，最后结果为terminal_node[index]

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
//Accepted

int pow(int x, int y) {
    int result = 1;
    for (int i = 0; i < y; i++)
        result *= x;
    return result;
}

int s_tree_function(char vva[], int n) {
    int start = 1, end = (int)pow(2, n);
    int mid = (start + end) / 2;
    for (int i = 0; i < n - 1; i++) {
        if (vva[i] == '0') {
            end = mid;
            mid = (start + mid) / 2;
        }
        else {
            start = end;
            mid = (end + mid) / 2;
        }
    }
    if (vva[n - 1] == '1') mid++;
    return mid;
}

int main() {
    int N;
    int cases = 0;
    while (cin >> N && N != 0) {
        cases++;
        string tmp;
        for (int i = 0; i < N; i++) {
            cin >> tmp;
        }
        char terminal_node[150];
        cin.ignore(1);
        for (int i = 1; i <= (int)pow(2, N); i++) {
            terminal_node[i] = getchar();
        }

        int M; cin >> M;
        cout << "S-Tree #" << cases << ":" << endl; // 将printf替换为cout
        for (int i = 0; i < M; i++) {
            cin.ignore(1);
            char vva[10];
            for (int i = 0; i < N; i++) {
                vva[i] = getchar();
            }
            int index = s_tree_function(vva, N);
            cout << terminal_node[index];
        }
        cout << endl << endl;

    }

    return 0;
}