性质

1. 深度为 k 的二叉树最多 2^k - 1 个结点 （k >= 1）
2. 度为 0 的结点数为 n₀，度为 2 的结点数为 n₂，则 n₀ = n₂ + 1
3. 有 n 个结点的完全二叉树深度 k = ⌊ log₂(n) ⌋ + 1
4. 对于含 n 个结点的完全二叉树中编号为 i （1 <= i <= n） 的结点
   1. 若 i = 1，为根，否则双亲为 ⌊ i / 2 ⌋
   2. 若 2i > n，则 i 结点没有左孩子，否则孩子编号为 2i

存储结构

二叉树数据结构

顺序存储

链式存储

遍历方式

• 先序遍历
• 中序遍历
• 后续遍历
• 层次遍历

分类

• 满二叉树
• 完全二叉树（堆）
  • 小顶堆：根 <= 左 && 根 <= 右
• 二叉查找树（二叉排序树）：左 < 根 < 右
• 平衡二叉树（AVL树）：| 左子树树高 - 右子树树高 | <= 1
• 最小失衡树：平衡二叉树插入新结点导致失衡的子树：调整：
  • LL型：根的左孩子右旋
  • RR型：根的右孩子左旋
  • RL型：右孩子的左子树，先右旋，再左旋