一、树

1、树的定义

树是 N（N >= 0）个结点的有限集合。
当 N =0 时，称为 空树 ；
当 N >0 时，应满足：

1）有且仅有一个特定的称为根的结点，它没有直接前驱，但有零个或多个后继。
2）其余n-1个结点可分为m（m>=0)个互不相交的有限集T1,T2,....,Tm, 其中Ti又是一棵树，并且称为根的子树

2、相关术语

结点的度 ：结点的子树个数
树的度（阶）：树的所有结点中最大的度数 N，同时这棵可称为 N 叉树
叶结点 ：度为 0 的结点
父结点 ：有子树的结点是其子树的根节点的父结点
子结点 ：若 A 结点是 B 结点的父结点，则称 B 结点是 A 结点的子结点
兄弟结点 ：具有同一个父结点的各结点彼此是兄弟结点
祖先结点 ：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点
子孙结点 ：某一结点的子树中的所有结点是这个结点的子孙
结点的层次 ：规定根结点在 1 层，其他任一结点的层数是其父结点的层数加 1
树的深度 ：树中所有结点中的最大层次是这棵树的深度
有序树 ：树中任意节点的子结点之间有顺序关系；反之称为 无序树
森林 ：由 m（m >= 0）个互不相交的树组成的集合被称为森林
路径 ：从一个结点往下可以达到的孩子或孙子结点之间的通路
路径长度 ：通路中分支的数目。若规定根结点的层数为 1，则从根结点到第 L 层结点的路径长度为 L -1
结点的权 ：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权
结点的带权路径长度 ：从根结点到该结点之间的路径长度与该结点的权的乘积
树的带权路径长度 ：所有叶子结点的带权路径长度之和，记为 WPL
结点的平衡因子 ：某节点的左子树与右子树的高度(深度) 差

二、二叉树

1、二叉树定义

每个结点至多拥有两棵子树的树结构。并且，二叉树的子树有左右之分，其次序不能任意颠倒。

2、类型

满二叉树 ：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层

完全二叉树 ：叶结点只能出现在最底层的两层，且最底层叶结点均处于次底层叶结点的左侧

3、遍历

按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
先序遍历 ：首先访问根，再先序遍历左子树，最后先序遍历右子树
中序遍历 ：首先中序遍历左子树，再访问根，最后中序遍历右子树
后序遍历 ：首先后序遍历左子树，再后序遍历右子树，最后访问根
层序遍历 ：首先访问第一层的根节点，然后从左到右访问第 2 层上的节点，以此类推，自上而下，自左至右逐层访问

4、树的转换

树转换为二叉树

1）加线。在所有兄弟结点之间加一条连线。
2）去线。树中的每个结点，只保留它与第一个孩子结点的连线，删除它与其它孩子结点之间的连线。
3）层次调整。以树的根节点为轴心，将整棵树顺时针旋转一定角度（第一个孩子是左孩子，其余结点是右孩子）

二叉树转换为树

1）加线。若某结点X的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点…，都作为结点X的孩子。
2）去线。删除原二叉树中所有结点与其右孩子结点的连线。
3）层次调整。孩子靠左排列

三、线索二叉树（二叉树变种）

对于 n 个结点的二叉树，在二叉链存储结构中有 n + 1 个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。
根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。同时为了区别线索指针和孩子指针，在每个结点中添加两个标志 ltag 和 rtag。

线索化规则 ：

若结点的左子树为空，则该结点的左孩子指针指向其前驱结点。
若结点的右子树为空，则该结点的右孩子指针指向其后继结点。

建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索，以中序二叉树为例：


线索二叉树充分利用了指针空间，同时又便于寻找结点的前驱结点和后继结点。线索二叉树适用于经常需要遍历寻找结点 前驱或者后继结点 的二叉树。

四、最优二叉树（又：哈夫曼树）

1、定义

给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树 (Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

2、构造哈夫曼树

假设有 n 个权值，则构造出的哈夫曼树有 n 个叶子结点。 n 个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
2) 在森林中选出两个带权路径长度最小的树合并，作为一棵新树的左、右子树；
3)从森林中删除选取的两棵树，并将新树加入森林；
4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

3、哈夫曼编码

哈夫曼编码是一种基于最小冗余编码的压缩算法。最小冗余编码是指，如果知道一组数据中符号出现的频率，就可以用一种特殊的方式来表示符号从而减少数据需要的存储空间。
例如，需传送的报文为“A A C B C A A D D B B A D D A A B B”，这里用到的字符集为“A，B，C，D”。现要求为这些字母设计编码。要区别 4 个字母，最简单的二进制编码方式是 等长编码 ，固定采用 2 位二进制，可分别用 00、01、10、11 对“A，B，C，D”进行编码发送。然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如 A、B、C 的使用频率远远高于 X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。
基本步骤：
1）统计各个字符出现的次数
2）以次数作为权值构建哈夫曼树。
3）左子树路径标 0，右子树路径标 1（或者相反）
4）则从根到叶结点的路径标记即为该结点的编码

原始字符串：A A C B C A A D D B B A D D A A B B
哈夫曼编码：0 0 111 10 111 0 0 110 110 10 10 0 110 110 0 0 10 10，编码长度为 35
等长编码：00 00 10 01 10 00 00 11 11 01 01 00 11 11 00 00 01 01，编码长度为 36
可以看出使用霍夫曼编码可以缩短数据编码长度，达到数据压缩的效果。当字符数目较少时不能体现霍夫曼编码带来的压缩效果，但是当字符数目较多时，霍夫曼编码的压缩效率将显著提高。

五、二叉查找树（又：二叉搜索树，二叉排序树，有序二叉树）

1、定义

是一棵空树，或者是具有下列性质的二叉树：

1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
3）它的左、右子树也分别为二叉查找树

2、查找算法

与插入算法类似，在二叉查找树 b 中查找 x 的过程为：

1）若b是空树，则搜索失败
2）若x等于b的根结点的数据域之值，则查找成功
3）若x小于b的根结点的数据域之值，则搜索左子树；否则：查找右子树

3、插入算法（对空树进行不断插入数据即为：创建二叉查找树）

向一个二叉查找树 b 中插入一个结点 s 的算法是一个递归算法，过程为：

1）若b是空树，则将s所指结点作为根结点插入并返回
2）若s->data等于b的根结点的数据域之值，不插入并返回
3）若s->data小于b的根结点的数据域之值，则把s所指结点插入到左子树中，否则：把s所指结点插入到右子树中。

4、删除算法

在二叉查找树删去一个结点 p（假设已经找到要删除结点的位置）删除过程为：

1）若结点p的左右子树都为空，直接删除此子结点即可
2）若结点p只有左子树PL或右子树PR，此时只要令PL或PR直接成为其父结点的左子树或右子树即可
3）若结点p的左子树和右子树均不空，可以有两种做法：
其一是令p的左子树代替父节点f，p的右子树为新f的最右结点的右子树（或者相反）；
其二是令p的直接前驱（或直接后继）替代p，然后再从二叉排序树中删去它的直接前驱（或直接后继）

六、平衡二叉树（又：AVL 树）

1、定义

是一棵空树或左右两个子树的高度差（记为平衡因子）的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

2、左旋与右旋

调整平衡二叉树要用到的基本算法，左旋升高左子树，右旋和左旋互逆 ，左旋方法：根结点替换 左结点的右结点 ， 原左结点的右结点 成为原根结点的右孩子（截右左替补左右），右旋同理

3、失衡调整

平衡二叉树也是一棵二叉搜索树，所以它的增加删除结点也是建立在二叉搜索树之上的，只是，我们需要在不平衡的时候进行调整。无论是插入还是删除结点，总是最多存在一个失去平衡的最小子树。首先要找失去平衡的最小子树根结点的指针，然后再调整这个子树中有关结点之间的链接关系, 使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后, 原有其他所有不平衡子树无需调整, 整个二叉排序树就又成为一棵平衡二叉树。

七、红黑树

1、定义

红黑树 是每个结点都带有颜色属性的二叉查找树 ，颜色为红色或黑色，同时还要满足如下的额外要求:

1）结点是红色或黑色
2）根结点是黑色
3）每个叶子结点都带有两个空的黑色节点（称之为 NIL 节点，它又被称为黑哨兵）
4）每个红色节点的两个子节点都是黑色
5）从任一节点到它所能到达得叶子节点的所有简单路径都包含相同数目的黑色节点

红黑树的 5 条特性确保了从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，使得整棵树大致上是平衡的。树上的增删改查操作的最坏情况时间都与树的高度成正比，所以红黑树在最坏情况下也是高效的。在红黑树中一般用黑的 NIL 节点表示叶节点，不包含值，只是标志该分支结束，有时候绘图中会直接省略。

2、和 2 -3- 4 树的等价关系

如果一棵树满足红黑树，把红色节点收缩到其父节点，就变成了 2 -3- 4 树，所有红色节点都与其父节点构成 3 或 4 节点，其它节点为 2 节点。一颗红黑树对应唯一形态的 2 -3- 4 树，但是一颗 2 -3- 4 树可以对应多种形态的红黑树（主要是 3 节点可以对应两种不同的红黑树形态：左树和右树）。

3、调整操作

红黑树的插入删除方式与二叉查找树是一样的，只不过插入删除后可能需要做 调整 ，以满足红黑树的 5 条特性。新插入的结点总是 设为红色 ，如果 插入的父结点为黑色，就不需要调整 ，因为没有任何性质被改变，所以只有在父结点为红色结点时需要做调整，这时，以 插入结点的祖父节点为根的子树不平衡 ，需要调整；删除时如果是 叶子节点就直接删除 ，如果是非叶子节点，就会用中序遍历的后继（或前驱）节点来顶替要删除的节点。删除修复操作在遇到被删除的节点是红色节点或者到达 root 节点时，调整操作完毕。
调整操作为：若左子树的红色更多，右旋，反之左旋，同时改变这棵子树每个结点的颜色（化多补少，交换颜色）。

八、B 树（或 B - 树、B_树）

1、定义

一棵 m 阶 B 树是一棵 m 路查找树。它或者是空树，或者是满足下列性质的树：
1、每个结点最多有 m - 1 个关键字
2、根结点最少可以只有 1 个关键字
3、非根结点至少有 m / 2 个关键字
4、结点中的关键字按照从小到大排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它
4、所有的叶子结点都位于同一层。

九、堆

1、定义

堆通常是一个可以被看做一棵树的数组对象，需满足下列性质：

1）堆中某个节点的值总是不大于或不小于其父节点的值；
2）堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆, 由于堆是完全二叉树，故直接 使用数组存储。