一、树的几个概念
1、度：儿子结点的个数
2、叶结点：度=0的结点
3、分支结点：度≠0的结点
4、内部结点：除根结点外的分支结点
5、祖先：父结点和自身（不包含自身的叫做真祖先）
6、子孙：子结点和自身（不包含自身的叫做真结点）
7、结点的高度：结点到各个叶结点的最长路径的长度
二、二叉树
二叉树的基本概念
1、二叉树中，每个结点至多有两个儿子结点，而且区分左儿子和右儿子
2、有序树只有一个儿子时，无需区分左右次序，而二叉树即使只有一个儿子也有左右之分
3、二叉树不是树的特殊情形
4、完全二叉树：除了最后一层，其他每层的结点都满了，最后一层可以有右边的结点没满
5、满二叉树：每一层的结点都满了，近似满二叉树：没有左儿子，就一定没有右儿子
二叉树的重要性质
1、高度为h的二叉树至少有h+1个结点，至多有2^(h+1) - 1个结点
2、含有n个结点的向下取整(logn) <= 二叉树高度 <= n-1
3、含有n个结点的二叉树共有C(2n, n) / (n+1)种形态
4、对任意的非空二叉树T，如果叶结点的个数为n0，而其度为2的结点数为n2，则：n0 = n2 + 1
5、要确定一个二叉树，必须要有中序遍历序列
三、哈夫曼树
1、概念：给定n个权值作为n个叶子结点，构造一颗二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树
2、基本术语：
1）结点的权：给结点的一个赋予某种含义的数值
2）带权路径长度：根结点到该结点的路径长度 × 结点的权
3）树的带权路径长度：即WPL，为根结点的带权路径长度之和
3、构造哈夫曼树：
4、哈夫曼编码：
由于哈夫曼树具有离根结点近的权值大，离根结点远的权值小的特点。而在通信中，我们希望能够尽量缩短传送的二进制串长度，对于这种情况下，采用何种编码就成为了一个重要的问题。而我们只要让高频字符用短编码，低频字符用较长编码，就能实现整体编码长度最优，而哈弗曼树刚好适应于这种场景，所以产生了哈夫曼编码
1）首先假设我们要传送“ADDDAAABBCCCDDDA”，我们可以先统计词频，如下：A（5）、B（2）、C（3）、D（6）
2）我们把词频作为权值，构造哈夫曼树得：
3）可以对每个叶子结点进行编码，编码规则为左边的路径权值为1，右边的路径权值为0，如此构造得：
- D -> 6：0
- A -> 5：10
- B -> 2：111
- C -> 3：110
4）所以，串就可以以上述编码发送：
1000010101011111111011011000010