二叉树核心解析：结构、存储与遍历算法详解

#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;
}

三、遍历算法

二叉树的遍历主要分为深度优先遍历（DFS）和宽度优先遍历（BFS）。

3.1 深度优先遍历

根据处理根节点的时机不同，分为先序、中序和后序三种。整体可以划分为三部分：根节点 + 左子树 + 右子树。

• 先序遍历：根 + 左 + 右
• 中序遍历：左 + 根 + 右
• 后序遍历：左 + 右 + 根

代码实现

这里使用递归方式实现，逻辑非常直观。需要注意的是，测试代码中函数命名需区分开，避免冲突。

#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 宽度优先遍历

宽度优先遍历（BFS）通常使用队列来实现层序遍历。将根节点入队，然后循环取出队首元素，将其左右孩子依次入队。

#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;
}

运行结果会按照层级顺序输出节点编号。