二叉树的复习及应用

二叉树的复习及应用编一个程序按后缀表示法输入一个算术表达式按中缀表示法输出等价的达式。设用“@结束输入。例如，输入-*输出）（C*D*）{不得有多余括号}测试：-*AB+C*D-@AB+CD*-@、鸟语字典【问题描述】是只极其聪明的鸟，他着迷于人类丰富的语言。经过长时间的摸索模仿人类的英语创造出了鸟类的语言英语类似这种鸟语的基本单（我们不妨也称其为字母）也是由26个写英文字母至z组的。同时，若干个字母组成一个单词，用来表达一定的意思（和英语一样邻两个单词由一个空格隔开为新发明的鸟语创造了丰富的词汇，并花费了大量精力写成一本鸟语词典。想把一些英文的书籍（如《时间史源等）翻译成鸟语。但是，这项工作实在是太浩大了，以至于无法完成。Robin想了使用计算机，他编写了一个自动翻译的程序来做翻译这些书。但是，他很快发现，有很多词汇是他原先所没有想到的（例如》“夸克，厚厚的鸟字典里并没有这个词这种情况，他的自动翻译程序不会对其进行翻译，而是直接放入译文中。下面是一个例子，表1表字典中只有个文单词及其鸟语含义给出下列英文句子：Iamacleverbird.翻译后的鸟语语句为opdgmyself.对于没有在字典中出现的单词clever，自动翻译程序直接将其入译文中。序号

英文IamaBird表给定的一个字典

鸟语amyself

现在，Robin已翻译了些著作，他希望补充他的鸟语字典。因此，他想知道有多少单词在他的鸟语字典里是没有的且他想统计出在这些没有出现在他的鸟语字典中的单词中，出现次数最多的单词是哪一个。【输入】鸟语字典来自文件dic.txt其中第一行为一个正整数（1≤n≤表字典内的单词数目。接下来有n行每行有一个单词（没有多余的空格典中没有重复的单词。输入数据来自输入文件input.txt该件中是一段文本由若干鸟（语单词组成，相邻两个单词之间用至少一个空格隔开，文本中可能存在某些标点及其他符号本中的单词数目不超过【输出】输出文件名为。输出文件的第一行是一个整数m表示有个词没有在鸟语字典中出现接来的若干行行一个单词示那个没有出现在鸟语字典中出次数最多的单词（有几个就输出几个【样例输入】【样例输出】dic.txt：aejdinput.txt：aejdldjd、下一棵树问题(nextree.pas)[问题描述：

：jdaFarmerJohn的场上有N（）树，在上过计算课后lin发所有的树实际上都是严格的二叉树，二叉树的每个非叶结点都恰好有两个子结点给个点一个数以表示这个结点为根的子树的叶结点数。然后，lin按先序遍历的结果把和结点相关的数列出作为它的特征序列。但是，她列出了与根结点和所有的左子结点相关的数。例如对下面的树：用*号表示的是lin列的点，这棵树的特征序列为：111在用这种方法表示完所有的树后lin发：所有的树有同样多的叶结点；所有的树有不同的特征序列；所有可能的严格的二叉树都在农场上。所以，决把这些特征序列排序,后希望给出一棵树的特征序列，求出紧接着的一个序列。[输入格式]：

第N，征序列的长度。第N个空格隔开的数，表示一棵树的征序列。[输出格式]：单独的一行，表示按字典顺序排列后所给序列的后一个序列，如果所给序列是最后一个序列，则输出0记住：输入和输出序列代表的树要有相同的叶结点数。[样例输入]：.in)21[样例输出]：.11问题分析：根据一棵树的特征系列，可以建立一棵唯一二叉树，分析问题可以发现所谓当前序列的后一个序列实就是把这棵树的最右子树的叶结点适当向左边调整成一棵二叉树的特征序列，所以本问题实质是左右子树及叶结点的变换调整。、树的重量树结构可以用来表示物种之间的进化关系。一棵“进化树”是一个带权的树，其结点表示一个物种，两个叶结点之间的距离表示两个物种的差异。现在重的问题是根物种之间的距离重构相应的“进化树令}用个n上矩阵M来定义树T其中矩M满对任意的有M[I,j]+M[j,k]<=M[I,k]。满足：（1叶结点属于集合；（2边权均为非负数；（3dT(I,j)=M[I,j]其中dT(I,j)，示上ij的短路径长度。如下图，矩阵M描了一棵树。507

95

07140

树的重量是指树上所有边权之和。对于任意给出的合法矩阵M，它所能表示树的量是惟一确定的，不可能找到两棵不同重量的树，它们都符合矩阵M你的任务就是，根据给出的矩阵M计M所示树的重量下是上面给出的矩阵M所能表示的一棵树这棵树的总重量为。输入第行一个整数（2<n<30其n-1行出的是矩阵M的个三不包括对角线阵中所有元素是不超过的非负整数。输数据保证合法。输出：输出一个整数，表示树的重量。Weight.in

1211Weight.out附加题：将一棵一般树（由单字符组成）转换成二叉树，并输出转换得到的二叉树的广义表表示。一般树输入方式用父亲与孩子间加括号的串表示。例如，图1所示的树，串表示输入为：A(B(E)，，G)，D(H(I，K)))分析一树转化为二叉树的方结点的第一个孩子作为左孩子结点的右邻兄弟作为前面左孩子结点的右孩子如1的根结点Ａ的第一个孩子为结点Ｂ结点Ｂ转化二叉树后为结点Ａ的左孩子点Ｃ是结点Ｂ的右邻兄弟结Ｃ为转化二叉树后结点