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

【题10】根据根据前、中序遍历求后序遍历 约定一棵二叉树的前序遍历和中序遍历序列，用你熟悉的程序设计语言生成该二叉树，并将其后序遍历打印出来。为便于编程，二叉树的结点用单个大写英文字母表示，且结点互不重复。比如，输入前序遍历序列为DBACPMZX，中序遍历序列为ABCDMPXZ，应生成的二叉树结构如图6.1.13所示：图6.1.13 应输出的后序遍历序列为ACBMXZPD 注意：你的程序应能鉴别任何的错误输入。题解1 鉴别错误输入设 predstr前序串； s1前序串的字符集； midstr中序串； s2中序串的字符集；predstr串与midstr串必须同时满足下述三个条件方可对应同一棵二叉树：1. predstr串与midstr串的长度相等；2. 两串的字符为 AZ的子集且各不相同；3. 在predstr串中的字符必须在midstr串出现； 判别输入合法性的过程由布尔函数correct完成。若输入合法(即predstr串与midstr串可对应同一棵二叉树)，则返回true；否则返回false。 fuction correct：boolean； begin correctfalse； if length(predstr)=length(minstr) 若两序列的长度相同 then begin s1； 前序串的字符集初始化 for i1 to length(predstr) do 分析前序串的每一个字符 if (predstris1)or(predstri AZ) then exit 若前序串中字符重复或出现非法字符，则返回false else s1s1+predstri； 否则当前字符进入前序串的字符集 s2； 中序串的字符集初始化 for i1 to length(midstr) do if (midstris1)or(midstris2) then exit 若中序串的当前字符非前序串字符或者为重复字符，则返回false else s2s2+midstri； 否则当前字符进入中序串的字符集 correcttrue； 返回输入合法标志 end；then end；correct2 构造两个线性序列对应的二叉树 若给出一棵二叉树的前序遍历和中序遍历，那么这两个线性序列可以唯一对应一棵二叉树。问题是如何由这两个线性序列推导出对应的二叉树呢？设 predstr= ABCD midstr= BCAD 由前序遍历和中序遍的递归定义可以看出，前序遍历的首字符是树的根，例如上述前序序列中的A。我们根据该字符在中序序列中的位置i将中序序列一分为二，左端序列(即第1i-1个字符)为左子树中序遍历的结果，例如上述中序序列中的BC； 右端序列(即第i+1个字符尾字符)为右子树中序遍历的结果，例如上述中序序列中的D；前序序列的第2i个字符为左子树的前序遍历的结果，例如上述前序遍历中的BC；前序序列的第i+1至尾部的字符为右子树前序遍历的结果。例如上述前序遍历中的D。这样便分别求出了左子树的根和左子树的前序序列、左子树的中序序列，右子树的根和右子树的前序序列、右子树的中序序列。再运用上述方法继续分别求解左子树和右子树。如此反复，直至对应的二叉树求出为止。显然，这一求解过程是递归的。根据上述思想，我们设计一个递归函数maketree。该函数的输入值参为前序序列和中序序列两个字串，返回的函数值为指向根结点的地址指针。 设二叉树的定义为 Type Link=node； 结点的指针类型 node=record 结点的数据类型 val：char； 值域 left,right：link； 左、右指针 end； var root：link； 二叉树的根结点指针function maketree(predstr, midstr)：link；输入前序串和中序串，计算和返回对应的二叉树 var root：link； 子树的根结点指针 s1，s2：string； 子树的前序串和中序串 begin new (root)； 为子树根申请内存 rootvalpredstr1； 设定根值 ipos(rootval,midstr)； if i=1 then rootleftnil 左子树为空else begin s1copy(predstr,2，i-1)； s2copy(midstr，1，i-1)； 计算左子树的前序串和中序串 rootleftmaketree(s1,s2)； 构造左子树 end；else if i=length (midstr) then rootrigthnil 右子树为空 else begin s1copy(predstr,i+1，length(predstr)-i)； s2copy(midstr，i+1，length(midstr)-i)； 计算右子树的前序串和中序串 rootrigthmaketree(s1,s2)； 构造右子树 end；else maketreeroot； 返回根结点end；maketree 我们通过调用maketree(ABCD,BCAD)计算对应的二叉树，计算过程如图6.1.14所示图6.1.143 输出二叉树的后序序列 由maketree函数求出了前序序列和中序序列对应的二叉树的根结点指针后，便可以根据后序遍历的递归定义编写程序，输出这两棵二叉树的后序序列 procedure out (root)； begin if rootnil then begin out (rootleft)； 递归遍历左子树 out(rootright)； 递归遍历右子树 输出rootval； end；then