第 07 讲

树与二叉树入门

树就像一份家谱:最上面一个根,下面一层层分叉。这一章只学五件事: 树和二叉树长什么样、二叉树怎么存、五条常用结论、四种遍历, 最后用并查集把结点分成组。

预计 60 分钟 前置:会写简单的递归函数 关键词:根 · 孩子 · 叶子 · 完全二叉树 · 五条性质 · 四种遍历 · 并查集

7.1 树是什么

7.1.1 用「家谱」理解树

树由结点和连接结点的边组成。它有一个最上面的结点,叫根; 除根以外,每个结点都只有一个双亲,但可以有多个孩子。 像下面这样:

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

7.1.2 两个最基本的事实

这两句话不用背证明,画一棵树数一数就能明白。

7.2 二叉树

7.2.1 二叉树是什么

二叉树是每个结点最多有两个孩子的树,而且这两个孩子分左孩子和右孩子, 不能随便交换。

它只有五种基本形态:

  1. 空树;
  2. 只有根;
  3. 只有左子树;
  4. 只有右子树;
  5. 左右子树都有。

特别注意:只有左孩子和只有右孩子是两种不同的二叉树,不能当成同一棵树。

7.2.2 满二叉树与完全二叉树

满二叉树:每一层都排满,没有空位。深度为 k 的满二叉树有 2k−1 个结点。

完全二叉树:除了最后一层,上面每一层都排满;最后一层的结点必须从左往右连续排列, 中间不能空一个再放一个。

满二叉树(深度 3)          完全二叉树(6 个结点)
        A                          A
       / \                        / \
      B   C                      B   C
     / \ / \                    / \ /
    D E F G                    D E F

判断完全二叉树时记住一句话:一个结点如果只有右孩子、没有左孩子,它一定不是完全二叉树。

7.2.3 二叉树怎么存

最直观的存法是二叉链表:每个结点存三样东西——自己的值、左孩子指针、右孩子指针。 没有孩子时,指针为空。

struct Node { char val; Node *left, *right; };

例如上面那棵树,A 的 left 指向 B,right 指向 C; D 的 left 和 right 都是空指针。大多数树形算法都采用这种存法。

7.3 二叉树的五条常用性质(只记结论)

这五条性质不需要背证明,会拿来算数量、判断完全二叉树就够了。

7.3.1 第 i 层最多有 2i−1 个结点

根在第 1 层,只有 1 个;第 2 层最多 2 个;第 3 层最多 4 个…… 例:第 5 层最多有 24 = 16 个结点。

7.3.2 深度为 k 的二叉树最多有 2k−1 个结点

把每一层的最大值加起来:1 + 2 + 4 + … + 2k−1 = 2k−1。 满二叉树正好取到这个最大值。

7.3.3 叶子数 = 度为 2 的结点数 + 1

对任何一棵非空二叉树,设叶子数为 n0,度为 2 的结点数为 n2,则 n0 = n2 + 1。 例:一棵树有 5 个叶子,那么度为 2 的结点就有 4 个。

7.3.4 n 个结点的完全二叉树深度

深度 = ⌊log2 n⌋ + 1。 例:1000 个结点,29 = 512 ≤ 1000 < 1024 = 210, 所以深度是 9 + 1 = 10。

7.3.5 完全二叉树的下标关系(从 1 开始编号)

结点 i(i>1)的双亲是 ⌊i/2⌋,左孩子是 2i, 右孩子是 2i+1。如果 2i 超过结点总数,就没有左孩子; 如果 2i+1 超过,就没有右孩子。

例:6 个结点的完全二叉树,结点 3 的左孩子是 6,右孩子 7 不存在; 结点 6 的双亲是 3。

7.4 四种遍历

7.4.1 遍历是什么

遍历就是按某种规则,把树上的每个结点都访问一次,而且只访问一次。 常用的有四种顺序:

7.4.2 手工走一遍

用 7.1.1 的那棵树练习:

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

两个小规律:先序的第一个一定是根;后序的最后一个一定是根; 中序里根左边的结点都在左子树,右边的都在右子树。

7.4.3 看动画

下面四个动画分别演示四种遍历,注意绿色是已经访问过的结点:

7.4.4 递归代码

三种深度优先遍历的代码几乎一样,区别只在「什么时候访问根」这一行:

#include <iostream>
using namespace std;

struct Node {
    char val;
    Node *left, *right;
    explicit Node(char v) : val(v), left(nullptr), right(nullptr) {}
};

void preOrder(Node* p) {
    if (!p) return;
    cout << p->val;          // 先访问根
    preOrder(p->left);
    preOrder(p->right);
}

void inOrder(Node* p) {
    if (!p) return;
    inOrder(p->left);
    cout << p->val;          // 中间访问根
    inOrder(p->right);
}

void postOrder(Node* p) {
    if (!p) return;
    postOrder(p->left);
    postOrder(p->right);
    cout << p->val;          // 最后访问根
}

int main() {
    /* 手工建出 7.1.1 的那棵树 */
    Node* A = new Node('A');
    Node* B = new Node('B');
    Node* C = new Node('C');
    Node* D = new Node('D');
    Node* E = new Node('E');
    Node* F = new Node('F');
    Node* G = new Node('G');

    A->left = B;  A->right = C;
    B->left = D;  B->right = E;
    E->left = G;
    C->right = F;

    cout << "先序: "; preOrder(A);  cout << "\n";   // ABDEGCF
    cout << "中序: "; inOrder(A);   cout << "\n";   // DBGEACF
    cout << "后序: "; postOrder(A); cout << "\n";   // DGEBFCA
    return 0;
}

每个结点只访问一次,所以时间复杂度是 O(n); 递归深度最多等于树的高度。

7.5 并查集:把结点分成组

7.5.1 它解决什么问题

有 n 个元素,需要做两件事:

典型用途:判断两个元素是否在同一组,比如判断图里两个点是否连通。

7.5.2 用「父结点数组」表示

每个组看成一棵树,树的根就是这一组的代表。用一个数组 fa 记录每个结点的父亲: fa[x] = x 说明 x 是根。

例如 5 个元素,fa = [0, 0, 1, 3, 3]:

find(x):沿着父亲一直往上走,直到 fa[x] == x,这个 x 就是代表。
union(a, b):先找到两组的根,再让一个根指向另一个根, 例如 fa[find(a)] = find(b)。

一个小优化叫路径压缩:find 的时候,把沿途经过的结点直接连到根上, 以后再找就会更快。并查集的基础就这些,先会用 find / union 即可。

7.6 几句话小结