pascal中级教程第二章递归与递推

《pascal中级教程第二章递归与递推》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章递归与递推2.1遍历问题源程序名travel.???（pas,c,cpp）可执行文件名travel.exe输入文件名travel.in输出文件名travel.out【问题描述】我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：aaaa//\bbbb//cccc所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历

2、却不相同。【输入】输A数据共两行，第一行表示该二叉树的前序遍历结果s1，第二行表示该二叉树的后序遍历结果s2。【输出】输出可能的中序遍历序列的总数，结果不超过长整型数。【样例】trave1.intrave1.outabc4bca【算法分析】根据二叉树先序遍历和后序遍历的特点，可以知道，先序遍历的第一个结点是后序遍历的最后一个结点，对于中序遍历来说却是中间的一个结点，这里所说的中间也只是相对而言的中间。如果一棵二叉树的根结点没有左子树，那么先序遍历的第一个结点也是中序遍历的第一个结点，如果一棵二叉树的根结点没有右子树，那么先序遍历的第一个结点是中序遍历的

3、最后一个结点。我们这里还认为就是中序遍历的中间结点，上面两种情况只是特殊的情况。设二叉树的结点总数为n(对于输入的字符串来说是它的长度)，对于先序遍历的结果，第一个结点为根结点，从第二个结点到最后一个结点分为n种情况：根结点的左子树结点个数为n-1，右子树结点的个数为0；根结点的左子树结点个数为n-2，右子树结点的个数为1；……根结点的左子树结点个数为n-i，右子树结点的个数为i-1；{0<＝i<=n-1)；……根结点的左子树结点个数为0，右子树结点的个数为n-1。根据这n种情况，分别将二叉树拆分为左子树和右子树，左子树结点个数为n-i，右子树结点的个

4、数为i-l(0<＝i<＝n-1)，先序遍历的结果是从第二个结点(字符)开始取，而后序遍历的结果里是从第1个结点字符开始取。也就是说对于每一种情况，分两步处理：第一步在先序遍历和后序遍历的结果里取左子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目；第二步在先序遍历和后序遍历的结果里取右子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目。这两步都递归调用了统计过程，不再递归调用的条件就是当统计的是空树或只有一个结点的树，这时返回的值是可能有的中序遍历结果数目。结合“分类相加原理”和“分步相乘原理”，可以得到下面的递归函数：Function

5、count(先序结果first，后序结果last:string):longint;beginLen:=遍历结果的长度；如果len为0或1，则返回结果即count:=l否则begint为当前统计后符合条件的数目，初值为0；分类统计fori:=len-1downto0dobegin在first中取出长度为i的左子树结果LF；在last中取出长度为i的左子树结果LL；在first中取出长度为len-1-i的左子树结果RF；在last中取出长度为len-1-i的右子树结果RL；如果LF、LL符合基本规则(LF的首字符跟LL的尾字符相同、LF中，所有的字符在LL

6、中也都有)并且RF、RL也符合基本规则，那么t:=t+count(LF，LL)*count(RF，RL);{分步相乘、分步相加}{这里count函数中递归调用了count}end;返回值为t即count:=t;end;end;其中，检查先序结果和后序结果两个字符串是否符合基本规则，可以再通过一个函数来实现：functioncheck(先序字符串F，后序字符串L)：boolean；beginCheck:=true;如果F的首字符不等于L的尾字符则check:=false;从F的第二个字符取到最后一个字符，如果该字符不在L中，则check:=false;e

7、nd;【思考与提高】上面的算法通过递归，结合统计的基本原理“分步相乘，分类相加”，从而统计出所有可能解的个数，如果输入的两个字符串没有解，上述算法同样能得到结果。在肯定有解的情况下，上述算法最终可以递归调用到0、1个结点，如果有多组解，那么调用到两个结点时，如先序为ab、后序为ba，此时有可能有如下两种结构：aa/bb这两种结构的中序遍历结果分别为：ba、ab，有两种。根据分步相乘的原理，对比两个字符串，每出现一次如上的情况，可能有的结构数目(结构不同，中序遍历结果也不同，因此可能有的二叉树结构的数目就是可能有的中序遍历结果数目)就乘以2一次，最终得

8、到总的数目。这也可以理解为一种递推的方法。从这里可以看到，在肯定有解的情况下，给定先序遍历的结