二叉树基础：概念、存储结构与遍历算法详解

2.2 链式存储

可以创建两个数组 l[N]，r[N]，其中 l[i] 表示结点号为 i 的结点的左孩子编号，r[i] 表示结点号为 i 的结点的右孩子编号。

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int l[N], r[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        // 存下 i 号结点的左右孩子
        cin >> l[i] >> r[i];
    }
    return 0;
}

三、二叉树的遍历

3.1 深度优先遍历

不同于常规树的深度优先遍历，二叉树因其独特的性质可以划分成三种深度优先遍历：先序遍历，中序遍历，和后序遍历。其中，三种遍历方式的不同在于处理根节点的时机。 对于一棵二叉树而言，整体可以划分成三部分：根节点 + 左子树 + 右子树： • 先序遍历的顺序为：根 + 左 + 右； • 中序遍历的顺序为：左 + 根 + 右； • 后序遍历的顺序为：左 + 右 + 根。

3.1.1 先序遍历

// 先序遍历
void dfs1(int u) {
    if (u == 0) // 递归出口
        return;
    cout << u << " "; // 根
    dfs1(l[u]); // 左
    dfs1(r[u]); // 右
}

测试：

3.1.2 中序遍历

// 中序遍历
void dfs2(int u) {
    if (u == 0) // 递归出口
        return;
    dfs2(l[u]); // 左
    cout << u << " "; // 根
    dfs2(r[u]); // 右
}

测试：

3.1.3 后序遍历

// 后序遍历
void dfs3(int u) {
    if (u == 0) // 递归出口
        return;
    dfs3(l[u]); // 左
    dfs3(r[u]); // 右
    cout << u << " "; // 根
}

测试：

3.1.4 所有测试代码

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int l[N], r[N];

// 先序遍历
void dfs1(int u) {
    if (u == 0) // 递归出口
        return;
    cout << u << " "; // 根
    dfs1(l[u]); // 左
    dfs1(r[u]); // 右
}

// 中序遍历
void dfs2(int u) {
    if (u == 0) // 递归出口
        return;
    dfs2(l[u]); // 左
    cout << u << " "; // 根
    dfs2(r[u]); // 右
}

// 后序遍历
void dfs3(int u) {
    if (u == 0) // 递归出口
        return;
    dfs3(l[u]); // 左
    dfs3(r[u]); // 右
    cout << u << " "; // 根
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
    }
    // dfs1(1); // 先序遍历
    // dfs2(1); // 中序遍历
    dfs3(1); // 后序遍历
    return 0;
}

3.2 宽度优先遍历

这个就和常规的树的遍历方式一样，直接用队列帮助层序遍历即可。

#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int l[N], r[N];

void bfs() {
    queue<int> q;
    q.push(1);
    while (q.size()) {
        int u = q.front();
        q.pop();
        cout << u << " "; // 左右孩子入队
        if (l[u]) q.push(l[u]);
        if (r[u]) q.push(r[u]);
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];
    bfs();
    return 0;
}

运行结果：