问题引出

问题:具有n个节点的不同形态的树(二叉树)有多少棵。 相关概念:

二叉树的计数问题就是讨论具有n个节点、互不相似的二叉树的数目bn

题解

从生成树的角度

一棵具有n(n>1)个结点的二叉树可以看成是由一个根节点、一棵具有i个节点的左子树和一棵具有n-i-1个节点的右子树组成,因此可以推出以下公式: 演算得(递推过程有点复杂需要较好的数学功底): 思前想后还是把递推过程放上来吧,有兴趣可以看看: 对于序列 定义生成函数: 因为: 根据上面的递推公式: 由此得: 即: 解此二次方程得: 由初值 应有 所以 利用二项式展开 k=0时,上式的第一项为1,故有: 对照生成函数和上式而得:

从前中序遍历序列唯一性的角度

由前面二叉树的性质可以知道,树的前序遍历序列和中序遍历序列是唯一的,那么,由前序序列和中序序列也可以唯一确定一棵树。 因为:前序序列第一个元素是根,则可以在中序序列中根结点前的都是左子树的结点,依次类推可以确定一棵树。

确定中序序列的过程:

  1. 定根 A
  2. 在中序序列中找到 A
  3. 中序序列中的 A 的左部为 A 的左子树上的所有结点, A 的右部为 A 的右子树中的所有结点。
  4. 根据 A 的左子树的所有结点的前序序列确定 A 的左子树的根节点,它是 A的左儿子。
  5. 根据 A 的右子树的所有结点的前序序列确定 A 的右子树的根节点,它是A的右儿子。
  6. 在左、右子树中反复以上过程。至所有结点处理完毕。结束

由于问题所求的解是树形种数,则: 设二叉树的前序的序列为 1、2、3、… 、n 不同的中序序列对应着不同形态的二叉树 不同的中序序列的总数 = 不同形态二叉树总数 不同的中序序列在中序遍历时和相应的进出栈序列一一对应。 不同的进出栈序列的总数 = 不同形态的二叉树的总数

进出栈序列总数的计算为: 2n个方格中放置31的组合数 - 不合理的序列总数

按不同顺序进出栈得到的排列的数目为:

由二叉树的计数可推得树的计数,由“森林与二叉树的转换”中可知一棵树可转换成唯一的一棵没有右子树的二叉树,反之亦然。 所以具有n个节点的不同形态的树的数目和具有n-1个节点的二叉树的数目相同。 这里的树指的是有序树。

总结

树的计数问题的结果数称为Catalan数 Cat(n)同时也是把n+2边的凸多边形,连n-1条不相交的对角线,把这个凸多边形分成三角形的不同的方法的数目。


总结自:《数据结构(C语言版)》 清华大学出版社 严蔚敏、吴伟民编著