线索二叉树
利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为”线索”）。因此，提出了一种方法，利用原来的空链域存放指针，指向树中其他结点。这种指针称为线索。
记ptr指向二叉链表中的一个结点，以下是建立线索的规则：
（1）如果ptr->lchild为空，则存放指向中序遍历序列中该结点的前驱结点。这个结点称为ptr的中序前驱；
（2）如果ptr->rchild为空，则存放指向中序遍历序列中该结点的后继结点。这个结点称为ptr的中序后继；
显然，在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继，需要一个区分标志的。因此，我们在每个结点再增设两个标志域ltag和rtag，注意ltag和rtag只是区分0或1数字的布尔型变量，其占用内存空间要小于像lchild和rchild的指针变量。结点结构如下所示。
其中：
（1）ltag为0时指向该结点的左孩子，为1时指向该结点的前驱；
（2）rtag为0时指向该结点的右孩子，为1时指向该结点的后继；
十字链表
十字链表是有向图的一种链式存储结构。 十字链表是为了便于求得图中顶点的度（出度和入度）而提出来的。它是综合邻接表和逆邻接表形式的一种链式存储结构。 在十字链表存储结构中，有向图中的顶点的结构如下所示：
其中data表示顶点的具体数据信息，而firstIn则表示指向以该顶点为弧头的第一个弧节点。而firstOut则表示指向以该顶点为弧尾的第一个弧节点。为了表示有向图中所有的顶点，采用一个顶点数组存储每一个结点
另外，在十字链表存储结构中，有向图中的每一条弧都有一个弧结点与之对应，具体的弧结点结构如下所示：
其中的tailVex表示该弧的弧尾顶点在顶点数组xList中的位置，headVex表示该弧的弧头顶点在顶点数组中的位置。hLink则表示指向弧头相同的下一条弧，tLink则表示指向弧尾相同的下一条弧。
从十字链表的数据结构来看，每一个顶点对应两个链表：以该顶点为弧尾的弧结点所组成的链表以及以该顶点为弧头的弧结点所组成的链表。
如下图所示的一个有向图：
其对应的顶点以及弧结点如下所示。拿结点A说明，该结点对应两个链表（绿色和黄色标记的）。绿色链表表示以结点Ａ为弧头的弧组成的链表。黄色链表表示以结点Ａ为弧尾的弧组成的链表。
哈夫曼编码
1）树的路径长度 树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短. （2）树的带权路径长度(Weighted Path Length of Tree，简记为WPL) 结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。 树的带权路径长度(Weighted Path Length of Tree)：定义为树中所有叶结点的带权路径长度之和 $ WPL = \sum_{i = 1}^n w_il_i $ 其中： n表示叶子结点的数目 wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。 树的带权路径长度亦称为树的代价。
我们称判定过程最优的二叉树为哈夫曼树，又称最优二叉树
[参考这个博客](https://blog.csdn.net/shuangde800/article/details/7341289)
B-树
B树，也就是英文中的B-Tree，一个 m 阶的B树满足以下条件：
(1)树中每个结点至多有m棵子树
(2)若根节点不是叶子结点,则至少有两棵子树
(3)除根之外的所有非终端结点至少有ceil(m/2)棵子树
(4)至少有 ceil(m/2) - 1个关键字,最多有m - 1个关键字.
(5)所有叶子结点在同一层
如一棵四阶B-树，其深度为4.
B-树的深度 $ log_{ceil(m/2)} (\frac{N + 1}{2}) + 1$ N为关键字个数
B-树主要应用在文件系统
为了将大型数据库文件存储在硬盘上以减少访问硬盘次数为目的 在此提出了一种平衡多路查找树——B-树结构 由其性能分析可知它的检索效率是相当高的
B+树
B+树是B树的一种变形。
1.有n棵子树的节点中含有n个关键字
2.所有的叶子结点中包含了全部的关键字信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字大小自小而大顺序链接。
3.所有的非终端结点可以看成是索引的部分,结点中仅含有其子树(根节点)中的最大(或最小)关键字
B+树既可以进行顺序查找也可以进行随机查找,而B-树(B树)只能进行随机查找,这是因为B+树有两个指针,一个指向根节点,一个指向最小的叶子结点
平均查找长度
平均查找长度:为确定记录在查找表中的位置,需和给定值进行比较的关键字个数的期望值成为查找算法在查找成功时的平均查找长度。
