二叉树

• 使用数组存储完全二叉树，一层一层的从上到下从左到右存储到数组中。则节点i的左孩子为 2i，右孩子为 2i + 1;
• 二叉树的层次遍历。使用队列，从根节点开始入队，然后出队，每出队一个节点，就把该节点的左孩子和右孩子入队。出队的顺序就是遍历的结果。

平衡二叉树

• 左右子树深度之差不超过 1。

二叉查找树

• 左子树的数字小于根节点，右子树的数字大于根节点，子树也符合这个规律。

满二叉树

• 除了叶子节点所有节点都有两个孩子。

完全二叉树

• 结点序号为 i 的结点在二叉树中的位置与满二叉树中结点 i 的位置相同。

红黑树

• 根和叶子都是黑色的。
• 每个红色结点都有两个黑色子结点。
• 任意结点到其每个叶子节点的所有路径包含相同数目的黑色节点。

哈夫曼树

• 带权路径最小的二叉树称为哈夫曼树，也称为最优二叉树。
• 只有叶子节点有权值。
• 构建哈夫曼树

1. 给定 n 个带权节点。
2. 选两个权值最小节点的构成一个二叉树。取根节点的权值为两个子节点的和。
3. 从n个节点中去掉这两个最小的。加入新构成二叉树的根节点。
4. 然后继续选两个最小的以此类推，就可以构成一个哈夫曼树。

B- 树

• 结点包含的最多孩子数是 b- 树的阶 m。
• 根结点至少有 2 个孩子。
• 中间结点包含 k-1个元素和 k 个孩子， 其中 m/2 <= k <= m。
• 每一个叶子结点都包含 k-1 个元素。其中 m/2 <= k <= m。
• 所有的叶子结点都位于同一层。
• 结点中 k-1 个孩子正好是 k 个结点的值域分布。

B+ 树

• 有 k 个子树的中间结点包含 k 个元素，每个元素不包含数据只包含索引。
• 所有叶子结点包含了全部元素的信息，以及指向元素的指针，而且叶子结点本身依照关键字的大小升序排序。
• 所有中间结点元素都同时存在于子节点中，在子节点中是最大值或者最小值。
• 叶子结点中含有指针指向右侧下一个叶子结点。

优势：

1. 单一结点存储更多元素，使查询的IO次数更少。
2. 所有查询都要找到叶子结点，查询性能稳定。
3. 所有叶子结点形成有序链表，便于范围查询。

堆

• 堆就是用数组实现的二叉树

图

• 图中的结点称为顶点。
• 无向图中连接顶点的路径称为边。
• 有向图中连接顶点的路径称为弧，指向顶点的一端称为弧头，反之称为弧尾。
• 有向图中指向某个顶点的弧的数量称为入度，远离顶点的弧的数量称为出度。
• 弧和边带有权重的数字的图称为带权图，分别称为有向有权图，无向有权图。
• 带权图也称为网，可以分为有向网和无向网。

图的分类

• 无向图中各个顶点都与其他顶点有关系的图称为 完全图。
• 有向图满足上述条件的称为 有向完全图。
• 无向图中任意两个顶点是连通着的，则称此无向图为连通图。
• 无向图不是连通图，但是子图符合连通图属性，则称该子图为连通分量，这里的子图为最大连通子图，也称为极大连通子图。
• 有向图中任意两个顶点都连通，称此有向图为强连通图。
• 有向图不是强连通图，但是存在子图满足强连通图性质，则称此最大连通子图为强连通分量。
• 即如果图中具有很少的边（或弧），此图就称为稀疏图，反之，则称此图为稠密图。稀疏和稠密的判断条件是：e<nlogn，其中 e 表示图中边（或弧）的数量，n 表示图中顶点的数量。如果式子成立，则为稀疏图；反之为稠密图
• 无向图中任意两个顶点之间含有不止一条通路，这个图称为重连通图，重连通图中删除某个顶点以及该顶点相关联的边后，依然是一个连通图。

连通图的生成树。

• 图的生成树就像一个普通的树，满足两个条件：

1. 包含图的所有顶点。
2. 任意两个顶点只有一条通路。

非连通图的生成森林。

• 非连通图包含多个连通分量，多个连通分量对应的生成树构成生成森林。