高级数据结构二叉树计数.pptVIP

高级数据结构 ——二叉树计数 二叉树计数 树的计数 树的计数 树的计数 * * n = 0或1: 只有一棵二叉树 n = 2: 存在2棵不同（结构）的二叉树 n = 3 存在5棵不同的二叉树： 那么，具有n个结点的不同二叉树究竟有多少呢？ 树的基本要素： 结点，边 树的计数： 将n个结点编号为1到n 将n个结点组合成合法的二叉树 计算不同的二叉树总数 怎样确定一棵合法的二叉树？ 假设一棵二叉树的前序序列为1 2 3 4 5 6 7 8 9 中序序列为2 3 1 5 4 7 8 6 9 则通过这对序列可以唯一确定一棵二叉树 前序序列为1 2 3 4 5 6 7 8 9 中序序列为2 3 1 5 4 7 8 6 9 为了构造相应的二叉树，可找出前序第一个结点，即1。于是，结点1是树根，中序序列中所有在1之前的结点（2 3）属于左子树，其余结点（5 4 7 8 6 9）属于右子树。 接着，可根据前序序列2 3和中序序列2 3构造左子树。显然，结点2是树根。由于在中序序列中，结点2之前无结点，所以其左子树为空，结点3是其右子树，如下图所示： 前序序列为1 2 3 4 5 6 7 8 9 中序序列为2 3 1 5 4 7 8 6 9 如此继续，最终可唯一地构造下图所示的二叉树： 前序序列为1 2 3 4 5 6 7 8 9 中序序列为2 3 1 5 4 7 8 6 9 设计算法，根据二叉树的前序/中序序列对构造该树 每一棵二叉树都有唯一的前序/中序序列对 如果树中结点按前序编号，即树的前序序列为1, 2, …, n 不同的中序序列定义不同的二叉树 不同的二叉树个数等于从前序序列为1, 2, …, n的二叉树可产生的不同的中序序列的个数 设bn是具有n个结点的不同二叉树的个数。bn实际上是按以下方式形成的各种可能的二叉树个数之和：一个根和两个结点数分别为i和n–i–1的子树(0≤i n) 对于每一个i，存在bi bn-i-1棵不同的树，因此有 (4.3) 为了用n表示bn，必须求解递归方程(4.3)。设 (4.4) B(x)是二叉树个数的生成函数。由于 即 x B2(x) – B(x) + 1 = 0 解此一元二次方程，并注意B(0) = b0 = 1（等式(4.3)），可得 利用二项式公式展开(1 – 4x)1/2得到 令n = m + 1，可得 (4.5) 比较等式(4.4) 和(4.5)，并注意bn是B(x)中xn的系数，可得 不同的中序序列在中序 遍历时和相应的进出栈 序列一一对应 不同的进出栈序列的总 数是不同树形的二叉树 的总和 例： 当 二叉树的结点个数 n = 3 前序序列为 1、2、3 时 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1、进栈 2、进栈 3、进栈 3、出栈 2、出栈 1、出栈 1、进栈 2、进栈 2、出栈 3、进栈 3、出栈 1、出栈 1、进栈 2、进栈 2、出栈 1、出栈 3、进栈 3、出栈 1、进栈 1、出栈 2、进栈 3、进栈 3、出栈 2、出栈 1、进栈 1、出栈 2、进栈 2、出栈 3、进栈 3、出栈 进出栈序列总数的计算为 2n个方格中放置 n个1的组合数 － 不合理的序列总数 1 1 1 0 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0 合 理 不合理 二叉树的结点个数 n = 3