S-Trees UVA - 712 (二叉树模拟)

题目太长不贴了:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=653

解题思路:

每一次查询的结果就是按照Xn顺序得到的二进制数转成10进制,然后根据10进制数去叶子节点中查找对应的数,把所有查询结果按顺序拼接在一起得到的就是答案

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <string>
#include <math.h>
using namespace std;
const int MAXN = 10;
int kN,kM;
int numHash[MAXN];  //索引
//首先根据X建树,然后根据二进制计算
int sindex = 0;
//二进制转10进制

int BTOD(string num) {
	int res = 0;
	int temindex = 0;
	for (int i = num.length()-1; i >= 0; --i) {
		res += (num[i] - '0') * pow(1.0*2, temindex++);
	}
	return res;
}

int main(){
	while(cin >> kN){
		if(kN == 0) break;  //如果等于0,退出
		string tempStr,ordStr,numStr;
		string nodeStr;
		string resStr;  //结果
		for(int i = 0;i < kN;++i){
			cin>>tempStr;
			ordStr+=tempStr[1];  //父亲结点
		}
		cin >> nodeStr;  //读入叶子结点
		cin >> kM;
		for(int j = 0; j < kM;++j){
			memset(numHash,0,sizeof(numHash));
			cin >> numStr;
			for(int k = 0; k < numStr.length();++k){
				numHash[k+1] = numStr[k]-'0'; //索引
			}
			string ten;
			for(int v = 0; v < ordStr.length();++v){
				ten += numHash[ordStr[v]-'0']+'0';  //按顺序得到二进制数
			}
			int tindex = BTOD(ten);
			resStr += nodeStr[tindex];
		}
		printf("S-Tree #%d:\n",++sindex);
		cout<<resStr<<endl<<endl;
		 
	}
	system("PAUSE");
	return 0;
}