常见术语
根节点：位于二叉树顶层的节点，没有父节点叶节点：没有子节点的节点（度为0的节点），其两个指针均指向None- 森林：由m(m>0)棵互不相交的树的集合
- 无序树：树中任意节点的子节点之间没有顺序关系
- 有序树：树中任意节点的子节点之间有顺序关系
- 二叉树：每个节点最多含有2个子树的树
边：连接两个节点的线段，即节点引用(指针)- 节点所在的
层:从顶到底递增，根节点所在的层为1 - 节点的
度:节点的子节点的数量。在二叉树中，度的取值范围是0、1、2 - 树的
度: 一棵树中，最大的节点的度称为树的度 - 二叉树的
高度:从根节点到最远叶节点所经过的边的数量 - 节点的
深度:从根节点到该节点所经过的边的数量 - 树的
深度:从根节点到树中最深叶子节点的最长路径上的节点数(只有根节点的树深度为1) - 节点的
高度:从距离该节点最远的叶节点到该节点所经过的边的数量
WARNING
上面这个高度和深度，具体是以边来计算还是以节点来计算，似乎不太一致。 但都是从1开始计算的
高度的计算是从山脚开始往上量的深度的计算是从山顶开始往下量的
演示图
Preview
二叉树类型
- 完美二叉树(满二叉树)：除了叶子节点，其他节点度都为2
- 完全二叉树：只有叶子节点没填满，且叶子节点都靠最左
- 完满二叉树：除了叶子节点，其他节点都有2个节点（没有度为1的节点）
- 平衡二叉树：任意节点左子树和右子树高度差绝对值不超过1
- 二叉搜索树：任意节点满足左子树中所有节点的值<父节点的值<右子树中所有节点的值
- AVL树（平衡二叉搜索树）：即是平衡二叉树又是二叉搜索树
- 红黑树
- B树(不是二叉树)
- B+树(不是二叉树)
二叉树的性质
Preview
数组表示下的二叉树
树的遍历
广度优先（层序遍历）
借助“队列”实现
深度优先
基于“递归”实现
- 前序遍历：中左右
- 中序遍历：左中右
- 后续遍历：左右中