一、概述

        在某个阶段都是两种结果的情形，比如开和关、0和1、真和假、上和下、对与错、正面和反面，都适合用一种很特殊的树状结构 建来建模，即为二叉树。定义如下：

1、二叉树的特点：Degree≤2

2、二叉树具有五种基本形态：

二、特殊二叉树

1、斜树

• 左/右斜树：所有的结点都只有左/右子树，统称为斜树。
• 特点：每一层都只哟一个结点，结点的个数与二叉树的深度相同，即Depth=n.
• 线性表结构可以理解为是树的一种及其特殊的表现形式。

2、满二叉树（完美二叉树）

注意：单是每个节点都存在左右子树不蹦不能算满二叉树，还必须要所有的叶子都在同一层上，这就做到了整棵树的平衡。

• 满二叉树的特点：

3、完全二叉树

注意理解：满（完美）和完全

满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的。

举例说明：

完全二叉树的特点：

判断完全二叉树：

三、二叉树的性质

• 2^0、2^1、2^2......等比数列：2……i-1
• 用途：计算每次的结点数

• 2^0、2^0+2^1、2^0+2^1+2^2、......等比数列求和：（2^k）-1
• 用途：知道深度求结点数的范围

• 终端结点就是叶子结点。

    总结点数：n = n0+n1+n2

    总连接数：n-1=2*n2+1*n1+0*n0   注意：n-1代表根节点没有进入线。

    联立上边两个式子得到：n0=n2+1

• 用途：知道度为2的结点数求叶子结点。

深度和总结点数的关系由性质2可得：n=（2^k）-1，则k=log2(n+1)

深度为k-1的总结点数 <= 总结点数 <= 深度为k的总结点数

即(2^(k-1))-1 < n <= （2^k）-1，因为n为整数，这里可以去掉等号即为2^(k-1) <= n < 2^k

取对数得：k-1<=log2(n)<k

k为整数，因此k的取值范围为：

• 用途：知道结点数求深度的范围

可自行验证：

• 用途：知道某个编号，求双亲编号、子树编号，判断结点有无兄弟，判断结点是否为叶结点等。

四、二叉树的存储结构

1、顺序存储结构：一般只用于完全二叉树，因为完全二叉树具有严格的定义

用^来表示不存在的结点。

对于不是完全二叉树的树，数组中会有很多^，造成空间浪费，尤其是右斜树。

2、二叉链表

二叉树每个结点最多有两个孩子，所有设计一个数据域和两个指针域，称为二叉链表。

• data：数据域
• lchild：存放左孩子的指针
• rchild：存放右孩子的指针

如有需要，可以增加一个指向双亲的parent指针域，即成为三叉链表。

五、遍历二叉树

1、访问

2、遍历

3、二叉树遍历方法

• 前序遍历

• 中序遍历

• 后续遍历

• 层序遍历

4、研究遍历的意义：

六、线索二叉树

        对于一个有n个结点的二叉链表，每个结点有指向左右孩子的两个指针域，一共2n个指针域。而n个结点的二叉树一共n-1条分支线，也就是存在2n-(n-1)=n+1个空指针域。

        为了利用这些空指针域，提出线索二叉树。

指向前驱和后继的指针称为线索，加上线索的二叉链称为线索链表，相应的二叉树称为线索二叉树。

中序遍历：HDIBEAFCG

所有的空指针域中的rchild改为指向它的后继结点，lchild改为指向它的前驱结点。如下：

线索二叉树，等于是把一课二叉树转变成了一个双向链表，这样对插入删除结点、查找某个结点都带来了方便。对其遍历，其实就等于是操作一个双向链表结构。

线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程。

此时遇到一个问题：lchild指向的是它的左孩子还是指向前驱，rchild指向的是它的右孩子还是指向后继？

因此增设两个标志域（boolean）：ltag和rtag，只能存放0和1。

七、树、森林与二叉树的转换

1、树——二叉树

2、森林——二叉树

3、二叉树——树

4、二叉树——森林

5、树与森林的遍历

八、哈弗曼树

最基本的压缩编码方法——哈弗曼编码

1、哈弗曼树

• 路径长度：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称作路径长度。
• 树的路径长度：从树根到每一结点的路径长度之和。

a树的路径长度为20，b树的路径长度为16。

考虑带权的结点：

• 结点的带权的路径长度：该结点到树根之间的路径长度与结点上权的乘积。
• 树的带权路径长度：树中所有叶子结点的带权路径长度之和。

2、构造哈弗曼树的步骤：

3、哈夫曼编码