UVa 712：S-Trees

题目链接：

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

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

样例输入：

3
x1 x2 x3
00000111
4
000
010
111
110
3
x3 x1 x2
00010011
4
000
010
111
110
0

样例输出：

S-Tree #1:
0011

S-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;
            else
                pos = pos*2+1;
        }
        printf("%c", termi[pos-(1<<n)]);
    }
    printf("\n");
}  

int main(){
    freopen("input.txt", "r", stdin);
    int cas=1;
    while(scanf("%d", &n) && n){
        printf("S-Tree #%d:\n", cas++);
        Solve();
        printf("\n");
    }
    return 0;
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索数字
， 结点
， 题目
， 输出
， 一个
最后
uva oj、uva和uvb的区别、uvb、uva大学、弗吉尼亚大学，以便于您获取更多的相关知识。