数据结构[二叉树]

二叉树

满二叉树: 所有非叶子都有左右节点、所有叶子节点都在同一级
完全二叉树:满二叉树的特例,路径需跟满二叉树一致、但不要求都有左右叶子(即最后一层不满)

遍历

  • 深度优先遍历

    仅有前序和后序遍历,不能确定一个二叉树,必须有中序遍历的结果

    L、D、R分别表示遍历左子树、访问根结点和遍历右子树

    • 先序遍历:DLR
    • 中序遍历:LDR
    • 后序遍历:LRD
  • 广度优先遍历
    • 层序遍历:从根节点到叶子节点逐层遍历到叶子节点

性质

  • 二叉数
    • 性质1:在二叉树中第 i 层的结点数最多为 $2^{i-1}$ (i≥1)
    • 性质2:高度为 k 的二叉树其结点总数最多为 $2^k-1$ (k≥1)
    • 性质3:叶子的个数为 $n_0$,度为 2 的结点数为 $n_2$,则:$n_0 = n_2 + 1$
      • 节点数 = $n_0$ + $n_1$ + $n_2$
      • 节点数 - 1 = 边
      • $n_0$ + $n_1$ + $n_2$ - 1 = 0 * $n_0$ + 1 * $n_1$ + 2 * $n_2$
      • $n_0$ - 1 = $n_2$
      • $n_0$ = $n_2$ + 1
  • 满二叉树
    • 性质4:第 i 层上的节点数为 $2^{i-1}$
  • 完全二叉树
    • 性质5:对于具有 n 个结点的完全二叉树的高度为 $log_n^2$ + 1