树到二叉树的转换（三十五）
我们在之前学习了通用树的相关知识，那么通用树的结构实现相对来说比较复杂，有没有一种比较简单的树呢？我们在之前的通用树结构中使用的是双亲孩子表示法，每个结点都有一个指向其双亲的指针，每个结点都有若干个指向其孩子的指针。结构如下图所示
创新互联公司主要从事网站建设、网站设计、网页设计、企业做网站、公司建网站等业务。立足成都服务桃江,10年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18982081108
那么还有另一种树结构模型 -- 孩子兄弟表示法。每个结点都有一个指向其第一个孩子的指针，每个结点都有一个指向其第一个右兄弟的指针。结构如下图所示
孩子兄弟表示法的特点：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 层最多有 2i-1 个结点（i >= 1）。
第一层最多有 21-1 = 1个结点；
第二层对多有 22-1 = 2个结点；
第三层最多有 23-1 = 4 个结点；
......
2、高度为 k 的二叉树最多有 2k-1个结点（k >= 0）。
如果有一层，最多有 1 = 21-1 = 1 个结点；
如果有二层，最多有 1 = 22-1 = 3 个结点；
如果有三层，最多有 1 = 23-1 = 7 个结点；
......
3、对任何一颗二叉树，如果其叶结点有 n0 个，度为 2 的非叶结点有 n2 个，则有 n0 = n2 + 1。
证明：假设二叉树中度 1 的结点有 n1个且总结点为 n 个，则： n = n0 + n1 + n2；
假设二叉树中连接父结点与子结点间的边为 e 条，则： e = n1 + 2n2 = n -1 ；
所以：n0 = n2 + 1
4、具有 n 个结点的完全二叉树的高度为[log2n] + 1。（[X] 表示不大于 X 的最大整数）。
证明：假设这 n 个结点组成的完全二叉树高度为 k，则： 2k-1-1 < n <= 2k-1；
因为 n 为整数，所以： 2k-1 <= n < 2k；
取对数：k-1 <= log2n < k；
因为 k 为整数，所以：k = [log2n] + 1
5、一颗有 n 个结点的完全二叉树（高度为[log2n] + 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、二叉树是最多只有两个孩子的树。
分享名称：树到二叉树的转换（三十五）
网页链接：http://myzitong.com/article/jhsioc.html