定义
在数据结构中，树的定义如下。
树（tree）是n（n≥0）个节点的有限集。当n=0时，称为空树。在任意一个非空树中，有如下特点。
- 有且仅有一个特定的称为根的节点。
- 当n>1时，其余节点可分为m（m>0）个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。
树的最大层级数，被称为树的高度或深度。
二叉树
二叉树（binary tree）是树的一种特殊形式。二叉，顾名思义，这种树的每个节点最多有2个孩子节点 。注意，这里是最多有2个，也可能只有1个，或者没有孩子节点。
满二叉树： 一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树。
完全二叉树： 对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。
物理存储结构
1.链式存储结构
每一个节点：
- 存储数据的 data 变量
- 指向左孩子的 left 指针
- 指向右孩子的 right指针
2.数组
- 按层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或右孩子空缺，则数组的对应位置也空出来。
- 假设一个父节点的下标是parent，那么它的左孩子节点下标就是2×parent + 1 ；右孩子节点下标就是2×parent + 2。
二叉查找树
限定条件：
- 如果左子树不为空，则左子树上所有节点的值均小于根节点的值
- 如果右子树不为空，则右子树上所有节点的值均大于根节点的值
- 左、右子树也都是二叉查找树
对一个节点分布相对均衡的二叉查找树来说，如果节点总数为n，那么搜索节点的时间复杂度就是 O(logn) ，和树的深度是一样的。
遍历
从节点之间位置关系的角度来看，二叉树的遍历分为4种。
- 前序遍历（根、左、右）
- 中序遍历（左、根、右）
- 后序遍历（左、右、根）
- 层序遍历（一层一层遍历）
从更宏观的角度来看，二叉树的遍历归结为两大类。
- 深度优先遍历（前序遍历、中序遍历、后序遍历）（递归、栈）。
- 广度优先遍历（层序遍历）（队列）
二叉堆
二叉堆本质上是一种完全二叉树，它分为两个类型：
- 最大堆
最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值。 - 最小堆
最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值。
二叉堆的根节点叫做堆顶。
对于二叉堆，有如下几种操作。
- 插入节点。（节点上浮）
- 删除节点。（删除节点后判断然后下浮）
- 构建二叉堆。
这几种操作都基于堆的自我调整。
二叉堆使用数组存储。
假设父节点的下标是parent，那么它的左孩子下标就是 2×parent+1 ；右孩子下标就是2×parent+2。
作用：用于实现优先队列和堆排序。
优先队列
最大（小）优先队列，无论入队顺序如何，都是当前最大（小）的元素优先出队。