前言

线性结构的数据简单明了，关系清晰，但是我们实际生活中很多东西的关系是错综复杂的，没法用线性结构去体现，如：家族树，组织架构，用户角色等等。树结构可以很好地体现这些数据的关系。其中，二叉树又是树结构里面相对简单的，所以这里先从二叉树开始介绍。

什么是树

树(Tree)是 n (n ≥ 0)个有限数据元素的集合。当 n = 0 时，称这棵树为空树。
在一颗非空树中：

1. 有一个特殊的数据元素称为树的根结点，该结点没有前驱节点
2. 若 n ≥ 1，除根结点外的其余数据元素被分成 m（m > 0）个互不相交的集合，其中每一个集合本身又是一棵树，这些树又称为这个根结点的子树
3. 除了根结点外，其余节点有且只有一个前驱结点
4. 结点可以有零个或者多个后继结点
5. 结点的度是指该结点所拥有的子树的个数
6. 叶结点是指度为0的结点
7. 分支结点，除了叶节点就是分支结点
8. 结点间的关系，左孩子（左结点），右孩子（右节点），双亲（父结点），兄弟
   A 是 B 和 C 的双亲，B 和 C 是兄弟，B 是 A 的左孩子，C 是 A 的右孩子
9. 结点的层数，根结点所在的层数是1，其余结点的层数是它的双亲所在的层数加一
10. 树的深度是指这棵树的最大层次

树

二叉树

二叉树也是树，所以也要符合树的定义，拥有树的特性。

二叉树的特性：
1. 任意一个结点最多只能有两个后继结点（或者说不存在分支度超过2的结点）
2. 二叉树是有序树，左子树和右子树不能随意颠倒

上面只是介绍了普通的二叉树的特性，接下来要介绍一些特殊的二叉树：完全二叉树、满二叉树。

完全二叉树
如下图，添加结点总是从左到右，只有左结点挂满后，才会添加到右结点。

完全二叉树（图来自维基百科）

满二叉树
所有分支结点的度均为2

满二叉树（图来自维基百科）

二叉树的存储

无非是两种：顺序存储、链表存储

顺序存储

可以简单理解成用数组来实现。

完全二叉树（图来自维基百科）

如上图，用数组存储如下

完全二叉树的顺序存储示意图

这种存储方式的优点：读取快。
缺点：
1. 添加，删除，修改结点效率不高
2. 当要存储的不是完全二叉树时，甚至是退化称链表的树时，十分浪费存储空间

链表存储

可以简单理解成用链表来实现。
每个结点必需有

二叉链表存储结构

这种结构从上往下走是可以的，但是如果需要回溯时就很不方便了，所以可以增加一个属性存储双亲地址，如下图

三叉链表存储结构