二叉树
一般来说，二叉树使用链表来定义----二叉链表
完全二叉树
1. 对完全二叉树当中的任何一个结点（设编号为x），其左孩子编号一定为2x，右孩子编号一定是2x+1。也就是说，完全二叉树可以通过建立一个大小为的数组来存放所有结点的信息，其中k为完全二叉树的最大高度，且1号位存放的必须是根结点。
2. 如果题目中已经规定是完全二叉树，那么数组大小只需设为结点上限个数加1即可，这将会大大节省编码复杂度。
3. 数组中元素存放的顺序恰好为该完全二叉树的层序遍历序列。
4. 判断某个结点是否为叶结点的标志为：该叶结点(记下标为root)的左叶子结点的编号root*2大于结点总个数n
5. 判断某个结点是否为空结点的标志：该结点下标root大于结点总个数n
二叉树的遍历
二叉树的遍历是指通过一定的顺序访问二叉树的所有结点。遍历的方法一般有四种：先序遍历、中序遍历、后序遍历以及层序遍历。其中，前三种一般使用深度优先搜索实现，而层次遍历一般用广度优先搜索实现。
树的遍历
二叉查找树BST
二叉查找树是一种特殊的二叉树，又称排序二叉树、二叉搜索树、二叉排序树。二叉查找树的递归定义如下：
1. 要么二叉查找树是一棵空树。
2. 要么二叉查找树中各结点数据域左<=根<右
对二叉查找树进行中序遍历，遍历的结果是有序的。
平衡二叉树AVL
AVL树仍是一棵二叉查找树。所谓平衡是指，对AVL树的任意结点来说，其左子树与右子树的高度之差的绝对值不超过1，其中左子树与右子树的高度之差称为该结点的平衡因子。
并查集
并查集用数组实现：int father[N];其中father[i]表示元素i的父亲结点。另外，如果father[i]==i，则说明元素i是该集合的根结点，但对同一个集合来说只存在一个根结点，且将其作为所属集合的标识。
堆
1. 堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子结点的值。
2. 堆一般用于优先队列的实现，而优先队列默认情况下使用的是大顶堆。
3. 建堆--向下调整；添加元素--向上调整
假设序列中元素个数为n，由于完全二叉树的叶子结点个数为n/2向上取整，因此数组下标在[1,n/2向下取整]范围内的结点都是非叶子结点。于是可以从n/2向下取整号位开始倒着枚举结点，对每个遍历到的结点i进行[i,n]范围的调整。为什么要倒着枚举？这是因为每次调整完一个结点后，当前子树中权值最大的结点就会处在根结点的位置，这样当遍历到其父亲结点时，就可以直接使用这个结果。也就是说，这种做法保证每个结点都是以其为根结点的子树中的权值最大的结点。
哈夫曼树
1. 非叶结点的权值之和 = 树的带权路径长度（叶结点的带权路径长度之和）
2. 对同一组叶子结点来说，哈夫曼树可以是不唯一的，但是最小带权路径长度一定是唯一的
3. 对哈夫曼树来说，不存在度为1的结点
哈夫曼编码
1. 对于任何一个叶子结点，其编号一定不会成为其他任何一个结点编号的前缀
2. 前缀编码的存在意义在于不产生混淆，让解码能够正常进行
3. 哈夫曼编码是能使给定字符串编码成01串后长度最短的前缀编码
4. 哈夫曼编码是根据各字符的出现次数建立哈夫曼树，因此哈夫曼编码是针对确定的字符串来讲的
