二叉树

BinaryTree.cpp

性质

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

存储结构

二叉树数据结构

typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

顺序存储

二叉树顺序存储图片

链式存储

二叉树链式存储图片

遍历方式

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

分类

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