二叉树

BinaryTree.cpp

性质

  1. 非空二叉树第 i 层最多 2(i-1) 个结点 (i >= 1)
  2. 深度为 k 的二叉树最多 2k - 1 个结点 (k >= 1)
  3. 度为 0 的结点数为 n0,度为 2 的结点数为 n2,则 n0 = n2 + 1
  4. 有 n 个结点的完全二叉树深度 k = ⌊ log2(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

存储结构

二叉树数据结构

  1. typedef struct BiTNode
  2. {
  3. TElemType data;
  4. struct BiTNode *lchild, *rchild;
  5. }BiTNode, *BiTree;
顺序存储

二叉树顺序存储图片

二叉树 - 图1

链式存储

二叉树链式存储图片

二叉树 - 图2

遍历方式

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

分类

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