二叉树

概念

- 二叉树，最多有两个度（分支）的树
- 分为   __满二叉树__ （全满）  __斜树__ （只有一边）
- [[自平衡二叉树]]
- [[完全二叉树]]

• 性质

  • 一层最多有 $2^{k-1}-1$ 个结点
  • 结点最多有 $2^k-1$ 个
  • 度为2 与 度为0（叶子结点）满足 $n_2+1=n_0$
  • n个节点深度为 $lo{g}_{2}n-1$
  • 编号为 i 左子结点为 $2i$ 右子节点为 $2i+1$

• >结构实现

  • 数组实现
    • 2i 为左，2i + 1为右， 没有设为空，实际上就是从上到下从左到右的依次编号存储