第六章：树和二叉树
1.树：是n(n≥0)个结点的有限集。(1)有且仅有一个特定的称为根（root）的结点;（2）当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树 。
2.二叉树：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。
二叉树的性质，存储结构。
性质1: 在二叉树的第i层上至多有2^(i-1)个结点（i>0）。
性质2: 深度为k的二叉树至多有2^k-1个结点（k>0）。
性质3: 对于任何一棵二叉树，如果其终端结点数为n0,度为2的结点数有n2个，则叶子数n0=n2＋1
性质4: 具有n个结点的完全二叉树的深度必为 [log2n]+1
性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）。
二叉树的存储结构：
1).顺序存储结构
按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。
若是完全/满二叉树则可以做到唯一复原。
不是完全二叉树：一律转为完全二叉树！
方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。
缺点：①浪费空间；②插入、删除不便
2).链式存储结构
用二叉链表即可方便表示。一般从根结点开始存储。
lchild
data
rchild
优点：①不浪费空间；②插入、删除方便
3.二叉树的遍历。
指按照某种次序访问二叉树的所有结点，并且每个结点仅访问一次，得到一个线性序列。
遍历规则:二叉树由根、左子树、右子树构成，定义为D、 L、R
若限定先左后右，则有三种实现方案：
DLR LDR LRD
先序遍历 中序遍历 后序遍历
4.线索二叉树
1）线索二叉树可以加快查找前驱与后继结点，实质就是将二叉链表中的空指针改为指向前驱或后继的线索，线索化就是在遍历中修改空指针。
通常规定：对某一结点，若无左子树，将lchild指向前驱结点；若无右子树，将rchild指向后继结点。
还需要设置左右两个tag，用来标记当前结点是否有子树。
若ltag==1,lchild指向结点前驱；若rtag==1，rchild指向结点后继。
2）线索二叉树的存储结构如下：
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag;
}ThreadNode, *ThreadTree;
5.树和森林
1）树有三种常用存储方式：
①双亲表示法 ②孩子表示法 ③孩子—兄弟表示法
2）森林、树、二叉树的转换
(1)将树转换为二叉树
树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：a.在所有兄弟结点之间加一连线
b.对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。
(2)将一个森林转换为二叉树：
具体方法是：a.将森林中的每棵树变为二叉树；
b.因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。
(3)二叉树转换为树
是树转换为二叉树的逆过程。
a.加线。若某结点X的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点，都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来。
b.去线。删除原二叉树中所有结点与其右孩子结点的连线。
(4)二叉树转换为森林：
假如一棵二叉树的根节点有右孩子，则这棵二叉树能够转换为森林，否则将转换为一棵树。
a.从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除。直到所有这些根节点与右孩子的连线都删除为止。
b.将每棵分离后的二叉树转换为树。
6.树和森林的遍历
树的遍历
① 先根遍历：访问根结点；依次先根遍历根结点的每棵子树。
② 后根遍历：依次后根遍历根结点的每棵子树；访问根结点。
森林的遍历
① 先序遍历
若森林为空，返回；
访问森林中第一棵树的根结点；
先根遍历第一棵树的根结点的子树森林；
先根遍历除去第一棵树之后剩余的树构成的森林。
② 中序遍历
若森林为空，返回；
中根遍历森林中第一棵树的根结点的子树森林；
访问第一棵树的根结点；
中根遍历除去第一棵树之后剩余的树构成的森林。
7.哈夫曼树及其应用
Huffman树：最优二叉树（带权路径长度最短的树）
Huffman编码：不等长编码。
树的带权路径长度：(树中所有叶子结点的带权路径长度之和)
构造Huffman树的基本思想：权值大的结点用短路径，权值小的结点用长路径。
构造Huffman树的步骤（即Huffman算法）：
(1) 由给定的 n 个权值{ w1, w2, …, wn }构成n棵二叉树的集合F = { T1, T2, …, Tn } （即森林） ，其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均空。
(2) 在F 中选取两棵根结点权值最小的树 做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。
(3) 在F 中删去这两棵树，同时将新得到的二叉树加入 F中。
(4) 重复(2) 和(3) , 直到 F 只含一棵树为止。这棵树便是Huffman树。
具体操作步骤：
应用：用于通信编码
在通信及数据传输中多采用二进制编码。为了使电文尽可能的缩短，可以对电文中每个字符出现的次数进行统计。设法让出现次数多的字符的二进制码短些，而让那些很少出现的字符的二进制码长一些。假设有一段电文，其中用到 4 个不同字符Ａ，Ｃ，Ｓ，Ｔ，它们在电文中出现的次数分别为 7 ， 2 ， 4 ， 5 。把 7 ， 2 ， 4 ， 5 当做 4 个叶子的权值构造哈夫曼树如图(a) 所示。在树中令所有左分支取编码为 0 ，令所有右分支取编码为1。将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列，就得这个叶子结点所代表的字符的二进制编码，如图(b) 所示。这些编码拼成的电文不会混淆，因为每个字符的编码均不是其他编码的前缀，这种编码称做前缀编码。