512 二叉树、树、森林的结构等价性

二叉树、树、森林的结构等价性

数量等价关系

• 双射映射：一棵树或一个森林可以唯一地转换成一棵二叉树，反之亦然。这种转换关系是一一对应的，即存在双射映射。
• 转换方法：
  • 树到二叉树的转换（左子右兄表示法）
  • 森林到二叉树的转换
  • 二叉树到森林的转换

形态数计算

无标号情形

• 定义：指结点之间没有区别（不可区分）的树或二叉树的形态种类数。
• Catalan 数 (卡特兰数)：
  • 对于 $n$ 个结点的无标号二叉树的形态数 $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$。
  • 对于 $n$ 个结点的无标号树的形态数也满足卡特兰数 $C_{n-1}$ (对于 $n$ 个结点的树，可以看作 $n-1$ 个结点的二叉树形态)。
  • 递推公式：$C_0=1,C_n={\sum }_{i=0}^{n-1}{C}_i{C}_{n-1-i}$ 对于 $n\ge 1$。
  • 前几项：$C_0=1,C_1=1,C_2=2,C_3=5,C_4=14,C_5=42,\dots$
• 特殊形态下的无标号形态数：
  • 完全左/右斜二叉树：对于 $n$ 个结点的二叉树，只有一种形态是完全左斜树或完全右斜树。
  • 满二叉树：对于给定高度 $h$ (或给定结点数 $n=2^{h+1}-1$) 的满二叉树，只有一种形态。
  • 完全二叉树：对于给定结点数 $n$ 的完全二叉树，只有一种形态。

有标号情形

• 定义：指结点之间有区别（可区分）的树或二叉树的形态种类数。
• 有标号二叉树：
  • 对于 $n$ 个结点的有标号二叉树的形态数：$C_n\times n!=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)\times n!=\frac{(2n)!}{(n+1)!n!}$。
  • 考虑每个结点都可以是左孩子或右孩子，且结点有标号。
• 有标号树 (Cayley 定理)：
  • 对于 $n$ 个结点的有标号树的形态数是 $n^{n-2}$。
  • 例如，3 个结点的有标号树有 $3^{3-2}=3$ 种。
  • 证明方法：可以通过 Prüfer 序列来证明。

实际应用

• 数据结构表示：树或森林可以通过二叉树（孩子 - 兄弟表示法）来存储和操作，简化了存储结构和算法设计。
• 编译原理：抽象语法树（AST）的构建和遍历。
• 文件系统：目录结构通常是树形结构，其遍历和管理可以借鉴树的遍历算法。
• 算法设计：许多树相关的算法，如查找、插入、删除等，可以通过转换为二叉树后使用二叉树的算法来解决。
• 组合数学：卡特兰数在计算机科学和数学中广泛应用于计数问题，如括号匹配、出栈序列、凸多边形三角划分等。

二叉树空指针结点计算

• 空指针域：在二叉树的链式存储结构中，当一个结点没有左孩子或右孩子时，其对应的指针域（lchild 或 rchild）会存储一个空值（例如 NULL 或 nullptr），表示该方向上没有子结点。
• lchild 指针：指向该结点的第一个孩子。
• rchild 指针：指向该结点的下一个兄弟。

非终端结点（在原树/森林中）

• 定义：指在原树/森林中至少有一个孩子的结点。
• 在转换后的二叉树中，右指针域为空：
  • 如果一个结点在其二叉树表示中的 rchild 指针为空，则说明在原树/森林中，该结点没有右兄弟。
  • 示例：考虑一棵树的根结点，如果它是森林中的最后一棵树的根，或者如果它作为单棵树的根，它就没有右兄弟。

叶结点（在原树/森林中）

• 定义：指在原树/森林中没有孩子的结点。
• 在转换后的二叉树中，左指针域为空：
  • 如果一个结点在其二叉树表示中的 lchild 指针为空，则说明在原树/森林中，该结点没有孩子，即它是一个叶结点。

空指针域计算

右指针域为空的结点计算

定理 1：如果森林 $F$ 有 $n$ 个非终端结点，则转换后的二叉树 $B$ 中右指针域为空的结点数为 $n+1$。

证明：

• 设森林 $F$ 中有 $k$ 棵树，每棵树的根结点都没有右兄弟
• 每个非终端结点的孩子序列中，最右边的孩子没有右兄弟
• $n$ 个非终端结点产生 $n$ 个 ” 最右孩子 “，右指针域为空
• 加上 $k$ 个树根，但森林根结点已计入，实际增加 $(k-1)$ 个
• 由于每棵树至少有一个根结点为非终端结点，所以 $k\le n+1$
• 实际上，右空指针数 = $n+1$

左指针域为空的结点计算

定理 2：一个有 $n$ 个结点的树，其叶结点个数为 $m$，则该树对应二叉树中无左孩子的结点个数为 $m$。

证明：

• 在树到二叉树转换中，左指针 $lchild$ 连接第一个孩子
• 当且仅当原树中的结点为叶结点时，转换后左指针域为空
• 因此无左孩子的结点数 = 原树中叶结点数 = $m$

无右孩子结点计算

定理 3：一个有 $n$ 个结点的树，其叶结点个数为 $m$，则该树对应二叉树中无右孩子的结点个数为 $n-m+1$。

证明：

• 设原树有 $n$ 个结点，其中叶结点 $m$ 个，非终端结点 $(n-m)$ 个
• 在转换后的二叉树中，右指针连接兄弟结点
• 每个非终端结点的孩子中，只有最右边的孩子无右兄弟
• $(n-m)$ 个非终端结点产生 $(n-m)$ 个最右孩子，右指针为空
• 另外，树根也无右兄弟，右指针为空
• 因此无右孩子的结点数 = $(n-m)+1=n-m+1$

验证：对于 $n$ 个结点的二叉树，总空指针数为 $n+1$

$$\text{左空指针数}+\text{右空指针数}=m+(n-m+1)=n+1$$