NOJ 1848--二叉树

题目来源：http://acm.nuc.edu.cn/OJ/problem.php?pid=1848

Description:

对于一颗二叉树，当给定前序遍历和中序遍历，那么后序遍历必定是确定的，但是如果只给定前序遍历和中序遍历时，中序遍历是不定的。例如，前序遍历为ABCD，后序遍历为CBDA，那么中序遍历有CBAD和BCAD两种。 现在的问题就是给定前序和后序遍历序列，要求出总共有多少棵不同形态的二叉树满足这样的遍历顺序。

Input:

整个输入有两行，第一行给出前序遍历的访问顺序，第二行给定后序比那里的访问顺序，二叉树节点用一个大写字母表示，不会有两个节点标上相同的字母。输入数据不包含空格，且保证至少有一棵二叉树满足要求。

Output:

输出一个整数，表示符合要求的不同形态二叉树的数目。

Example Input:

ABCD
CBDA

Example Output:

2

首先对例子进行分析

/****真是悲哀，不知道怎么插入图片，只能通过上传图片的方式**/

（1） 前序遍历和后序遍历的最后一个字母必定是根，即都是 A

（2） 前序遍历的第二个字母是 B 也必定是某颗子树的根（左右无法确定）。那么 B 在后序遍历中一定出现在它所在子树的最后，因此我们可以通过查找 B 在后序遍历中的位置来得到左子树的所有节点，即为 B 和 C ，剩下的 D 就是右子树的节点了

（3） 分别用同样的方法分析左子树 BC 及右子树 D ， D 只有一个根，形态是唯一的， BC 只有一颗子树，它可以是左也可以是右

（4） 最后看看有多少个节点（假设是 n ）是只有一颗子树的，用乘法 pow （ 2 ， n ）就是结果

 

下面推广到所有的二叉树：

首先我们需要设几个变量：

PreStr[100];    // 前序遍历的数组

PostStr[100];   // 后序遍历的数组

Length ；      // 数组的长度

Count;       // 记录只有一个子树的节点的个数

(1)  如果 Length == 1 ，显然结果唯一

(2)  当顶点多余 1 时，说明存在子树，必然有 PreStr[0]==PostStr[Length-1]; 如果 PreStr[1] == PostStr[Length-2]; 说明从 1 到 Length-1 都是 PreStr[0] 的子树，至于是左还是右就无法确定，此时 Count++ 。对剩下的 PreStr[1] 到 PreStr[Length-1] 与 PostStr[0] 到 PostStr[Length-2] 作为一颗新树进行处理

 

(3)  如果 PreStr[1] != PostStr[Length-2], 显然存在左右子树 (PostStr 中以与 PreStr[1] 相等的位置分为左右子树 ) ，对左右子树分别作为一颗独立的子树进行处理

 

#include <stdio.h>
#include <string.h>

char PreStr[30];    //前序遍历的字符串
char PostStr[30];   //后序遍历的字符串
int count;          //记录只有一个子树的节点的个数

void calc(int a1,int b1,int a2,int b2)
{
    /*计算前序遍历a1到b1的子串,后序遍历a2到b2的子串*/
    int i;
    if(a1>=b1)  return;                //子串长度为1时不需要作出处理

    for(i=a2; i<=b2-1; i++)            //寻找左子树的位置
    {
        if(PreStr[a1+1] == PostStr[i])  break;
    }

    if(i == b2-1)  count++;             //只有一颗子树时

    calc(a1+1,a1+1+(i-a2),a2,i);       //处理左子树
    calc(a1+1+(i-a2)+1,b1,i+1,b2-1);   //处理右子树
}

int Pow(int n)
{
    /*计算2的n次方*/
    int i;
    int m = 1;

    for(i = 0; i < n; i++)
    {
        m *= 2;
    }

    return m;
}

int main()
{
    int Length;
    scanf("%s", PreStr);
    scanf("%s", PostStr);

    Length = strlen(PreStr);
    count = 0;

    calc(0,Length-1,0,Length-1);
    printf("%d\n", Pow(count));
    return 0;
}