Lesson 0404 · 树与二叉树基础

④ 数据结构与算法 — 第 4 课

1. 树的基本概念

        1          ← 根 root
       / \
      2   3        ← 2、3 是 1 的孩子
     / \   \
    4   5   6      ← 4、5、6 是叶子

注意：树和链表最大的区别是——树不会成环，而且每个节点只有一个父节点。这两条保证了从根出发能走遍整棵树，且不会绕回来。

2. 二叉树：最多两个孩子

二叉树是最常用的树：每个节点最多有 左、右两个子节点。

struct Node {
    int val;
    Node* left;    // 左孩子
    Node* right;   // 右孩子

    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

空指针 nullptr 表示「这个方向没有孩子」。注意它和链表不同：链表只有一个方向，树有两个，所以每个节点要存两个指针。

3. 手动建一棵二叉树

Node* root = new Node(1);

root->left  = new Node(2);
root->right = new Node(3);

root->left->left   = new Node(4);
root->left->right  = new Node(5);
root->right->right = new Node(6);

这就建出了本节课开头的那棵树。注意 root->right->left 没有赋值，所以 3 只有右孩子 6，左孩子是 nullptr。

4. 三种深度优先遍历

遍历 = 按某种顺序访问每个节点一次。二叉树的三种经典顺序只差「访问根」这一步放在哪里。

void preorder(Node* root) {
    if (root == nullptr) return;
    cout << root->val << " ";   // 先访问根
    preorder(root->left);         // 再左
    preorder(root->right);        // 再右
}

void inorder(Node* root) {
    if (root == nullptr) return;
    inorder(root->left);          // 先左
    cout << root->val << " ";   // 再根
    inorder(root->right);         // 再右
}

void postorder(Node* root) {
    if (root == nullptr) return;
    postorder(root->left);        // 先左
    postorder(root->right);       // 再右
    cout << root->val << " ";   // 最后根
}

用上面那棵树（1 为根，2、3 是孩子，4、5 在 2 下，6 在 3 的右边）：

前序：1 2 4 5 3 6
中序：4 2 5 1 3 6
后序：4 5 2 6 3 1
层序：1 2 3 4 5 6

把结果按「第几个被访问」拆开，同一棵小树的四种顺序一目了然（表头 1–6 是访问次序，不是节点编号）：

盯住前三个：前序第一个是根 1，后序最后一个才是根 1，中序的根 1 在中间——这就是「根放在哪」的全部区别。层序则完全按层来，先第一层、再第二层、再第三层。

5. 层序遍历：一层一层访问

层序遍历用队列实现，先访问第 1 层，再第 2 层、第 3 层……

#include <queue>

void levelorder(Node* root) {
    if (root == nullptr) return;

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* cur = q.front();
        q.pop();

        cout << cur->val << " ";

        if (cur->left != nullptr)  q.push(cur->left);
        if (cur->right != nullptr) q.push(cur->right);
    }
}

上面那棵树的层序结果：

1 2 3 4 5 6

为什么用队列？因为层序是「先遇到的先处理」——第 2 层没处理完，不会轮到第 3 层，这正是队列的先进先出。换成栈就变成深度优先了。

6. 数组存二叉树

除了指针，也可以用数组存：下标 i 的左孩子是 2*i，右孩子是 2*i+1。

int tree[100] = {0, 1, 2, 3, 4, 5, 0, 6};

// 下标 1 是根
// 1 的左孩子是 2，右孩子是 3
// 2 的左孩子是 4，右孩子是 5
// 3 的左孩子是下标 6，但 tree[6] 是 0，表示空
// 3 的右孩子是下标 7，tree[7] = 6

注意：用数组存树，空位置要用 0 或其他特殊值占位，否则左右关系会错。上面 tree[6] = 0 就是给 3 的左孩子留的空位——如果没有它，tree[7] = 6 的位置就全错位了。

void preorderArray(int i) {
    if (tree[i] == 0) return;

    cout << tree[i] << " ";
    preorderArray(2 * i);       // 左孩子
    preorderArray(2 * i + 1);   // 右孩子
}

7. 完整示例

#include <iostream>
using namespace std;

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

// ==== 三种深度优先遍历 ====
void preorder(Node* root) {
    if (!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

void postorder(Node* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

// ==== 建树并输出 ====
int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(6);

    preorder(root);  cout << endl;
    inorder(root);   cout << endl;
    postorder(root); cout << endl;

    return 0;
}

8. 坑点清单

• 递归边界漏写：if (root == nullptr) return; 是三个遍历的第一行，漏了就是空指针崩溃。
• 前序 / 中序 / 后序搞混：三份代码只差「打印根」那一行的位置，背口诀不如把三行代码并排看。
• 层序遍历用 stack：顺序会变成深度优先，必须用 queue。
• 1-based 和 0-based 混用：2*i / 2*i+1 是 1-based 的公式，从 0 开始要整套换。
• 数组存树不留空位：空孩子不占位，2*i 就会指到别的子树去。
• 层序不判空就 q.push(root)：空树时后面取 cur->val 会崩。

9. 小测

10. 动手练习

        A
        / \
       B   C
      / \   \
     D   E   F

11. 本课小结

• 树：根、父、子、叶子、子树；每个节点只有一个父节点，且不会成环。
• 二叉树：每个节点最多左、右两个孩子，空方向用 nullptr 表示。
• 深度优先：前序根左右、中序左根右、后序左右根，差别只在打印根的位置。
• 层序：queue 一层一层访问，靠 FIFO 保证顺序。
• 数组存树：左 2*i、右 2*i+1，空位要占位。