树及其应用上机练习题目
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树的后序遍历序列。
【样例输入】
3
10001011
【样例输出】
IBFBBBFIBFIIIFF
【数据规模】
对于40%的数据，N
对于全部的数据，N
2.树的遍历(tree)
【问题描述】
我们都知道二叉树的后序遍历，即对于节点i，先访问它的左儿子，再访问它的右儿子，最后输出它本身。我们对其稍加改动：对于节点i，先访问它的右儿子，再访问它的左儿子，最后输出它本身。给你一棵有序的二叉树（亦即，每个节点的值严格大于它左子树的节点的值，严格小于它右子树的节点的值）的后序遍历，请你输出它的“右-左-中”遍历。
【输入】
第一行是一个整数n，表示节点个数。
第二行有n个数，表示一个n个节点的有序的二叉树的后序遍历的数值。
【输出】
输出文件仅包含一行，有n个整数，表示这个二叉树的“右-左-中”遍历。
【样例输入】
9
1 7 5 21 22 27 25 20 10
【样例输出】
27 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。
【样例输入】
1 2 9
【样例输出】
15
【数据规模】
对于30％的数据，保证有n
对于50％的数据，保证有n
对于全部的数据，保证有n
