UVa 712：S-Trees

UVa 712：S-Trees2014-10-06 shuangde800 题目链接：

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=653

题目类型：数据结构，二叉树

样例输入：

3x1 x2 x30000011140000101111103x3 x1 x20001001140000101111100

样例输出：

S-Tree #1:0011S-Tree #2:0011

题目大意：

给一个序列集合VVI {x1, x2, x3, ....,xn}, VVI中不是0就是1 然后有一个n层的树，每一层同层的都是相同的一个数，这个数取自VVI中，输入会给出每一层是VVI中的哪一个

本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45527.htm

最后一层是叶子结点，上面是一串给定的数字。

从跟结点出发，如果那个结点是0，就往左儿子方向走，如果是1就往右儿子方向走。最后落在最后一层的叶子结点上，输出这个数字

解题思路：

这题应该算是这个二叉树专题中很水的一道题了。不用建树，如果是1就当前结点*2+1，如果是0就乘。最后得到一个数字。这个数字再减去前面层的结点之和，然后就可输出对应的结果。

具体看代码。

#include<iostream>#include<cstdio>#include<vector>using namespace std;int n,m;char termi[200];char vva[200];vector<int>vtOrder; inline void Solve（）{char temp[10];int val;vtOrder.clear（）;for（int i=0; i<n; ++i）{scanf（"%s", temp）;sscanf（temp+1, "%d", &val）;vtOrder.push_back（val）;}scanf（"%s", termi）;scanf（"%d", &m）;while（m--）{scanf（"%s", vva+1）;int pos=1;for（int i=0; i<vtOrder.size（）; ++i）{if（vva[vtOrder[i]]=="0"）pos = pos*2;elsepos = pos*2+1;}printf（"%c", termi[pos-（1<<n）]）;}printf（"
"）;} int main（）{freopen（"input.txt", "r", stdin）;int cas=1;while（scanf（"%d", &n） && n）{printf（"S-Tree #%d:
", cas++）;Solve（）;printf（"
"）;}return 0;}