树
什么是树
树由 n(n>=1) 个有限结点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
与线性表表示的一一对应的线性关系不同，树表示的是更为复杂的数据元素之间的非线性关系。如果我们要判断一个结构是否为树，可以从以下几方面入手：
- 有且只有一个根节点；
- 有若干个互不相交的子树；
- 根节点（root）没有父节点；
- 一个节点有且只有一个父节点（根节点除外）；
- 节点可以有多个子节点；
树概念
| Terminology（术语） | Explaining（解释） |
|---|---|
| Root（根） | 树中的顶级节点。 |
| Child（子节点） | Root 的每一个子树的根叫做 Root 的子节点（Child）。 |
| Parent（父节点） | Root 是每一个子树的根的父节点（Parent）。 |
| Siblings（兄弟节点） | 一些具有相同父节点的节点称为兄弟节点。 |
| Descendant（后代） | 对任意节点 x，从根节点到节点 x 的所有节点都是 x 的祖先。 |
| Ancestor（祖先） | 对任意节点 x，从节点 x 到叶子节点的所有节点都是 x 的后代。 |
| Leaf（叶子节点） | 没有子节点的节点。 |
| Degree（度） | 子节点的个数（最大子节点的度称为树的度）。 |
| Edge（边） | 父节点和子节点相连的一个路径。 |
| Depth（深度） | 节点的深度定义为：当前节点和根之间的边数。 |
| Height of node（节点的高） | 节点的高度是该节点与后代节点之间最长路径上的边数，所以叶子节点高度为0。 |
| Height of tree（树的高） | 树的高度是其根节点的高度。 |
| Forest （森林） | 多颗互不相交的树组成的集合。 |
树的分类
无序树
树的任意节点的子节点没有顺序关系。
有序树
树的任意节点的子节点有顺序关系。
二叉树
树的任意节点至多包含两棵子树。
满二叉树
叶子节点都在同一层并且除叶子节点外的所有节点都有两个子节点。
完全二叉树
对于一颗二叉树，假设其深度为 d（d>1）。除第 d 层外的所有节点构成满二叉树，且第 d 层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树。
平衡二叉树（AVL）
它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树。
二叉查找树（二叉搜索树、BST）
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
霍夫曼树
带权路径最短的二叉树称为哈夫曼树或最优二叉树。
红黑树
红黑树是一颗特殊的二叉查找树，除了二叉查找树的要求外，它还具有以下特性：
- 每个节点或者是黑色，或者是红色。
- 根节点是黑色。
- 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
B-tree（B-树或者B树）
一颗 m 阶 B 树的特性：
- 根结点至少有两个子女（如果 B 树只有一个根节点，这个根节点的 key 的数量可以为 [1~m-1]）。
- 每个非根节点所包含的关键字个数 j 满足：⌈m/2⌉ - 1 <= j <= m - 1，节点的值按非降序方式存放，即从左到右依次增加。
- 除根结点以及叶子节点以外的所有结点的度数正好是关键字总数加 1，故内部节点的子树个数 k 满足：⌈m/2⌉ <= k <= m。
- 所有的叶子结点都位于同一层。
B+树
m 阶 B+ 树是 m 阶 B-tree 的变体，它的定义大致跟 B-tree 一致，不过有以下几点不同：
- 有 n 棵子树的结点中含有 n 个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点，其中 ⌈m/2⌉ <= n <= m。
- 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
- 所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。
- 通常在 B+ 树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。
森林
n 个互不相交的树的集合。
图解树
一个普通的树的具体结构如下：
我们看到，这是一颗普通的树，其每个结点下面的子节点的个数是任意的，我们现在再来看下二叉树的结构如下图：
我们看到，每个结点下面最多只有两个子节点。
二叉树结构
二叉树的结构定义如下：
struct BTreeNode
{
int data; //队列每个结点的数据
struct BTreeNode *pLChild; //左孩子
struct BTreeNode *pRChild; //右孩子
};
我们定义了一个二叉树的结构 BTreeNode，其中 data 是二叉树的数据，pLChild 是该结点的左孩子，pRChild 是该结点的右孩子。
