二叉树详解：四种遍历方法及C++代码实现-北京尧图网络

1. 什么是二叉树二叉树Binary Tree是计算机科学中一种非常重要的数据结构它是一种特殊的树形结构。在二叉树中每个节点最多只能有两个子节点分别称为左子节点和右子节点。这两个子节点通常被区分为左子树和右子树且左右顺序不能颠倒。二叉树具有以下基本特征每个节点最多有两个子节点这是二叉树与一般树结构最核心的区别。左子树和右子树有明确顺序即使只有一个子节点也要区分它是左子节点还是右子节点。递归定义二叉树要么为空要么由根节点、左子树和右子树组成而左右子树本身也是二叉树。二叉树在计算机领域应用广泛例如二叉搜索树BST用于高效的数据查找和排序。堆Heap用于实现优先队列。哈夫曼树用于数据压缩。表达式树用于编译器的语法分析。2. 二叉树的节点定义在C中我们通常使用结构体或类来定义二叉树的节点。每个节点包含三个部分存储的数据、指向左子节点的指针、指向右子节点的指针。下面是一个典型的节点定义#include iostream using namespace std; // 二叉树节点定义 struct TreeNode { int val; // 节点存储的数据 TreeNode* left; // 指向左子节点的指针 TreeNode* right; // 指向右子节点的指针 // 构造函数 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };这里我们定义了一个名为TreeNode的结构体包含一个整型数据val和两个指针left、right。构造函数用于初始化节点默认将左右指针设为nullptr空指针。3. 二叉树的四种遍历方法二叉树的遍历是指按照某种特定顺序访问树中的所有节点每个节点恰好被访问一次。根据访问根节点与左右子树的先后顺序二叉树主要有四种遍历方法前序遍历、中序遍历、后序遍历和层序遍历。前三种遍历方法前序、中序、后序都属于深度优先遍历DFS它们通过递归或栈来实现而层序遍历属于广度优先遍历BFS通常借助队列来实现。3.1 前序遍历Preorder Traversal前序遍历的访问顺序是根节点 → 左子树 → 右子树。也就是说先访问根节点然后递归地前序遍历左子树最后递归地前序遍历右子树。前序遍历的递归实现代码如下// 前序遍历根 → 左 → 右 void preorderTraversal(TreeNode* root) { if (root nullptr) { return; // 空节点直接返回 } cout root-val ; // 1. 访问根节点 preorderTraversal(root-left); // 2. 遍历左子树 preorderTraversal(root-right); // 3. 遍历右子树 }前序遍历的特点是第一个访问的节点一定是根节点。因此前序遍历常用于复制一棵二叉树或者用于序列化二叉树。3.2 中序遍历Inorder Traversal中序遍历的访问顺序是左子树 → 根节点 → 右子树。先递归地中序遍历左子树然后访问根节点最后递归地中序遍历右子树。中序遍历的递归实现代码如下// 中序遍历左 → 根 → 右 void inorderTraversal(TreeNode* root) { if (root nullptr) { return; } inorderTraversal(root-left); // 1. 遍历左子树 cout root-val ; // 2. 访问根节点 inorderTraversal(root-right); // 3. 遍历右子树 }中序遍历有一个非常重要的性质对于二叉搜索树BST中序遍历的结果是一个递增的有序序列。因此中序遍历常用于验证一棵树是否为二叉搜索树或者将二叉搜索树转换为有序数组。3.3 后序遍历Postorder Traversal后序遍历的访问顺序是左子树 → 右子树 → 根节点。先递归地后序遍历左子树然后递归地后序遍历右子树最后访问根节点。后序遍历的递归实现代码如下// 后序遍历左 → 右 → 根 void postorderTraversal(TreeNode* root) { if (root nullptr) { return; } postorderTraversal(root-left); // 1. 遍历左子树 postorderTraversal(root-right); // 2. 遍历右子树 cout root-val ; // 3. 访问根节点 }后序遍历的特点是最后一个访问的节点一定是根节点。后序遍历常用于删除二叉树先删除子节点再删除根节点或者计算二叉树的高度和节点数。3.4 层序遍历Level Order Traversal层序遍历也称为广度优先遍历按照树的层次从上到下、从左到右依次访问每一层的节点。它需要使用队列Queue来辅助实现。层序遍历的实现代码如下#include queue // 层序遍历按层从上到下、从左到右 void levelOrderTraversal(TreeNode* root) { if (root nullptr) { return; } queueTreeNode* q; q.push(root); // 根节点入队 while (!q.empty()) { TreeNode* node q.front(); q.pop(); cout node-val ; // 访问当前节点 // 左子节点入队 if (node-left ! nullptr) { q.push(node-left); } // 右子节点入队 if (node-right ! nullptr) { q.push(node-right); } } }层序遍历的核心思想是每次从队列中取出一个节点并访问它然后将它的左右子节点依次加入队列。这样队列中始终保存着当前层和下一层的节点从而保证按层访问。4. 完整示例代码下面我们构建一棵具体的二叉树并演示四种遍历方法的完整运行结果。我们构建如下结构的二叉树1 / \ 2 3 / \ \ 4 5 6完整代码如下#include iostream #include queue using namespace std; // 二叉树节点定义 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // 前序遍历根 → 左 → 右 void preorderTraversal(TreeNode* root) { if (root nullptr) return; cout root-val ; preorderTraversal(root-left); preorderTraversal(root-right); } // 中序遍历左 → 根 → 右 void inorderTraversal(TreeNode* root) { if (root nullptr) return; inorderTraversal(root-left); cout root-val ; inorderTraversal(root-right); } // 后序遍历左 → 右 → 根 void postorderTraversal(TreeNode* root) { if (root nullptr) return; postorderTraversal(root-left); postorderTraversal(root-right); cout root-val ; } // 层序遍历按层从上到下、从左到右 void levelOrderTraversal(TreeNode* root) { if (root nullptr) return; queueTreeNode* q; q.push(root); while (!q.empty()) { TreeNode* node q.front(); q.pop(); cout node-val ; if (node-left ! nullptr) q.push(node-left); if (node-right ! nullptr) q.push(node-right); } } int main() { // 构建二叉树 TreeNode* root new TreeNode(1); root-left new TreeNode(2); root-right new TreeNode(3); root-left-left new TreeNode(4); root-left-right new TreeNode(5); root-right-right new TreeNode(6); cout 前序遍历结果: ; preorderTraversal(root); cout endl; cout 中序遍历结果: ; inorderTraversal(root); cout endl; cout 后序遍历结果: ; postorderTraversal(root); cout endl; cout 层序遍历结果: ; levelOrderTraversal(root); cout endl; return 0; }运行上述代码输出结果如下前序遍历结果: 1 2 4 5 3 6 中序遍历结果: 4 2 5 1 3 6 后序遍历结果: 4 5 2 6 3 1 层序遍历结果: 1 2 3 4 5 65. 四种遍历方法对比总结为了更直观地对比四种遍历方法我们整理成如下表格遍历方法访问顺序实现方式典型应用前序遍历根 → 左 → 右递归 / 栈复制二叉树、序列化中序遍历左 → 根 → 右递归 / 栈BST 排序输出后序遍历左 → 右 → 根递归 / 栈删除二叉树、计算高度层序遍历逐层从左到右队列求树宽度、最短路径从上面的示例结果可以看出前序遍历的第一个节点是根节点1。中序遍历中根节点1位于左子树节点4、2、5和右子树节点3、6之间。后序遍历的最后一个节点是根节点1。层序遍历严格按照树的层次输出每层从左到右。6. 总结二叉树是数据结构学习中的核心内容掌握其四种遍历方法至关重要。前序、中序、后序遍历属于深度优先遍历通过递归可以非常简洁地实现层序遍历属于广度优先遍历需要借助队列完成。理解这四种遍历的访问顺序和实现原理是后续学习二叉搜索树、平衡二叉树、堆等高级数据结构的基础。在实际面试和工程应用中二叉树的遍历经常与递归、栈、队列等知识点结合考察。建议读者在理解递归实现的基础上进一步尝试使用迭代方式显式栈实现前序、中序和后序遍历以加深对遍历过程的理解。

二叉树详解：四种遍历方法及C++代码实现

相关推荐

基于STM32与PID算法的高精度半导体制冷片温控系统设计与实现

Sigrity OptimizePI CapGen实战：基于目标阻抗的PDN去耦电容自动优化

URP程序化草地实战：Compute Shader与数据驱动渲染

更多资讯

GO 小游戏在线试水

【10】自动驾驶行人车辆数据集(有v5/v8模型)/YOLO自动驾驶行人车辆检测

PRG解决哪种重复提交：POST之后为什么用303跳到GET

xv6的ecall怎么回来？从a0的第一次交换走到sret

ACE-Step 1.5 本地音乐生成安装教程：10 分钟从 0 到第一首歌完整指南

QT for webassembly

今日更新

PLFM_RADAR：从被动告警到主动感知的微服务健康监控系统

SPI隔离设计实战：MAX14431BAEE+与STM32F407工业级应用

数字隔离器如何根治SPI通信地环路干扰：MAX14431与TM4C129实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？