【题10】根据根据前、中序遍历求后序遍历--试题解析

《【题10】根据根据前、中序遍历求后序遍历--试题解析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、【题10】根据根据前、中序遍历求后序遍历约定一棵二叉树的前序遍历和中序遍历序列，用你熟悉的程序设计语言生成该二叉树，并将其后序遍历打印出来。为便于编程，二叉树的结点用单个大写英文字母表示，且结点互不重复。比如，输入前序遍历序列为DBACPMZX，中序遍历序列为ABCDMPXZ，应生成的二叉树结构如图6.1.13所示：图6.1.13应输出的后序遍历序列为ACBMXZPD注意：你的程序应能鉴别任何的错误输入。题解1鉴别错误输入设predstr—前序串；s1—前序串的字符集；midstr—中序串；s2—中序串的字符集；predstr串与midstr串必须同时满足

2、下述三个条件方可对应同一棵二叉树：1.predstr串与midstr串的长度相等；2.两串的字符为{’A’‥’Z’}的子集且各不相同；3.在predstr串中的字符必须在midstr串出现；判别输入合法性的过程由布尔函数correct完成。若输入合法(即predstr串与midstr串可对应同一棵二叉树)，则返回true；否则返回false。fuctioncorrect：boolean；begincorrect←false；iflength(predstr)=length(minstr){若两序列的长度相同}thenbegins1←[]；{前序串的字符集初

3、始化}fori←1tolength(predstr)do{分析前序串的每一个字符}if(predstr[i]s1)or(predstr[i][’A’‥’Z’])thenexit{若前序串中字符重复或出现非法字符，则返回false}elses1←s1+[predstr[i]]；{否则当前字符进入前序串的字符集}s2←[]；{中序串的字符集初始化}fori←1tolength(midstr)doif(midstr[i]s1)or(midstr[i]s2)thenexit{若中序串的当前字符非前序串字符或者为重复字符，则返回false}elses2←s2+[mi

4、dstr[i]]；{否则当前字符进入中序串的字符集}correct←true；{返回输入合法标志}end；{then}end；{correct}1构造两个线性序列对应的二叉树若给出一棵二叉树的前序遍历和中序遍历，那么这两个线性序列可以唯一对应一棵二叉树。问题是如何由这两个线性序列推导出对应的二叉树呢？设predstr=’ABCD’midstr=’BCAD’由前序遍历和中序遍的递归定义可以看出，前序遍历的首字符是树的根，例如上述前序序列中的’A’。我们根据该字符在中序序列中的位置i将中序序列一分为二，左端序列(即第1～i-1个字符)为左子树中序遍历的结果，例

5、如上述中序序列中的’BC’；右端序列(即第i+1个字符～尾字符)为右子树中序遍历的结果，例如上述中序序列中的’D’；前序序列的第2～i个字符为左子树的前序遍历的结果，例如上述前序遍历中的’BC’；前序序列的第i+1至尾部的字符为右子树前序遍历的结果。例如上述前序遍历中的’D’。这样便分别求出了左子树的根和左子树的前序序列、左子树的中序序列，右子树的根和右子树的前序序列、右子树的中序序列。再运用上述方法继续分别求解左子树和右子树。如此反复，直至对应的二叉树求出为止。显然，这一求解过程是递归的。根据上述思想，我们设计一个递归函数maketree。该函数的输入值

6、参为前序序列和中序序列两个字串，返回的函数值为指向根结点的地址指针。设二叉树的定义为TypeLink=↑node；{结点的指针类型}node=record{结点的数据类型}val：char；{值域}left,right：link；{左、右指针}end；varroot：link；{二叉树的根结点指针}functionmaketree(predstr,midstr)：link；{输入前序串和中序串，计算和返回对应的二叉树}varroot：link；{子树的根结点指针}s1，s2：string；{子树的前序串和中序串}beginnew(root)；{为子树根申请

7、内存}root↑．val←predstr[1]；{设定根值}i←pos(root↑．val,midstr)；ifi=1thenroot↑．left←nil{左子树为空}elsebegins1←copy(predstr,2，i-1)；s2←copy(midstr，1，i-1)；{计算左子树的前序串和中序串}root↑．left←maketree(s1,s2)；{构造左子树}end；{else}ifi=length(midstr)thenroot↑．rigth←nil{右子树为空}elsebegins1←copy(predstr,i+1，length(pred

8、str)-i)；s2←copy(midstr，i+1，length