习题6-2 S-Trees UVA - 712 满二叉树

题目链接：https://vjudge.net/problem/UVA-712

题意：根据输入的01序列判断最终会走到哪一片叶子（0左1右）（x1  x2 这些输入没用上）

思路：a数组存储叶子值，mov是最初的起点1，根据输入的路径走（0就是2*mov，1就是2*mov+1，因为一个节点k的左右儿子节点分别是2*k，2*k+1），最后算出的叶子的对应值，减去上边的2的n次方个节点，就是对应的以1开始的a数组存储的叶子节点的值。

Code：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 256+6;
int a[maxn];
int res[20000];
int main(){
	int n;
	int CASE = 1;
	while( scanf("%d",&n) && n ){	
		printf("S-Tree #%d:\n",CASE++);
		int cnt = 1;
		for( int i = 0 ; i < n ; i++ ){
			char op[5];			
			cin >> op;
		}
		for( int i = 1 ; i <= pow(2,n) ; i++ ){
			scanf("%1d",&a[i]);
		}
		int m ;
		cin >> m;
		for( int i = 0 ; i < m ; i++ ){
			int mov = 1;
			int x;
			for( int j = 1 ; j <= n ; j++ ){
				scanf("%1d",&x);
				mov = 2 * mov + x;
			} 
			int tmp ;
			tmp = mov - pow(2,n) + 1;
			res[cnt++] = a[tmp];
		}
		for(int i = 1;i <= m; i++ )
			printf("%d",res[i]);
		printf("\n\n");
	}
	return 0;
}