树是由n(n>=0)个有限节点组成一个具有层次关系的集合。常见的树有平衡二叉树、二叉查找树、平衡二叉查找树（AVL树、黄黑树）、完全二叉树、满二叉树等。
常见概念
节点高度，节点到叶子节点的最厂路径
节点深度，根节点到该节点的边的个数
节点层次，深度+1
树的高度，根节点的高度
树的存储方式
链式存储
数组存储(x位于i，则i * 2=左子树，i * 2+1=右子树)
满二叉树
叶子节点在最后一层
叶子节点外，所有节点都有左右子树
完全二叉树
叶子节点在最后2层
最后一层叶子靠左
其他层节点数最大
完全二叉树性质(根节点为0，用数组保存完全二叉树)
下标i的左子节点下标：2 * i + 1
下表i的右子节点下标：左下标+1
最后一个非叶子节点下标：n/2-1
二叉查找树
对于任意节点，左子树的每个节点小于该节点
对于任意节点，右子树的每个节点大于该节点
平衡二叉树
- 任意节点左右子树高度相差不能大于1
平衡二叉查找树
平衡二叉树的特征
二叉查找树的特征
堆
完全二叉树
每个节点大于等于（或小于等于）子树中每个节点的值
堆的操作
堆化：插入
删除堆顶元素
堆排序
建堆，可以从上往下堆化，或从下往上堆化
排序，取堆顶，与末尾交换然后堆化，继续取堆顶，与末尾交换，再堆化
堆的应用
优先级队列
TOP K 问题
求中位数