习题6-2 S树（S-Trees，UVa 712）

题目链接：https://vjudge.net/problem/UVA-712
分类：树
备注：水题
思路：回想例题的经验，直接建树就是了，我认为那些$x_i$xi​都是干扰做题的，无视就好了。隐约觉得有些地方没注意到，以后再看吧。

代码如下：

#include<iostream>
#include<string>
using namespace std;
int n, query, kase, lson[1 << 7], rson[1 << 7];
string line, out;
void Build(int root, int depth)
{
	if (depth == n - 1)
	{
		lson[root] = line[(root << 1) - (1 << n)] - '0';
		rson[root] = line[(root << 1 | 1) - (1 << n)] - '0';
		return;
	}
	lson[root] = root << 1; rson[root] = root << 1 | 1;
	Build(root << 1, depth + 1);
	Build(root << 1 | 1, depth + 1);
}
void dfs()
{
	int key = 1; string out; getline(cin, out);
	for (int pos = 0; pos < n; pos++)
	{
		if (out[pos] == '0')key = lson[key];
		if (out[pos] == '1')key = rson[key];
	}
	cout << key;
}
int main(void)
{
	while (cin >> n && n)
	{
		getchar();
		cout << "S-Tree #" << ++kase << ":\n";
		for(int i=0;i<2;i++)getline(cin, line); 
		Build(1, 0);//建树
		cin >> query;
		getchar();
		while (query--)dfs();
		cout << "\n\n";
	}
	return 0;
}