树到二叉树的转换（三十五）

我们在之前学习了通用树的相关知识，那么通用树的结构实现相对来说比较复杂，有没有一种比较简单的树呢？我们在之前的通用树结构中使用的是双亲孩子表示法，每个结点都有一个指向其双亲的指针，每个结点都有若干个指向其孩子的指针。结构如下图所示

那么还有另一种树结构模型 -- 孩子兄弟表示法。每个结点都有一个指向其第一个孩子的指针，每个结点都有一个指向其第一个右兄弟的指针。结构如下图所示

孩子兄弟表示法的特点：1、能够表示任意的树形结构；2、每个结点包含一个数据成员和两个指针成员；3、孩子结点指针和兄弟结点指针构成了"树杈"。

下来我们来看看二叉树的定义：二叉树是由 n ( n >= 0 ) 个结点组成的有限集合，该集合或者为空，或者是由一个根结点加上两颗分别称为左子树和右子树的、互不相交的二叉树组成。二叉树有以下 5 种形态

下来我们来看看两种特殊的二叉树：满二叉树（Full Binary Tree）和完全二叉树（Complete Binary Tree）。

1、满二叉树：如果二叉树中所有分支结点的度数都为 2，且叶子结点都在同一层次上，则称这类二叉树为满二叉树。

2、完全二叉树：如果一颗具有 n 个结点的高度为 K 的二叉树，它的每一个结点都与高度 K 的满二叉树中编号为 1 -- n 的结点一一对应。则称这颗二叉树为完全二叉树（从上到下从左到右编号）。

完全二叉树的相关特性：a> 同样结点数的二叉树，完全二叉树的高度最小；b> 完全二叉树的叶结点仅出现在最下面两层：最底层的叶结点一定出现在左边，倒数第二层的叶结点一定出现在右边，完全二叉树中度为 1 的结点只有左孩子。如下图所示

下来我们来看看二叉树的几个性质：

1、在二叉树的第 i 层最多有 2^i-1 个结点（i >= 1）。

第一层最多有 2^1-1 = 1 个结点；

第二层对多有 2^2-1 = 2 个结点；

第三层最多有 2^3-1 = 4 个结点；

......

2、高度为 k 的二叉树最多有 2^k-1个结点（k >= 0）。

如果有一层，最多有 1 = 2^1-1 = 1 个结点；

如果有二层，最多有 1 = 2^2-1 = 3 个结点；

如果有三层，最多有 1 = 2^3-1 = 7 个结点；

......

3、对任何一颗二叉树，如果其叶结点有 n₀ 个，度为 2 的非叶结点有 n₂ 个，则有 n₀ = n₂ + 1。

证明：假设二叉树中度 1 的结点有 n₁个且总结点为 n 个，则： n = n₀ + n₁ + n₂；

假设二叉树中连接父结点与子结点间的边为 e 条，则： e = n₁ + 2n₂ = n -1 ；

所以：n₀ = n₂ + 1

4、具有 n 个结点的完全二叉树的高度为[log₂n] + 1。（[X] 表示不大于 X 的最大整数）。

证明：假设这 n 个结点组成的完全二叉树高度为 k，则： 2^k-1-1 < n <= 2^k-1；

因为 n 为整数，所以： 2^k-1 <= n < 2^k；

取对数：k-1 <= log₂n < k；

因为 k 为整数，所以：k = [log₂n] + 1

5、一颗有 n 个结点的完全二叉树（高度为[log₂n] + 1），按层次对结点进行编号（从上到下，从左到右），对任意结点 i 有：

如果 i = 1，则结点 i 是二叉树根；如果 i > 1，则其双亲结点为 [i/2]；

如果 2i <= n，则结点 i 的左孩子为 2i；如果 2i > n，则结点 i 无左孩子；

如果 2i+1 <= n，则结点 i 的右孩子为 2i+1；如果 2i+1 > n，则结点 i 无右孩子；

通过对二叉树的学习总结如下：1、通用树结构采用了双亲结点表示法进行描述；2、孩子兄弟表示法有能力描述任意类型的树结构；3、孩子兄弟表示法能够将通用树转化为二叉树；4、二叉树是最多只有两个孩子的树。