【初阶数据结构】二叉树的几种遍历详解

这篇具有很好参考价值的文章主要介绍了【初阶数据结构】二叉树的几种遍历详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言

君兮_的个人主页

勤时当勉励 岁月不待人

C/C++ 游戏开发

Hello,米娜桑们,这里是君兮_,有了我们之前介绍的树结构与二叉树的基础概念,今天我们来讲讲对二叉树的基本使用——遍历

一.二叉树的创建

  • 我们自己先简单链式连接几个结点来创建一个二叉树方便我们之后对遍历的讲解
typedef struct BinaryTreeNode
{
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
    int val;
}BTNode;
//初始化
BTNode* BuyNode(int x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    if (node == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    node->val = x;
    node->left = node->right = NULL;
    return node;
}
int main()
{
  
    //手动构建
    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;
    node4->left = node5;
    node4->right = node6;
    int size = TreeLeafSize(node1);
    printf("%d", size);
    return 0;
}
  • 好了,有了这个基本的二叉树,我们正式开始我们今天的主要内容

二. 二叉树的遍历

1.前序遍历

  • 什么叫前序遍历?
    抛开定义简单点来说,就是先访问根节点,再访问左子树,最后访问右子树 这种遍历方式就叫做前序遍历
void PrevOrder(BTNode* root)
{
    if (root == NULL)
        return;
    printf("%d ", root->val);

    PrevOrder(root->left);
    PrevOrder(root->right);

}
  • 好了,这样我们这里就讲完了,来看看其他的遍历方式…
  • 此时你可能一头雾水,我讲了什么吗?如讲,没错这里的代码只有这短短的几行却暗藏玄只因,我们来详细的分析一下上面的代码在干嘛
if (root == NULL)
        return;
  • 首先,当这个二叉树为空或者程序遍历完二叉树后,我们就直接return,这点不难理解
	printf("%d ", root->val);
    PrevOrder(root->left);
    PrevOrder(root->right);

  • 然后我们打印了此时这个结点的值(注意,这里的打印该值就是相当于访问了这个结点)
  • 最后我们又递归调用了这个函数,并先传入该结点的左子树,最后又传入该结点的右子树
  • 这里还是有点不明所以,我们在干嘛?但是你仔细观察一下,这里的执行顺序是不是很像我们刚才讲的前序遍历的特点 该结点->该结点的左子树->该结点的右子树 我们画图来解释一下
  • 这里有如下的一个二叉树
    【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言
  • 我们现在来前序遍历一下
    【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言
  • 经过图中的一轮遍历,我们已经遍历完根结点和根结点的左子树了,下面我们要遍历根1的右子树
    【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言
  • 通过我们上面的分析,我们得知,当我们前序遍历这个二叉树时,打印在屏幕上的结果应该是 1 2 3 4 5 6
  • 我们来测试一下我们的结果
    【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言

2.中序遍历

  • 啥叫中序遍历呢?
  • 根据上面我们对前序遍历的简单解释,我们也可以相应的给中序遍历一个类似的解释
    当遍历时,先访问左子树再访问根结点最后访问右子树称为中序遍历
void InOrder(BTNode* root)
{
    if (root == NULL)
        return;
   
   InOrder(root->left);
   printf("%d ", root->val);
   InOrder(root->right);
}
  • 仔细观察我们发现,中序遍历和前序遍历非常类似,那就是访问的顺序,中序先递归左子树,然后访问根结点,最后再递归右子树,我们还是通过上面那个例子来画图讲解一下
    【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言
  • 此时根结点的左子树遍历完 打印根结点1 开始遍历右子树
    【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言
  • 那照着这样的逻辑结果应该打印出 3 2 1 5 4 6
    【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言
  • 注意:这里很多人会有一个误区,如果有一个题问你,该二叉树第一个访问的是什么?
    中序遍历先遍历左子树,那么很多人都误以为先访问的是3,但其实访问的是NULL也就是3的左子树,然后才是根结点,最后是右子树也是NULL,此时该结点遍历完开始回归
    【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言

3.后序遍历

  • 后序遍历
  • 同理,我们也可以相应的给后序遍历一个类似的解释
    当遍历时,先访问左子树再访问右子树最后访问根结点称为后序遍历
void PostOrder(BTNode* root)
{
    if (root == NULL)
        return;

    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ", root->val);
}
  • 上面已经画过两遍了,这里简单的画一下供大家参考
    【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言
  • 后序遍历结果应该是 3 2 5 6 4 1 我们来验证一下

【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言


三. 二叉树的层序遍历

  • 与之前的几种遍历方法不同,层序遍历不需要使用递归,层序遍历的实现往往是伴随着队列的。
  • 什么是层序遍历?
    就是一层一层的遍历二叉树
    【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言
  • 那我们怎末用队列实现呢?
  • 我们知道,关于队列这个结构是先进先出的,也就是先放进去的一定是在队首,类似树中的根节点,利用这个特性,我们可以写出这段代码来实现层序遍历
void LevelOrder(BTNode* root)
{
	Que q;
	QueueInit(&q);//初始化队列

	if (root)
		QueuePush(&q, root);//把要遍历的二叉树的根节点插入队列中

	while (!QueueEmpty(&q))//队列判空
	{
		BTNode* front = QueueFront(&q);//获取队首元素
		printf("%d ", front->val);//打印队首存储的元素
		if (front->left)//队首的左子树不为空就把左子树插入队列
			QueuePush(&q, front->left);

		if (front->right)//队首的右子树不为空就把右子树插入队列
			QueuePush(&q, front->right);

		QueuePop(&q);//让队首离队
	}
	printf("\n");

	QueueDestroy(&q);//销毁队列
}
  • 上面某些有关队列的操作看注释也没看懂的话可以看看这篇博客我对队列的介绍
    【数据结构】带你深入栈和队列,轻松实现各种接口功能
  • 具体分为哪几步呢。我们来画图看看
    【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言
    【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言
    【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言
    【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言
    【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言
    【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言
  • 相信此时你通过上图能明白层序遍历是怎么完成的,相比于之前的递归的前中后序遍历,层序遍历无疑简单了很多。

总结

  • 今天的内容就到这里了,这些都是二叉树的基础的使用方法,但无疑是非常重要的,后面很多的难题以及其他用法都是从此繁衍而来,因此,弄懂这里非常重要
  • 这里的难点是递归的理解,最好的理解方法就是像我一样画递归展开图,如果你能把递归的图给画明白,那我相信二叉树的遍历就对你不难了,好了,如果有任何有关的问题,欢迎在评论区提出或者直接私信我,我看到有时间会第一时间回复的!!

新人博主创作不易,如果感觉文章内容对你有所帮助的话不妨三连一下再走呗。你们的支持就是我更新的动力!!!

**(可莉请求你们三连支持一下博主!!!点击下方评论点赞收藏帮帮可莉吧)**

【初阶数据结构】二叉树的几种遍历详解,初阶数据结构,数据结构,开发语言,算法,c语言文章来源地址https://www.toymoban.com/news/detail-713479.html

到了这里,关于【初阶数据结构】二叉树的几种遍历详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构初阶之二叉树的详细解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶    Linux 欢迎大家点赞,评论,收藏。 一起努力,共赴大厂。 目录 1.前言  2.二叉树各个功能代码实现 2.1二叉树结构体 2.2二叉

    2024年02月05日
    浏览(42)
  • C语言数据结构初阶(10)----二叉树的实现

    · CSDN的uu们,大家好。这里是C语言数据结构的第十讲。 · 目标:前路坎坷,披荆斩棘,扶摇直上。 · 博客主页: @姬如祎 · 收录专栏: 数据结构与算法     目录 1. 函数接口一览 2. 函数接口的实现 2.1 BTNode* BuyNode(BTDataType x) 的实现 2.2 BTNode* CreateTree() 的实现  2.3 void

    2023年04月08日
    浏览(44)
  • 【数据结构初阶】八、非线性表里的二叉树(二叉树的实现 -- C语言链式结构)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】七、非线性表里的二叉树(堆的实现 -- C语言顺序结构)-CSDN博客  ==========

    2024年02月08日
    浏览(51)
  • 初阶数据结构之---二叉树链式结构(二叉树的构建,二叉树的前序,中序,后序和层序遍历,计算二叉树结点个数,第k层结点个数,叶子结点个数,判断是否为完全二叉树)

    本篇博客是初阶数据结构树的收尾,将会讲掉 基本二叉树链式结构的具体内容和实现,包括二叉树的构建,前序遍历,中序遍历,后序遍历和层序遍历,计算二叉树结点个数,第k层结点个数,二叉树叶子结点个数,以及判断一个二叉树是否为完全二叉树 。话不多说,开始我

    2024年03月24日
    浏览(50)
  • 【数据结构】树、二叉树的概念和二叉树的顺序结构及实现

    之前我们学习了顺序表、链表以及栈和队列这些数据结构,但这些数据结构都是线性的(一对一)。接下来要学习 非线性的数据结构——树(二叉树) ,相比前面的,树的结构更加复杂,话不多说,直接进入正题吧。 树是一种 非线性的数据结构 ,它是 一对多(也有可能是

    2024年02月07日
    浏览(42)
  • 数据结构:二叉树(初阶)

    朋友们、伙计们,我们又见面了,本期来给大家解读一下二叉树方面的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成!   C 语 言 专 栏:C语言:从入门到精通 数据结构专栏:数据结构 个  人  主  页 :stackY、 目录  ​编辑 前言:

    2024年02月07日
    浏览(36)
  • 数据结构——二叉树的链式结构

      个人主页 : 日刷百题 系列专栏 : 〖C语言小游戏〗〖Linux〗〖数据结构〗  〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ 这里我们使用先序遍历的思想来创建二叉树,这里的内容对于刚接触二叉树的朋友可能有些难理解,不妨先看完下面的二叉树各种遍历

    2024年02月05日
    浏览(47)
  • 【数据结构】二叉树的链式结构

    学习链式二叉树要知道三种遍历方式,便于对二叉树的节点以及左子树和右子树进行操作。 前序遍历:根、左子树、右子树 中序遍历:左子树、根、右子树 后序遍历:左子树、右子树、根 以下图为例: 得到的结果: 前序遍历:1 2 3 4 5 6 中序遍历:3 2 1 5 4 6 后序遍历:3 2

    2024年02月08日
    浏览(57)
  • 数据结构:二叉树的链式结构

    朋友们、伙计们,我们又见面了,本期来给大家解读一下链式二叉树的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏 :数据结构与算法 个  人  主  页 :stackY、 C 语 言 专 栏 :C语言:从入门到精通 目录 前言

    2024年02月07日
    浏览(59)
  • 【数据结构】二叉树的介绍和二叉树堆

    💓作者简介: 加油,旭杏,目前大二,正在学习 C++ , 数据结构 等👀 💓作者主页:加油,旭杏的主页👀 ⏩本文收录在:再识C进阶的专栏👀 🚚代码仓库:旭日东升 1👀 🌹欢迎大家点赞 👍 收藏 ⭐ 加关注哦!💖        树这一概念,在我们刚开始听说的时候会觉得

    2024年01月20日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包