学步园

/*

给定一颗k叉树的前序和后序遍历序列

求这个k叉树一共可能有多少种

求每个节点孩子节点的个数n，然后从m个位置中选n个位置给这n个孩子，一共有c(m ,n )中选法，

把所有节点的这个值相乘即可

*/

#include <iostream><br /> #define MAX_N 26<br /> using namespace std;<br /> int countv[MAX_N + 1];<br /> char pre[MAX_N + 1];<br /> char post[MAX_N + 1];<br /> int m;<br /> //计算组合数<br /> int getC(int n, int m)<br /> {<br /> if(m == 0 || n == m) return 1;<br /> else return getC(n - 1, m - 1) + getC(n - 1, m);<br /> }<br /> int getRes()<br /> {<br /> int res = 1;<br /> for(int i = 0; i < strlen(post); i++)<br /> res *= getC(m, countv[i]);<br /> return res;<br /> }<br /> //递归计算每个节点的儿子数<br /> void countSons(int curPrePos, int curPostPos, int endPrePos)<br /> {<br /> if(curPrePos == endPrePos)<br /> return;<br /> int pPre = curPrePos + 1, postP;<br /> char c;<br /> while(pPre <= endPrePos)<br /> {<br /> c = pre[pPre];<br /> countv[curPrePos]++;<br /> postP = curPostPos;<br /> while(post[postP] != c) postP++;<br /> countSons(pPre, curPostPos, pPre + (postP - curPostPos));<br /> pPre = pPre + (postP - curPostPos) + 1;<br /> curPostPos = postP + 1;<br /> }<br /> }<br /> int main()<br /> {<br /> while(scanf("%d", &m) && m != 0)<br /> {<br /> scanf("%s%s", pre, post);<br /> memset(countv, 0, sizeof(countv));<br /> countSons(0, 0, strlen(pre) - 1);<br /> printf("%d/n", getRes());<br /> }<br /> return 0;<br /> }