二叉树的复习和应用.docVIP

二叉树的复习及应用 1、编写一个程序，按后缀表示法输入一个算术表达式，并按中缀表示法输出等价的表达式。设用“@”结束输入。 例如，输入：AB+CD*EF - * / 输出：（A+B）/（C*D*（E-F）） { 不得有多余括号 } 测试： AB+D*AB-C*-@ AB+CD*EF - * /@ AB+C*D-@ AB+CD*-@ 2、鸟语字典 【问题描述】 Robin是一只极其聪明的鸟，他着迷于人类丰富的语言。经过长时间的摸索，Robin模仿人类的英语创造出了鸟类的语言。与英语类似，这种鸟语的基本单位（我们不妨也称其为字母）也是由26个小写英文字母a至z组成的。 同时，若干个字母组成一个单词，用来表达一定的意思（和英语一样），相邻两个单词由一个空格隔开。Robin为他新发明的鸟语创造了丰富的词汇，并花费了大量精力写成一本鸟语词典。Robin想把一些英文的书籍（如《时间史》、《特种起源》等）翻译成鸟语。 但是，这项工作实在是太浩大了，以至于Robin无法完成。Robin想到了使用计算机，他编写了一个自动翻译的程序来做翻译这些书。 但是，他很快发现，有很多词汇是他原先所没有想到的（例如，《时间史》中的“夸克”，厚厚的鸟字典里并没有这个词。）对于这种情况，他的自动翻译程序不会对其进行翻译，而是直接放入译文中。下面是一个例子，表1表示字典中只有4个英文单词及其鸟语含义： 给出下列英文句子：I am a clever bird. 翻译后的鸟语语句为：op dg a clever myself. 对于没有在字典中出现的单词clever，自动翻译程序直接将其放入译文中。 序号 英文 鸟语 1 I op 2 am dg 3 a a 4 Bird myself 表1 给定的一个字典 现在，Robin已经翻译了一些著作，他希望补充他的鸟语字典。因此，他想知道有多少单词在他的鸟语字典里是没有的，并且，他想统计出在这些没有出现在他的鸟语字典中的单词中，出现次数最多的单词是哪一个。 【输入】 鸟语字典来自文件dic.txt，其中第一行为一个正整数n（1≤n≤10000）表示字典内的单词数目。接下来有n行，每行有一个单词（没有多余的空格）。字典中没有重复的单词。 输入数据来自输入文件input.txt。该文件中是一段文本，由若干鸟语（英语）单词组成，相邻两个单词之间用至少一个空格隔开，文本中可能存在某些标点及其他符号。（文本中的单词数目不超过10000。） 【输出】 输出文件名为output.txt。输出文件的第一行是一个整数m，表示有m个单词没有在鸟语字典中出现。接下来的若干行每行一个单词，表示那个没有出现在鸟语字典中、且出现次数最多的单词（有几个就输出几个）。 【样例输入】 【样例输出】 dic.txt： output.txt： 3 2 ae jda jd opq input.txt： ae jd . jda opq jda ae. ld jd opq! 3、下一棵树问题 (nextree.pas) [问题描述]： Farmer John的农场上有N（1=N=1000）棵树，在上过计算机课后，lin发现所有的树实际上都是严格的二叉树，二叉树的每个非叶结点都恰好有两个子结点。lin给每个结点一个数以表示这个结点为根的子树的叶结点数。 然后，lin按照先序遍历的结果把和结点相关的数列出作为它的特征序列。但是，她只列出了与根结点和所有的左子结点相关的数。例如对下面的树： 用*号表示的是lin列出的结点，这棵树的特征序列为： （7 4 1 2 1 1 1）。 在用这种方法表示完所有的树后，lin发现： 所有的树有同样多的叶结点； 所有的树有不同的特征序列； 所有可能的严格的二叉树都在农场上。 所以，lin决定把这些特征序列排序,然后希望给出一棵树的特征序列，求出紧接着的一个序列。 [输入格式]： 第1行：N，特征序列的长度。 第2行：N个用空格隔开的数，表示一棵树的特征序列。 [输出格式]： 单独的一行，表示按字典顺序排列后所给序列的后一个序列，如果所给序列是最后一个序列，则输出0。记住：输入和输出序列代表的树要有相同的叶结点数。 [样例输入]： (nextree .in) 5 5 3 2 1 1 [样例输出]： (