山东省信息学奥赛夏令营提高一树及其应用练习题目由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“山东省信息学夏令营”。
树及其应用上机练习题目
1.FBI树(fbi)
【问题描述】
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
（1）T的根结点为R，其类型与串S的类型相同；
（2）若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。
现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。
【输入文件】
输入文件fbi.in的第一行是一个整数N（0
【输出文件】
输出文件fbi.out包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。
【样例输入】
10001011
【样例输出】
IBFBBBFIBFIIIFF
【数据规模】
对于40%的数据，N
对于全部的数据，N
2.树的遍历(tree)
【问题描述】
我们都知道二叉树的后序遍历，即对于节点i，先访问它的左儿子，再访问它的右儿子，最后输出它本身。我们对其稍加改动：对于节点i，先访问它的右儿子，再访问它的左儿子，最后输出它本身。给你一棵有序的二叉树（亦即，每个节点的值严格大于它左子树的节点的值，严格小于它右子树的节点的值）的后序遍历，请你输出它的“右-左-中”遍历。
【输入】
第一行是一个整数n，表示节点个数。
第二行有n个数，表示一个n个节点的有序的二叉树的后序遍历的数值。
【输出】
输出文件仅包含一行，有n个整数，表示这个二叉树的“右-左-中”遍历。
【样例输入】
5 21 22 27 25 20 10
【样例输出】21 22 25 20 7 1 5 10
【样例说明】
【数据规模和约定】
对于30%的数据，n
对于100%的数据，n
3.合并果子(fruit.pas)
【问题描述】
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
【输入文件】
输入文件fruit.in包括两行，第一行是一个整数n(1
【输出文件】
输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。
【样例输入】2 9
【样例输出】
【数据规模】
对于30％的数据，保证有n
对于50％的数据，保证有n
对于全部的数据，保证有n
