树与二叉树

  1. 节点数 n = 所有节点度（degree） + 1

  2. 二叉树中：n = n0 + n1 + n2

  3. n2 = n0 + 1

  4. 树的路径长度：树根到每个节点的路径长度的总和

  5. 中序遍历 + 前序/后序/层序 ——》 构建一颗树

  6. n 个节点二叉树的空指针域个数：n + 1

  7. 前序遍历结果与中序遍历结果相同：非叶子节点只有右子树

    前序遍历结果与后序遍历结果相反：高度等于节点数（所有节点度为 1）

  8. 树的先根遍历与二叉树（森林）的先序遍历结果相同

    树的后根遍历与二叉树（森林）的中序遍历结果相同

  9. 平衡二叉树调整不平衡

    • LL：右旋
    • RR：左旋
    • LR：左旋、右旋
    • RL：右旋、左旋

  10. 高为 h 的平衡二叉树最少有几个节点：
    $$
    h_n = h_(n-1) + h_(n-2) + 1
    $$