树及其应用上机练习题目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<=N<=10），第二行是一个长度为2N的“01”串。【输出文件】输出文件fbi.out包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。【样例输入】310001011【样例输出】IBFBBBFIBFIIIFF【数据规模】对于40%的数据，N<=2；对于全部的数据，N<=10。2.树的遍历(tree)【问题描述】我们都知道二叉树的后序遍历，即对于节点i，先访问它的左儿子，再访问它的右儿子，最后输出它本身。我们对其稍加改动：对于节点i，先访问它的右儿子，再访问它的左儿子，最后输出它本身。给你一棵有序的二叉树（亦即，每个节点的值严格大于它左子树的节点的值，严格小于它右子树的节点的值）的后序遍历，请你输出它的“右-左-中”遍历。【输入】第一行是一个整数n，表示节点个数。第二行有n个数，表示一个n个节点的有序的二叉树的后序遍历的数值。【输出】输出文件仅包含一行，有n个整数，表示这个二叉树的“右-左-中”遍历。【样例输入】9175212227252010【样例输出】272122252071510【样例说明】【数据规模和约定】对于30%的数据，n<=100对于100%的数据，n<=200000，所有节点数值不超过maxlongint且互异。3.合并果子(fruit.pas)【问题描述】在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。【输入文件】输入文件fruit.in包括两行，第一行是一个整数n(1<＝n<=10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=20000)是第i种果子的数目。【输出文件】输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。【样例输入】3129【样例输出】15【数据规模】对于30％的数据，保证有n<=1000：对于50％的数据，保证有n<=5000；对于全部的数据，保证有n<=10000。