5.11 二叉树计数

考虑三个问题:

  • 『确定具有 nn 个结点的不同二叉树的个数』

如果 n=0n = 011,则只存在一棵二叉树。如果 n=2n = 2,则存在两棵不同的二叉树,而如果 n=3n = 3,则存在 5 棵不同的二叉树……

  • 『将 1,2,3,...,n1, 2, 3, ..., nnn 个数依次入栈,并通过栈以可能的方式得到的不同的排列为?』

考虑一棵二叉树的前序序列: 1 2 3 4 5 6 7 8 9 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9 和中序序列: 2 3 1 5 4 7 8 6 9 2\ 3\ 1\ 5\ 4\ 7\ 8\ 6\ 9 则可以唯一地确定这棵树:

倘若现在固定前序排列,从前序排列为 1,2,...,n1, 2, ..., n 的二叉树得到的不同的中序排列个数就等于不同的二叉树个数。

考虑 n=3n = 3,将 1,2,31, 2, 3 依次进栈,以所有可能的方式出栈得到的不同排列为: (1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,2,1) (1, 2, 3)\ (1, 3, 2)\ (2, 1, 3)\ (2, 3, 1)\ (3, 2, 1) 即:

  1. 11 进 -> 11 出 -> 22 进 -> 22 出 -> 33 进 -> 33
  2. 11 进 -> 11 出 -> 22 进 -> 33 进 -> 33 出 -> 22
  3. 11 进 -> 22 进 -> 22 出 -> 11 出 -> 33 进 -> 33
  4. 11 进 -> 22 进 -> 22 出 -> 33 进 -> 33 出 -> 11
  5. 11 进 -> 22 进 -> 33 进 -> 33 出 -> 22 出 -> 11

无论怎样出栈入栈,都不可能得到 (3,1,2)(3, 1, 2) 排列。这 5 种排列中的每一个都对应于具有三个结点的 5 个不同的二叉树中的一个。

5-37

  • n+1n + 1 个矩阵相乘的不同方法数』

假设要计算下面的 nn 个矩阵的乘积: M1M2Mn M_1 * M_2 * \cdots * M_n 由于矩阵乘法满足结合律,因此,可以按任意的顺序执行矩阵乘法操作。如果 n=3n = 3,那么有如下两种可能的结合方法: (M1M2)M3 (M_1 * M_2) * M_3 M1(M2M3) M_1 * (M_2 * M_3) 如果 n=4n = 4,则有以下五种可能的结合方法: ((M1M2)M3)M4 ((M_1 * M_2) * M_3) * M_4 (M1(M2M3))M4 (M_1 * (M_2 * M_3)) * M_4 M1((M2M3)M4) M_1 * ((M_2 * M_3) * M_4) M1(M2(M3M4)) M_1 * (M_2 * (M_3 * M_4)) (M1M2)(M3M4) (M_1 * M_2) * (M_3 * M_4) bnb_n 是计算 nn 个矩阵乘积不同的方法数。那么 b2=1b_2 = 1b3=2b_3 = 2b4=5b_4 = 5。令 Mij,ijM_{ij}, i \leq j 为矩阵 MiMi+1MjM_i * M_{i+1} * \cdots * M_j 的乘积。如果要计算的乘积是 M1nM_{1n},可以通过计算任何的 M1iMi+1,n(1in)M_{1i} * M_{i+1, n}(1 \leq i \leq n) 来计算 M1nM_{1n}。由于计算 M1iM_{1i}Mi+1,nM_{i+1, n} 的不同结合的方法数分别为 bib_ibnib_{n-i}。因此,令 b1=1b_1 = 1,有: bn=i=1n1bibni, n>1 b_n = \sum_{i=1}^{n-1}b_ib_{n-i},\ n>1 如果能够唯一确定 bnb_n 的关于 nn 的表达式,那么就得到问题的解。

现在令 bnb_n 为具有 nn 个结点的不同的二叉树的个数。且 bnb_n 是所有可能的二叉树的个数,这些二叉树都是按如下方式形成的:一个根结点和两棵结点个数分别为 bib_ibni1b_{n-i-1} 的子树,其中 0i<n0 \leq i < n。如下图。

所以, bn=i=0n1bibni1, n1, and b0=1 b_n = \sum_{i=0}^{n-1}b_ib_{n-i-1}, \ n \geq 1, \ \mathrm{and} \ b_0 = 1 这个公式和前一个公式在本质上是相同的。因此,具有 nn 个结点的二叉树的个数,用栈得到的 11nn 的排列个数和 n+1n + 1 个矩阵乘法的结合方法数是相等的。

因此,以上三个问题都有相同的答案。

  • 『结果』

B(x)=i0bixi B(x) = \sum_{i \geq 0} b_ix^i 这是计算二叉树个数的生成函数。其次,由递归关系得到的等式: xB2(x)=B(x)1 xB^2(x) = B(x) - 1 根据这个公式来解一元二次方程,并注意 B(0)=b0=1B(0) = b_0 = 1 得: B(x)=114x2x B(x) = \frac{1 - \sqrt{1 - 4x}}{2x} 使用二项式定理展开 (14x)1/2(1-4x)^{1/2},得到: B(x)=12x[1n0(1/2n)(4x)n]=m0(1/2n+1)(1)m22m+1xm \begin{aligned} B(x) & = \frac{1}{2x}\left[1 - \sum_{n \geq 0}\binom{1/2}{n}(-4x)^n \right] \\ & = \sum_{m \geq 0} \binom{1/2}{n+1}(-1)^m2^{2m+1}x^m \end{aligned} 与第一个方程相比,可以看出,在 B(x)B(x) 中的 xnx^n 的系数 bnb_n 是: (1/2n+1)(1)n22n+1 \binom{1/2}{n+1}(-1)^n2^{2n+1} 化简得: bn=1n+1(2nn) b_n = \frac{1}{n+1}\binom{2n}{n} 该值近似为: bn=O(4n/n3/2) b_n = O(4^n/n^{3/2}) .

results matching ""

    No results matching ""