1.树的基本知识
树是什么树是由边和节点构成的数据结构。节点通常就是存储数据的实体。
树的常见术语
1）根：树的顶端节点。一棵树只有一个根。
2）边：节点到节点的连接
3）路径：沿着边，从一个节点走到另一个节点，所经过的节点顺序称为路径
4）父节点、子节点
5）节点、叶节点
6）度：一个节点包含的子节点数
7）子树
8）层：就是从根开始到这个节点的“代”，层数也称为高度或深度
9）遍历：按照某个特定的顺序访问节点
10）关键字：节点对象域中的某个属性，用来识别节点对象
2.二叉树的概念和理解
二叉树是什么如果树中的每个节点，最多只能有两个子节点，这样的树称为二叉树。
二叉树理解
1、二叉树不是树的特殊情形，其区别为：
1）树中节点的字节点树没有限制，而二叉树中限制节点数为不超过2个
2）树的节点没有左右之分，二叉树节点是分左右的2、二叉树有五种基本形态
1）空二叉树，连根节点都没有
2）只有一个根节点的二叉树
3）只有左树
4）只有右树
5）完全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。3、满二叉树：除叶节点外，每一个节点都有左右子节点，且叶子结点都处在最底层的二叉树
4、满二叉树肯定是完全二叉树，完全二叉树不一定是满二叉树。
5、二叉树常被用作二叉查找树、二叉排序树、二叉堆。
3.二叉树的性质
- 性质1：在二叉树的第 i 层上至多有2^(i-1)个结点
- 性质2：深度为k的二叉树至多有 2^k -1个结点
- 性质3：对任何一颗二叉树T，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1
- 性质4：具有N个结点的完全二叉树的深度为[log2为底N]+1
- 性质5：如果对一棵有N个结点的完全二叉树的结点按层序编号，即从第 1层到第[log2为底N]+1层，每层从左到右，对任一结点i(1<=i<=n)有：
（1）如果i=1，则结点i是二叉树的根；如果i>1，则其父结点是[i/2]
（2）如果2i>n，则结点i无左子节点；否则其左子节点是2i。也就是该节点是叶子节点。
（3）如果2i+1>n，则结点i无右子节点；否则其右子节点是2i+1
（4）若i为奇数且不为1，则Ki的左兄弟的编号是i-1；否则，Ki无左兄弟
（5）若i为偶数且小于n，则Ki的右兄弟的编号是i+1；否则，Ki无右兄弟
4.二叉搜索树的查找、插入、遍历、查找最大最小值和删除操作的实现
二叉搜索树是什么如果一棵二叉树，满足：左子节点的值小于节点的值，而右子节点的值大于节点的值，就被称为二叉搜索树。
提示：删除节点有两个子节点的时候，要用它的中序后继来代替该节点，算法是：找到被删除节点的右子节点，然后查找这个右子节点下的最后一个左子节点，也就是这颗子树的最小值节点，这就是被删除节点的中序后继节点。
二叉搜索树操作的效率常见的操作效率是：O(logN)，是以 2为底的
用数组来表示树把树的节点遍上序号，按序存放到数组中。这样一来，查找节点就变成了查找相应的索引了。这种方法不常用，了解即可。这种方式效率不高，因为不满的节点，还有删除的节点，在数组中留下了洞，更糟糕的是删除节点时，如果需要移动子树的话，就更浪费时间了。
5.哈夫曼编码和哈夫曼树的基本知识
5.1 哈夫曼(Huffman)编码
霍夫曼编码是一种统计编码，属于无损压缩编码。
其基本思路是：对每个字符编码的码长是变化的，对于出现频率高的，编码的长度较短；而对于出现频率低的，编码长度较长。编码规则还要求：每个编码都不能是其它字符编码的前缀。
5.2 哈夫曼树
哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL= (W1L1+W2L2+W3L3+...+WnLn)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)要使其WPL值最小，必须使权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。
6.哈夫曼算法
哈夫曼树的构造方法——Huffman算法
- step1.对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}，构成n棵只有根节点的二叉树，令起始权值为Wj，为方便处理，可以按照权值进行升序排列
- step2.在这些二叉树中，选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
- step3.从森林中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到森林中。
- step4.重复2和3两步，直到森林中只有一棵二叉树为止
7.使用哈夫曼算法来实现压缩和解压的功能
哈夫曼压缩的编码部分的实现步骤：
- step1.统计：读入要压缩的源文件，统计字符出现的次数
- step2.建树：构建哈夫曼树
- step3.编码：对哈夫曼树的左边记0，右边记1，就可以得到字符的哈夫曼编码。
- step4.输出：把编码序列输出，这就是压缩后的数据
哈夫曼压缩的解码部分的实现步骤 ：
- step1.读取码表的信息，构建出码表来
- step2.读回具体的数据内容
- step3.把读回的字节还原成对应的整型数据
- step4.根据码表，把内容组成的哈夫曼编码，依次转换回原始的字符，从而得到原始的
