树习题解答.doc

数据结构——树习题解答 1、单词查找树【问题描述】 在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表中。为了提高查找和定位的速度，通常都画出与单词列表所对应的单词查找树，其特点如下： （1） 根节点不包含字母，除根街店为每一个节点都包含一个大写英文字母； （2） 从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该结点对应的单词。单词列表中的每个单词，都是该单词查找树某个节点所对应的单词； （3） 在满足上述条件下，该单词查找树的节点数最少。 要求：对一个确定的单词列表，请统计对应的单词查找树的结点数（包括根节点）. 输入： 输入文件名为word.in，该文件为一个单词列表，每行仅包含一个单词和一个换行/回车符。每个单词仅由大写字母组成，长度不超过63个字符。文件总长度不超过32K，至少有一行数据。 输出： 输出文件名为word.out，该文件仅包含一个整数，该整数为单词列表对应的单词查找树的结点数。 【样例输入】 A AN ASP AS ASC ASCII BAS BASIC 【样例输出】 13 【题解】 首先要对建树的过程有一个了解。对于当前被处理的单词和当前树：在根节点的子节点中找单词的为第一位字母，若存在则进而在该节点的子节点中寻找第二位……，如此直到单词结束，既不需要在该书中添加节点；若单词的第n个字母不能找到，即将单词的第n个字母及其后的字母依次加入单词查找树中。但本题只是问你结点总数，而非建树方案，且有32K大小的单词文件，所以应该考虑能不能通过不建树就直接算出结点数。 为了说明问题本质，我们定义单词相对于另一个单词的差：设单词1的长度为L，且与单词2从第N位开始不一致，则定义单词1相对于单词2的差为L-N+1，这是描述单词相似程度的量。可见，将一个单词加入单词树的时候，须加入的节点数等于该单词树中已有的单词的差得最小值。 单词的字典顺序排列后的序列则具有类似的特性，即在一个字典顺序序列中，第m个单词相对于第m-1个单词的差必定是它对于前m-1个单词的差中最小的。于是得出建树的等效算法： （1） 读入文件； （2） 对单词列表进行字典顺序排序； （3） 依次计算每个单词对前一个单词的差，并把差累加起来。注意：第一个单词相对于“空”的差为该单词的长度； （4） 将累家和再加上1（根结点），输出结果 program word(input,output); var a:array[1..32767] of char; index:array[1..6700] of integer; n,k,i,j,tot,t:integer; s,pre,now:string; function cmp(i, j:longint):boolean; begin while ((a[i]=a[j]) and (ord(a[i])32) and (ord(a[j])32)) do begin inc(i); inc(j); end; if (a[i]a[j]) then cmp := false else cmp := true; end; begin {main} assign(input,word.in);reset(input); assign(output,word.out);rewrite(output); fillchar(a, sizeof(a), 0); n := 0; k:= 0; while (not eof) do begin readln(s); n:=n+1; index[n] := k+1; for i:=1 to length(s) do a[k+i] := s[i]; k := k+i+1; end; for i:=1 to n do for j:=i+1 to n do if cmp(index[i], index[j]) then begin t := index[i]; index[i] := index[j]; index[j] := t; end; tot := 0; pre := ; for i:=1 to n do begin now := ; j := index[i]; while (ord(a[j])0) do begin now := now + a[j