S-Tree解题报告UVa 712二叉树／二分搜索

1.题目理解

题意：

1.按照x_1,x_2,x_3,…,x_i的次序不断“走”，如果为0，那么向左子树走，如果是1那么向右子树走。

注意事项：

1.x_1,x_2,x_3,…,x_i对应的树的层数不确定，如图二。其中的第二层为x_1。

2.解题分析-读入数据的处理

1.给出的变量x_1,x_2,x_3,…,x_i就是树的高度-> 2^i 也即叶子结点的数目。

这样话可以先初始化一个数组作为叶子结点的container，装载所有的数据

2.再开一个数组装载x_1,x_2,x_3, …,x_i，注意只装载其中的数字即可：

scanf(" x%d",&temp);

con.push_back(temp);

如果是x3 x1 x2 那么读取完成后为->我们遍历con即可获得应有的次序（这里有读取的小技巧scanf("x%d",&temp)-> 只读取其中的数字）

3.解题分析-实现

S-Tree解题报告UVa 712二叉树／二分搜索

其实可以发现本质就是一个二分的过程，最终并没有建树

4.算法性能

O(2N+lgN) = O(N)

N为叶子的数目

5.解题代码

#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
int main(int argc, char const *argv[])
{
int n , k = 1;
while (scanf("%d", &n) && n != 0) {
printf("S-Tree #%d:\n", k );
k++;
scanf("\n");
int length = pow(2, n);
char a[150];//最大为128 = pow(2,7);
vector<int>con;
for (int i = 0; i < n; i++)
{
int temp;
scanf(" x%d", &temp);
con.push_back(temp);
}
scanf("%s", a);
int command;
scanf("%d", &command);
for (int i = 0; i < command; i++)
{
char instructor[9];
scanf("%s", instructor);
int beginner = 1;
int ender = length;
int templength = length / 2;

for (int j = 0; j < n; j++)
{
if (instructor[con[j] - 1] == '1')
{
beginner += templength;
templength /= 2;
} else {
ender -= templength;
templength /= 2;
}
if (ender == beginner)
{
printf("%c", a[ender - 1] );
break;
}
}
}
printf("\n\n");
}

return 0;
}

刚刚入门，比较菜鸡，请多多指教！

S-Tree解题报告UVa 712二叉树／二分搜索

相关推荐