当前没有测试数据。

• 树：由结点和边组成的无环的非线性结构

  • 

• 应用场景：族谱、文件夹

• 基本概念：

  ---

  • 节点：

    • 根节点：无前驱的结点
    • 叶结点：无后继的结点
    • 父/子结点：结点间的前驱/后继关系
    • 兄弟结点：结点同属于一个父结点

  ---

  • 度：

    • 结点的度 = 其子结点的数量
    • 树的度 = 最大的结点的度

  ---

  • 层次：

    • 规定根结点所在层次为第1层，以此类推
    • 树的高（深）度 = 节点的最大层次

• 二叉树（每个节点最多只有2个子节点）

  ---

  • 5种基本形态：
    • 
    • 1、空二叉树
    • 2、只有根结点的二叉树
    • 3、只有左子树的二叉树
    • 4、只有右子树的二叉树
    • 5、左右子树都存在的二叉树

  ---

  • 性质：

    • 1、第 $i$ 层上的结点数目最多为 $2^{i - 1}$

    • 2、深度为$k$的二叉树最多有个结点为$2^{k} - 1$

    • 3、设叶结点数为 $n_0$，度为2的结点数为 $n_2$，则 $n_0 = n_2 + 1$

      • 设树的总结点数为 $n$，度为1的结点数为 $n_1$，上述公式推导过程如下：
      • $n = n_0 + n_1 + n_2$
      • $n = 1 * n_1 + 2 * n_2 + 1$（度为1的节点连着1个节点，度为2的节点连着2个节点，再加上根节点）
      • 等式简化得 $n_0 = n_2 + 1$

• 满二叉树：除叶结点外，每个结点的度都为2的二叉树（如下图左右都是满二叉树）

  • 
  • 性质：深度为$k$ 的满二叉树一共有==$2^k - 1$==个结点

• 完全二叉树：树中每个结点的编号与满二叉树一 一对应的二叉树

  • 

  ---

• 性质：

  • 1、结点数为 $N$ 的完成二叉树的深度 $k = floor(log_2 N) + 1$
  • 2、编号为 $i$ 的结点，其父结点编号为 $i / 2$
  • 3、节点数为 $n$ 时，其叶子节点数为 $floor[(n + 1) / 2]$

• 二叉树的遍历：按【一定规律和次序】访问树中每一个结点，分为先/中/后（根）序遍历（递归进行）和宽度优先遍历

  • 

  ---

  • 先序遍历：1 2 4 5 3 6 7

    • 先访问根节点1

    • 再访问左子树

      • 此时需要对左子树(2, 4, 5)继续进行先序遍历
        • 先访问根节点2
        • 再访问左节点4
        • 最后访问右节点5
        • 左子树(2, 4, 5)遍历结束

    • 最后访问右子树

      • 此时需要对右子树(3, 6, 7)继续进行先序遍历
        • 先访问根节点3
        • 再访问左节点6
        • 最后访问右节点7
        • 右子树(3, 6, 7)遍历结束

    • 树(1, 2, 3, 4, 5, 6, 7)遍历结束

    • 应用场景：复制树、打印树

  ---

  • 中序遍历：4 2 5 1 6 3 7

    • 先访问左子树

      • 此时需要对左子树(2, 4, 5)继续进行中序遍历
        • 先访问左节点4
        • 再访问根节点2
        • 最后访问右节点5
        • 左子树(2, 4, 5)遍历结束

    • 再访问根节点1

    • 最后访问右子树

      • 此时需要对右子树(3, 6, 7)继续进行中序遍历
        • 先访问左节点6
        • 再访问根节点3
        • 最后访问右节点7
        • 右子树(3, 6, 7)遍历结束

    • 树(1, 2, 3, 4, 5, 6, 7)遍历结束

    • 应用场景：中缀表达表达

      • 
      • 示例：(a - b) + (c + d) * e

  ---

  • 后序遍历：4 5 2 6 7 3 1

    • 先访问左子树

      • 此时需要对左子树(2, 4, 5)继续进行后序遍历
        • 先访问左节点4
        • 再访问右节点5
        • 最后访问根节点2
        • 左子树(2, 4, 5)遍历结束

    • 再访问右子树

      • 此时需要对右子树(3, 6, 7)继续进行后序遍历
        • 先访问左节点6
        • 再访问右节点7
        • 最后访问根节点3
        • 右子树(3, 6, 7)遍历结束

    • 最后访问根节点1

    • 树(1, 2, 3, 4, 5, 6, 7)遍历结束

    • 应用场景：销毁文件夹（先销毁子文件，再销毁根文件夹）

  ---

  • 宽度优先遍历（逐层、从左到右）：1 2 3 4 5 6 7