Problem.png
题目给出了叶子的值和每一层的取值，因此可以不用建树，直接模拟二分查找的过程即可。二分查找本质上也是构造了一棵搜索树。
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
using namespace std;
int main() {
int n;
int t = 1;
while (cin >> n && n) {
getchar();
printf("S-Tree #%d:\n", t++);
string order;
getline(cin, order);
vector<int> seq;
for (int i = 0; i < order.length(); i++) {
if (order[i] >= '0' && order[i] <= '9')
seq.push_back(order[i] - '0');
}
string leaf;
cin >> leaf;
int m;
cin >> m;
for (int i = 0; i < m; i++) {
string vva;
cin >> vva;
int low = 0, high = (1 << n) - 1;
int mid = 0;
for (int j = 0; j < seq.size(); j++) {
if (vva[seq[j] - 1] == '0') {
// 等于0，取左边一半
mid = low + (high - low) / 2;
high = mid;
}
else {
// 等于1，取右边一半
mid = low + (high - low) / 2 + 1;
low = mid;
}
}
cout << leaf[mid];
}
cout << endl << endl;
}
return 0;
}
