【数据结构指南】深入二叉树遍历

Ne0inhk

— 14 min read
【数据结构指南】深入二叉树遍历

前言：

        在前文中，我们探讨了完全二叉树和满二叉树的概念与性质，并基于完全二叉树实现了堆这一数据结构。然而，对于普通二叉树的认识仍有待深入，本文将系统性地介绍普通二叉树的遍历相关内容。

        

        

一、前置说明

        

一般而言，对于一棵普通二叉树是通过链式结构定义，即每个节点包含三个部分：

        

1.数据域（data）：用于存储节点的值

        

2.左指针（left）：用于指向左子节点

        

3.右指针（right）：用于指向右子节点        

        

typedef int BTDataType;//此处将 （int）整形 作为节点存储的内容 typedef struct BinaryTree { BTDataType data; struct BinaryTree* left; struct BinaryTree* right; }BTNode;

        

        在学习二叉树的基本操作前，需先要先创建一棵二叉树，然后才能学习其相关的基本操作，但是由于我们对二叉树结构掌握还不够深入，为此我们可以通过手动快速创建一棵简单的二叉树。

如下图所示：

        

代码实现如下：        

BTNode* BuyNode(int x) { BTNode* root = (BTNode *)malloc(sizeof(BTNode)); if (root == NULL) { perror("malloc fail"); return NULL; } root->data = x; root->left = NULL; root->right = NULL; return root; } BTNode* TreeCreate() { BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); node1->left = node2; node1->right = node4; node2->left = node3; node2->right = node6; node4->left = node5; return node1; }

        

二、二叉树前序遍历

        

1. 前序遍历的操作

        

   A、若此棵树为空树，即根节点为NULL，不进行任何操作。

        

   B、若此棵树不为空，即根节点不为NULL，进行如下操作：

        ①访问根节点

        ②先序遍历左子树

        ③先序遍历右节点

所以先序遍历也可简记为： 根   左   右  的顺序进行遍历，具体如何进行遍历，请帅观众耐心往下看。

           

现在有如下一棵二叉树：

        

由根节点 -> 左子树 -> 右子树 这个顺序：

        

那么肯定有帅观众问，直接访问根节点好理解，那么如何理解访问左子树和右子树呢？

       

其实我们可以把左子树再看成一棵树，这样就又可以看成：        根节点    左子树     右子树

        

其实我们也可以把右子树也看成一棵树，这样就也可以看成：     根节点   左子树      右子树

        

如上图所示：根节点1  左子树（以2为根节点）  右子树（以4为根节点）           

                        

                      左子树： 根节点2  左子树（以3为根节点）   右子树（空）

                        

                      右子树： 根节点4  左子树（以5为根节点）  右子树（以6为根节点）

        

这样是不是将一个大问题分成若干个小问题，这不就是递归的思想，所以我们可以通过递归函数的形式，对先序遍历的代码编写。

        

        

前序遍历的结果如下图所示：

        

        

如果不省略空节点的打印即为：1    2    3    NULL   NULL   NULL   4   5   NULL    NULL    6   NULL   NULL

        

如果省略空节点的打印即为：1    2    3    4    5    6

        

        

2.前序遍历代码实现

        

//前序遍历 void PrevOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->data); PrevOrder(root->left); PrevOrder(root->right); }

        

打印结果如下图所示：        

        

        

3.递归调用图

        

        

三、二叉树中序遍历

        

1.中序遍历的操作

        

   A、若此棵树为空树，即根节点为NULL，不进行任何操作。

        

   B、若此棵树不为空，即根节点不为NULL，进行如下操作：

        ①中序访问左子树

        ②访问根节点

        ③中序遍历右节点

所以先序遍历也可简记为：左    根   右  的顺序进行遍历。

        

现有如下一棵二叉树：

        

        

        

中序遍历的结果如下图所示：

        

如果不省略空节点的打印即为：NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL

        

如果省略空节点的打印即为： 3     2       1      5      4     6

        

        

2.中序遍历代码实现

        

//中序遍历 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); }

        

        

        

四、二叉树后序遍历

        

1.后序遍历的操作

        

 A、若此棵树为空树，即根节点为NULL，不进行任何操作。

        

   B、若此棵树不为空，即根节点不为NULL，进行如下操作：

        ①后序访问左子树

        ②访问根节点

        ③后序遍历右节点

所以先序遍历也可简记为：左    右   根  的顺序进行遍历。

        

现有如下一棵二叉树：

        

      

后序遍历的结果如下图所示：

        

        

如果不省略空节点的打印即为：NULL    NULL    3    NULL    2    NULL    NULL    5    NULL    NULL    6    4    1

        

如果省略空节点的打印即为： 3     2       5      6      4     1

        

        

2.后序的遍历代码实现

        

//后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); }

        

        

五、二叉树层序遍历

        

1.层次遍历的操作

进行层次遍历时需要借助一个队列，层次遍历的核心思想为：上一层的节点出队，带入下一层的节点入队

如下图所示：

        

① 将二叉树的根结点入队；

        

② 若队列非空，则队头结点出队并访问该结点，若它有左孩子，则将其左孩子入队；若它有右孩子，则将其右孩子入队；

        

        

        

下图为二叉树的层次遍历，即按照箭头所指的方向，按照自上而下，自左向右的顺序对二叉树的各个结点进行逐层访问.

        

可以得到下图二叉树的层次遍历序列为：1   2   3   4   5    6

                

        

2.层序遍历代码实现

        

// 层序遍历 // 上一层节点出队，带入下一层节点入队 void TreeLevelOrder(BTNode* root) { //创建一个队列 Queue q; //初始化队列 QueueInit(&q); //如果根节点指针不为空入队 if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { //获取队头元素，获取的是QNode节点中存储的值 BTNode* front = QueueFront(&q); //出队头，这里是销毁了QNode节点，而存储在QNode节点中的BTNode节点并未删除 QueuePop(&q); //打印队头信息 printf("%d ", front->data); //并访问该节点，如果该节点的左孩子存在则入队，如果该节点的右孩子存在则入队 if (front->left) QueuePush(&q, front->left); if (front->right) QueuePush(&q, front->right); } //销毁队列 QueueDestroy(&q); }

       

六、小试牛刀

     

1.练习一   

        

二叉树的前序（先序）遍历为：EFHIGJK，二叉树的中序遍历：HFIEJKG，则二叉树为?

        

核心思路：由前序遍历确定根，中序遍历确定左右子树

        

前序遍历的特点：根  左子树  右子树         中序遍历的特点： 左子树     根      右子树

        

所以对于前序遍历而言，从左往右进行的过程就是相当于对根的遍历

        

而通过根的确定，对中序序列进行分割左右子树。

        

        

二叉树如下图所示：

        

        

2.练习二

        

二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树的形状为?

        

核心思路：由后序遍历确定根，中序遍历确定左右子树

        

后序遍历的特点：  左子树  右子树   根         中序遍历的特点： 左子树     根      右子树

        

对于后序序列从右往左的过程，就相当于对根进行确定

        

 而通过根的确定，对中序序列进行分割左右子树。      

        

        

 二叉树如下图所示：        

        

        

                

3.练习三

        

二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列  

        

核心思路：由后序遍历确定根，中序遍历确定左右子树

        

后序遍历的特点：  左子树  右子树   根         中序遍历的特点： 左子树     根      右子树

        

对于后序序列从右往左的过程，就相当于对根进行确定

        

 而通过根的确定，对中序序列进行分割左右子树。

        

        

二叉树如下图所示：

        

  故而：层序遍历的结果为：FEDCBA

        

4.练习四

        

完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH ，则该完全二叉树的前序序列为?

        

由层序遍历的特性：自上而下，自左到右

        

二叉树如下图所示：

        

故而前序遍历的结果为：ABDHECFG

        

        

 既然看到这里了，不妨关注+点赞+收藏，感谢大家，若有问题请指正。

Read more

Python基于Android的电竞社区论坛交流系统 小程序

Python基于Android的电竞社区论坛交流系统 小程序

文章目录 * Python 基于 Android 的电竞社区论坛交流系统小程序技术大纲 * 系统架构设计 * 后端技术实现 * 前端技术实现 * 核心功能模块 * 性能与安全优化 * 测试与部署 * 扩展方向 * 系统设计与实现的思路 * 主要技术与实现手段 * 源码lw获取/同行可拿货,招校园代理 ：文章底部获取博主联系方式！ Python 基于 Android 的电竞社区论坛交流系统小程序技术大纲 系统架构设计 采用前后端分离架构，后端使用 Python（Django/Flask/FastAPI），前端使用 Android 原生开发或跨平台框架（如 Flutter）。数据库选用 MySQL 或 PostgreSQL 存储用户和帖子数据，Redis 处理缓存和实时消息。 后端技术实现 API 接口设计 RESTful API 规范，使用 Django REST

By Ne0inhk

llama-cpp-python完整安装指南：5步解决90%新手问题 [特殊字符]

llama-cpp-python完整安装指南：5步解决90%新手问题 🎯 【免费下载链接】llama-cpp-pythonPython bindings for llama.cpp 项目地址: https://gitcode.com/gh_mirrors/ll/llama-cpp-python llama-cpp-python是专为llama.cpp库设计的Python绑定项目，为开发者提供了在Python环境中高效运行本地大语言模型的完美解决方案。通过该项目，您可以轻松实现文本生成、对话交互、多模态推理等AI功能，无需依赖云端API即可享受强大的本地AI推理能力。 🔧 一键编译配置技巧 环境配置是新手最容易遇到问题的环节。llama-cpp-python支持多种硬件加速后端，正确配置编译环境至关重要。 步骤1：基础环境检查 确保系统已安装Python 3.8+和C编译器： * Linux/Mac: gcc或clang * Windows: Visual Studio或MinGW * MacOS: Xcode命令行工具 步骤2：核心安装命令 pip in

By Ne0inhk

【Python 爬虫实战】抓取 BOSS 直聘

一、前言 在求职或行业调研过程中，我们常常需要批量获取招聘平台的岗位信息，手动复制粘贴效率极低。本文将通过 DrissionPage 框架实现BOSS 直聘大数据开发岗位的批量爬取，无需分析复杂的页面元素，直接监听接口数据包获取 JSON 数据，最终将结果存入 CSV 文件，全程代码简洁易懂，新手也能快速上手。 本次实战目标 1. 监听 BOSS 直聘岗位列表接口，获取结构化 JSON 数据 2. 提取岗位名称、公司、薪资、学历要求等核心信息 3. 将爬取结果批量存入 CSV 文件，方便后续数据分析 4. 实现自动翻页，爬取前 20 页的岗位数据 二、环境准备 1. 所需 Python 库 本次实战核心使用 DrissionPage 框架（

By Ne0inhk
【Python库和代码案例：第二课】一边写“鼓励师”给自己打气，一边写“学生管理”鞭策别人：Python拿捏了

【Python库和代码案例：第二课】一边写“鼓励师”给自己打气，一边写“学生管理”鞭策别人：Python拿捏了

🎬 个人主页：艾莉丝努力练剑 ❄专栏传送门：《C语言》《数据结构与算法》《C/C++干货分享&学习过程记录》 《Linux操作系统编程详解》《笔试/面试常见算法：从基础到进阶》《Python干货分享》 ⭐️为天地立心，为生民立命，为往圣继绝学，为万世开太平 🎬 艾莉丝的简介： 文章目录 * 3 ~> 第三方库 * 3.5 代码示例：“程序猿鼓励师” * 3.5.1 安装第三方依赖 * 3.5.2 准备音频文件 * 3.5.3 编写代码 * 3.5.4 改进代码 * 3.5.5 操作流程 * 3.5.

By Ne0inhk