一、树的概念

1. 什么是树

树是一种非线性数据结构，由若干个节点组成，用来表示具有层次关系的数据。

例如：

        A
      / | \
     B  C  D
       / \
      E   F

这是一棵树：

  • A 是最上层节点
  • B、C、D 是 A 的子节点
  • E、F 是 C 的子节点

树通常可以递归地定义：

树是由一个根节点，以及若干棵互不相交的子树组成的。

二、树中的常用术语

不需要特意去背，看多了总能记住的。

但可惜我是老年痴呆？

仍以这棵树为例：

        A
      / | \
     B  C  D
       / \
      E   F

1. 节点

树中的每一个元素都叫节点。

例如 A、B、C、D、E、F 都是节点。

2. 根节点

树中最顶层的节点称为根节点。

上图中，A 是根节点。

一棵非空树只有一个根节点。

3. 父节点与子节点

如果一个节点下面直接连接了其他节点，那么：

  • 上面的节点叫父节点
  • 下面的节点叫子节点

例如：

  • A 是 C 的父节点
  • C 是 A 的子节点
  • C 是 E 和 F 的父节点

4. 兄弟节点

具有同一个父节点的节点互称兄弟节点。

例如：

  • B、C、D 是兄弟节点
  • E、F 是兄弟节点

5. 叶子节点

没有子节点的节点叫叶子节点，也叫终端节点。

上图中的叶子节点是：

B、D、E、F

6. 非叶子节点

至少有一个子节点的节点叫非叶子节点，也叫内部节点、非终端节点或分支节点。

上图中：

A、C

是非叶子节点。

7. 节点的度

一个节点拥有的子节点数量，叫这个节点的度。

例如：

  • A 有 3 个子节点，所以 A 的度为 3
  • C 有 2 个子节点，所以 C 的度为 2
  • B 没有子节点，所以 B 的度为 0

叶子节点的度一定是 0。

8. 树的度

树中所有节点的度的最大值，称为树的度。

上图中：

  • A 的度是 3
  • C 的度是 2
  • 其他节点的度是 0

所以这棵树的度是 3。

和几叉树不同，几叉树只规定了上限。

9. 节点的层次

一般规定根节点位于第 1 层。

上图中：

  • A 位于第 1 层
  • B、C、D 位于第 2 层
  • E、F 位于第 3 层

有些教材把根节点规定为第 0 层。做题时应先确认题目的定义。

10. 树的高度或深度

树中节点所在的最大层数，通常称为树的高度或深度。

上图共有 3 层，所以树的高度为 3。

  • 节点深度：从根节点到该节点经过的边数，从上往下
  • 节点高度：从该节点到最远叶子节点经过的边数，从下往上

11. 路径

从一个节点到另一个节点经过的节点或边构成的序列，叫路径。

例如从 A 到 F 的路径是：

A → C → F

路径长度通常指经过的边数，所以 A 到 F 的路径长度是 2。

12. 子树

一个节点和它的所有后代节点构成一棵子树。

例如以 C 为根的子树是：

      C
     / \
    E   F

13. 祖先与后代

如果节点 X 位于从根节点到节点 Y 的路径上，那么：

  • X 是 Y 的祖先
  • Y 是 X 的后代

例如：

  • A 是 E 的祖先
  • C 也是 E 的祖先
  • E 是 A 和 C 的后代

三、树的常用性质

性质 1：节点数和边数的关系

一棵有 nn 个节点的非空树，有n-1条边。

例如，一棵树有 6 个节点，那么一定有 5 条边。

除根节点外，每个节点都恰好有一条边连接到自己的父节点。

性质 2：所有节点的度数之和

对于一棵有 nn 个节点的树：

n=所有节点的度数之和+1n=\text{所有节点的度数之和}+1

节点的度数之和即为边的数量

例如：

        A
      / | \
     B  C  D
       / \
      E   F

各节点的度为：

A：3
B：0
C：2
D：0
E：0
F：0

总和为：

3+0+2+0+0+0=53+0+2+0+0+0=5

节点数为 6，所以：

6−1=56-1=5

四、二叉树的概念

二叉树是一种特殊的树。

二叉树中，每个节点最多只有两个子节点。

这两个子节点分别称为：

  • 左子节点
  • 右子节点

例如：

        A
       / \
      B   C
     / \   \
    D   E   F

这是二叉树，因为每个节点最多有两个子节点。

五、二叉树需要特别注意的地方

1. 二叉树不等于“度为 2 的树”

二叉树允许一个节点：

  • 没有子节点
  • 只有左子节点
  • 只有右子节点
  • 同时有左右两个子节点

例如：

    A
     \
      B

这是二叉树。

因为每个节点最多只有两个子节点。

2. 二叉树的左右子树有顺序

下面两棵二叉树通常被认为是不同的：

二叉树分左右

第一棵：       第二棵：

    A              A
   /                \
  B                  B

虽然都只有 A 和 B 两个节点，但是 B 的位置不同：

  • 第一棵中 B 是左子节点
  • 第二棵中 B 是右子节点

因此二叉树是一种有序树。

六、几种常见的特殊二叉树

1. 满二叉树

如果一棵二叉树中：

  • 每一层的节点数都达到最大值
  • 除叶子节点外，每个节点都有两个子节点
  • 所有叶子节点都在同一层

那么它叫满二叉树，也没啥好纠结定义的，一眼丁真。

例如：

        A
       / \
      B   C
     / \ / \
    D  E F  G

就是一个高度为 3 的满二叉树

2. 完全二叉树

完全二叉树的定义是：

  • 除最后一层外，其他各层的节点数都达到最大值
  • 最后一层的节点从左向右连续排列
  • 从上往下，从左往右

例如：

        A
       / \
      B   C
     / \ /
    D  E F

这是完全二叉树。

因为最后一层的 D、E、F 从左向右连续排列。

下面这棵树不是完全二叉树：

        A
       / \
      B   C
       \ /
        E F

原因是 B 没有左子节点却有右子节点，最后一层出现了空缺后又出现节点。

满二叉树和完全二叉树的关系

满二叉树一定是完全二叉树。

完全二叉树不一定是满二叉树。

3. 二叉搜索树

二叉搜索树也叫二叉排序树，通常满足：

对于任意节点：

  • 左子树中的所有值都小于该节点
  • 右子树中的所有值都大于该节点
  • 左右子树也分别是二叉搜索树

例如：

        8
       / \
      4   12
     / \  / \
    2  6 10 14

对这棵树进行中序遍历，可以得到递增序列：

2，4，6，8，10，12，14

如果允许重复值，需要额外规定相等元素放左边还是右边。

这种树的插入判定好麻烦，让我想起了不好的经历。

七、二叉树的常用性质

以下公式通常规定根节点为第 1 层，树的高度为层数。

性质 1：第 ii 层的最大节点数

二叉树第 ii 层最多有：

2i−12^{i-1}

个节点。

例如：

  • 第 1 层最多 20=12^0=1 个节点
  • 第 2 层最多 21=22^1=2 个节点
  • 第 3 层最多 22=42^2=4 个节点
  • 第 4 层最多 23=82^3=8 个节点

性质 2：高度为 hh 的二叉树最大节点数

高度为 hh 的二叉树最多有：

2h−12^h-1

个节点。

只有满二叉树能达到这个最大值。

性质 3：高度为 hh 的二叉树最少节点数

普通二叉树高度为 hh 时，最少有：

hh

个节点。

因为可以退化成一条链：

A
 \
  B
   \
    C
     \
      D

高度为 4，节点数也是 4。

性质 4：具有 nn 个节点的二叉树最小高度

具有 nn 个节点的二叉树，最小高度为：

⌈log⁡2(n+1)⌉\lceil \log_2(n+1) \rceil

例如有 10 个节点：

log⁡2(10+1)=log⁡211≈3.46\log_2(10+1)=\log_2 11\approx 3.46

向上取整得到：

hmin⁡=4h_{\min}=4

因为高度为 3 时最多只能容纳：

23−1=72^3-1=7

个节点，高度为 4 时最多可以容纳 15 个节点。

性质 5：具有 nn 个节点的二叉树最大高度

具有 nn 个节点的普通二叉树，最大高度为：

nn

当二叉树退化成斜树时，高度达到最大。

八、二叉树中叶子节点的常用公式

设一棵非空二叉树中：

  • n0n_0：度为 0 的节点数，即叶子节点数
  • n1n_1：度为 1 的节点数
  • n2n_2：度为 2 的节点数

总节点数为：

n=n0+n1+n2n=n_0+n_1+n_2

二叉树中有一个非常重要的性质：

n0=n2+1\boxed{n_0=n_2+1}

也就是说：

叶子节点数等于度为 2 的节点数加 1。

同样可推导出：

n0+n2=2∗n2+1\boxed{n_0+n_2=2*n_2+1}

n0+n2n_0+n_2 必定是一个奇数。

九、完全二叉树的常用性质

完全二叉树特别适合使用数组存储。

假设按照从上到下、从左到右的顺序编号，并且编号从 1 开始：

            1
          /   \
         2     3
        / \   / \
       4   5 6   7

对于编号为 ii 的节点：

1. 父节点编号

当 i>1i>1 时，父节点编号为：

⌊i2⌋\left\lfloor \frac{i}{2}\right\rfloor

例如节点 6 的父节点：

⌊62⌋=3\left\lfloor \frac{6}{2}\right\rfloor=3

2. 左子节点编号

如果左子节点存在，其编号为：

2i2i

例如节点 3 的左子节点编号是：

2×3=62\times3=6

3. 右子节点编号

如果右子节点存在，其编号为：

2i+12i+1

例如节点 3 的右子节点编号是：

2×3+1=72\times3+1=7

4. 判断叶子节点

在具有 nn 个节点的完全二叉树中，编号大于：

⌊n2⌋\left\lfloor \frac{n}{2}\right\rfloor

的节点都是叶子节点。

因此叶子节点的编号范围为：

⌊n2⌋+1到n\left\lfloor \frac{n}{2}\right\rfloor+1 \quad\text{到}\quad n

让我想起了可恶的堆排序。

十、完全二叉树的高度

具有 nn 个节点的完全二叉树高度为：

⌈log⁡2(n+1)⌉\boxed{\lceil\log_2(n+1)\rceil}

十一、树和二叉树的区别

对比项 普通树 二叉树
子节点数量 可以有任意多个 最多两个
子节点顺序 通常不强调顺序 严格区分左右
空树 可以为空 可以为空
常见存储方式 孩子表示法、双亲表示法 链式存储、数组存储
常见遍历 先根、后根、层序 前序、中序、后序、层序

需要注意，普通树通常没有单独的“中序遍历”，因为一个节点可能有多个子树，无法自然地确定根节点应该放在哪两棵子树之间。

十二、最常用公式汇总

普通树

有 nn 个节点：

边数=n−1\text{边数}=n-1 所有节点的度数之和+1=n\text{所有节点的度数之和} + 1=n

普通二叉树

第 ii 层最多有：

2i−12^{i-1}

高度为 hh 时最多有：

2h−12^h-1

高度为 hh 时最少有：

hh

叶子节点与度为 2 的节点之间：

n0=n2+1\boxed{n_0=n_2+1}

满二叉树

高度为 hh，总节点数为：

2h−12^h-1

叶子节点数为：

2h−12^{h-1}

完全二叉树

有 nn 个节点，高度为：

⌈log⁡2(n+1)⌉\boxed{\lceil\log_2(n+1)\rceil}

节点从 1 开始编号：

父节点=⌊i2⌋\text{父节点}=\left\lfloor\frac{i}{2}\right\rfloor 左子节点=2i\text{左子节点}=2i 右子节点=2i+1\text{右子节点}=2i+1

半夜四点，困死我了，来点可爱的贵贵 ┐(´д`)┌ 可爱的贵贵