【问题描述】 我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树： a a a a / / \ \ b b b b / \ / \ c c c c 所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。 【输入】 输A数据共两行，{dy}行表示该二叉树的前序遍历结果s1，第二行表示该二叉树的后序遍历结果s2。 【输出】 输出可能的中序遍历序列的总数，结果不超过长整型数。 【样例】 trave1.in trave1.out abc 4 bca 【算法分析】 根据二叉树先序遍历和后序遍历的特点，可以知道，先序遍历的{dy}个结点是后序遍历的{zh1}一个结点，对于中序遍历来说却是中间的一个结点，这里所说的中间也只是相对而言的中间。如果一棵二叉树的根结点没有左子树，那么先序遍历的{dy}个结点也是中序遍历的{dy}个结点，如果一棵二叉树的根结点没有右子树，那么先序遍历的{dy}个结点是中序遍历的{zh1}一个结点。我们这里还认为就是中序遍历的中间结点，上面两种情况只是特殊的情况。 设二叉树的结点总数为n(对于输入的字符串来说是它的长度)，对于先序遍历的结果，{dy}个结点为根结点，从第二个结点到{zh1}一个结点分为n种情况： 根结点的左子树结点个数为n-1，右子树结点的个数为0； 根结点的左子树结点个数为n-2，右子树结点的个数为1； …… 根结点的左子树结点个数为n-i，右子树结点的个数为i-1；{0<＝i<=n-1)； …… 根结点的左子树结点个数为0，右子树结点的个数为n-1。 根据这n种情况，分别将二叉树拆分为左子树和右子树，左子树结点个数为n-i，右子树结点的个数为i-l(0<＝i<＝n-1)，先序遍历的结果是从第二个结点(字符)开始取，而后序遍历的结果里是从第1个结点字符开始取。也就是说对于每一种情况，分两步处理：{dy}步在先序遍历和后序遍历的结果里取左子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目；第二步在先序遍历和后序遍历的结果里取右子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目。这两步都递归调用了统计过程，不再递归调用的条件就是当统计的是空树或只有一个结点的树，这时返回的值是可能有的中序遍历结果数目。 结合“分类相加原理”和“分步相乘原理”，可以得到下面的递归函数： {先序的{dy}个字符应该是后序的{zh1}一个字符，然后把先序后序的左子树(l1l,l2l)、右子树(l1r,l2r)都取出来，怎么取？for i:=n-1 downto 1,取出来以后，l1l与l2l，l1r与 l2r，应该符合要求，然后用相乘，相加原理} if length(a)=0 then check:=true for i:=2 to length(a) do end;
begin
|
