问小白 wenxiaobai
资讯
历史
科技
环境与自然
成长
游戏
财经
文学与艺术
美食
健康
家居
文化
情感
汽车
三农
军事
旅行
运动
教育
生活
星座命理

二叉树的前、中、后序遍历(C++)

创作时间:
2025-03-19 06:07:16
作者:
@小白创作中心

二叉树的前、中、后序遍历(C++)

引用
CSDN
1.
https://m.blog.csdn.net/m0_74091276/article/details/146070260

二叉树的遍历是数据结构与算法中的基础内容,掌握前序、中序和后序遍历方法对于深入学习树结构及其算法至关重要。本文通过代码示例介绍了二叉树的三种深度优先遍历方法,并使用递归方式实现,帮助读者深入理解二叉树的遍历过程及其应用。

1 简介

本文通过代码示例介绍了二叉树的三种深度优先遍历方法——前序遍历(根-左-右)、中序遍历(左-根-右)和后序遍历(左-右-根),并使用递归方式实现。递归方法直观易懂,符合树的天然递归结构,每种遍历方式都遵循固定的访问顺序:前序遍历先访问根节点,再遍历左子树和右子树;中序遍历先遍历左子树,再访问根节点,最后遍历右子树;后序遍历则先遍历左右子树,最后访问根节点。本文提供清晰的 C++ 代码示例,并分析递归的工作原理,帮助读者深入理解二叉树的遍历过程及其应用。

2 前序遍历

2.1 问题描述

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
数据范围:二叉树的节点数量满足 1≤n≤100 1≤n≤100 ,二叉树节点的值满足 1≤val≤100 1≤val≤100 ,树的各节点的值各不相同
示例 1:

2.1.1 示例1
输入:

{1,#,2,3}

返回值:

[1,2,3]

2.2 解题思路

采用递归方式实现二叉树的前序遍历(根-左-右),并将遍历结果存储在
vector
中。
preorderTraversal
函数调用
preorder
递归函数,
preorder
依次执行:访问当前节点(存入
result
)→ 遍历左子树 → 遍历右子树。递归终止条件是当前节点为空(即
nullptr
),此时直接返回。

2.3 代码实现

  
    vector<int> preorderTraversal(TreeNode* root) {
        // write code here
        vector<int> result;
        preorder(root, result);
        return result;
    }
    void preorder(TreeNode* node, vector<int>& result)
    {
        if(node == nullptr) return;
        result.push_back(node->val);
        preorder(node->left, result);
        preorder(node->right, result);
    }  

3 中序遍历

3.1 问题描述

给定一个二叉树的根节点root,返回它的中序遍历结果。
数据范围:树上节点数满足 0≤n≤10000≤n≤1000,树上每个节点的值满足 −1000≤val≤1000−1000≤val≤1000
进阶:空间复杂度 O(n)O(n),时间复杂度 O(n)O(n)
3.1.1 示例1
输入:

{1,2,#,#,3}

返回值:[2,3,1]

3.1.2 示例2

输入:

{}

返回值:[]

3.1.3 示例3
输入:

{1,2}

返回值:[2,1]

3.1.4 示例4
输入:

{1,#,2}

返回值:[1,2]

3.2 解题思路

采用递归方式实现二叉树的中序遍历(左-根-右),并将遍历结果存储在
vector
中。
inorderTraversal
函数调用
inorder
递归函数,
inorder
依次执行:先递归遍历左子树 → 访问当前节点(存入
result
)→ 递归遍历右子树。递归终止条件是当前节点为空(即
nullptr
),此时直接返回。

3.3 代码实现

  
    vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        vector<int> result;
        inorder(root, result);
        return result;
    }
    void inorder(TreeNode* node, vector<int>& result)
    {
        if(node == nullptr) return;
        inorder(node->left, result);
        result.push_back(node->val);
        inorder(node->right, result);
    }  

4 后序遍历

4.1 问题描述

给定一个二叉树,返回他的后序遍历的序列。
后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。
数据范围:二叉树的节点数量满足 1≤n≤100 1≤n≤100 ,二叉树节点的值满足 1≤val≤100 1≤val≤100 ,树的各节点的值各不相同
样例图
4.1.1 示例1
输入:

{1,#,2,3}

返回值:

[3,2,1]

4.1.2 示例2
输入:

{1}

返回值:

[1]

4.2 解题思路

采用递归方式实现二叉树的后序遍历(左-右-根),并将遍历结果存储在
vector
中。
postorderTraversal
函数调用
postorder
递归函数,
postorder
依次执行:先递归遍历左子树 → 递归遍历右子树 → 访问当前节点(存入
result
)。递归终止条件是当前节点为空(即
nullptr
),此时直接返回。

4.3 代码实现

  
    vector<int> postorderTraversal(TreeNode* root) {
        // write code here
        vector<int> result;
        postorder(root, result);
        return result;
    }
    void postorder(TreeNode* node, vector<int>& result)
    {
        if(node == nullptr) return;
        postorder(node->left, result);
        postorder(node->right, result);
        result.push_back(node->val);
    }  

5 总结

本文介绍了二叉树的前序遍历(根-左-右)、中序遍历(左-根-右)和后序遍历(左-右-根)三种深度优先遍历方法,并使用递归方式分别实现。递归方法利用二叉树的天然递归结构,使代码简洁直观,每种遍历方式都遵循固定的访问顺序。文章通过示例输入输出、解题思路解析和代码实现,帮助读者掌握不同遍历方法的应用。递归终止条件为当前节点为空(nullptr),以确保遍历完整执行。理解这三种遍历方式对于深入学习树结构及其算法至关重要,能够为后续的二叉树问题提供坚实基础。

© 2023 北京元石科技有限公司 ◎ 京公网安备 11010802042949号