一道关于树的初赛题

来源：百度知道 编辑：UC知道 时间：2024/05/30 05:17:44
题目描述:
我们都了解二叉树的先根遍历，中根遍历和后根遍历。当知道先根遍历的结果和中根遍
历结果的时候，我们可以唯一的确定二叉树；同样的，如果知道了后根遍历的结果和中根遍
历结果，二叉树也是唯一确定的。但是如果只知道先根遍历和后根遍历的结果，二叉树就不
是唯一的了。但是我们可以计算满足条件的不同二叉树的一共有多少个。这不是一个很困难
的问题，稍微复杂一点，我们把这个问题推广到N叉树。
我们用小写英文字母来表示N 叉树的结点，不同的结点用不同的字母表示。比如，对
于4叉树，如果先根遍历的结果是abdefgc，后根遍历的结果是defgbca，那么我们可以
得到6个不同的4叉树

NOIP2005程序填空第二题，请教下具体算法是什么？

你想要求不同树的个数算法,还是这道具体题的算法

对这题,a为根结点,b必为a的第一孩子,

观察b在后序中的位置,c在b后面,c只能为b的下一个孩子

d在先序中在b后,而在后序中在b前,说明d只能是b的第一个孩子,(如果是b的兄弟,在后序也应该在b后)

defg在先序和后序中顺序一样,所以它们是b的四个孩子,b度4

此时4叉树除了叶子仅有根未满度,且有2个孩子,即4个空位选2个,C(2,4)=4*3/2!=6