Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【数据结构】二叉树(遍历,递归)

【数据结构】二叉树(遍历,递归)

作者头像
秦jh
发布于 2024-01-19 02:48:44
发布于 2024-01-19 02:48:44
1450
举报
文章被收录于专栏:c语言,c++c语言,c++

前言

💬 hello! 各位铁子们大家好哇。 今日更新了树的遍历,递归的相关内容 🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

二叉树遍历规则

前序遍历

​ 注意:N代表空 分析:根据前序遍历的规则(根左右),先访问根1,然后左子树2,2的左子树3,3的左子树是N,右子树也是N,然后返回到2的右子树N,然后返回到1的右子树4,接着是4的左子树5,5的左右子树都是N,然后返回到4的右子树6,6的左右子树都是N。

中序遍历

分析:根据规则(左根右),1的左子树2,2的左子树3,3的左子树N,起始即为N,接着是根3,接着是3的右子树N,返回到根2,然后是2的右子树N,返回到根1,接着是1的右子树,以此类推。

后序遍历

分析:过程变为左右根,其实质与前面两种一样。

递归结构遍历

上图是要遍历的树的模型。

前序

假设树已构建好,下图是前序遍历的函数,执行后即可得到前序遍历的结果。

下图是递归的流程图:

分析:开始先打印根1,然后递归调用根2,以此类推到3的左子树N。此时左子树遍历完,返回到3的右子树,每次调用完就返回到上一层的函数中。

上图是递归调用占用的大致空间,每次调用完函数,返回到上一层,上一层接着调用,就会重复利用之前销毁的空间,如果空间不足,能用多少是多少。因此,递归的空间复杂度是看递归的深度。

中序

上图是中序遍历的函数,递归过程参考前序遍历过程。

后序遍历大致过程也同上,这里就不再写出。

求节点个数

递归过程图如下:

分析:如果根结点为空,则返回0。此递归过程会先找出左子树的节点个数,当遇到空节点时就返回0,然后加上根结点自身数量1,返回到上一层,以此类推。

求叶子节点个数

参考前面的递归过程理解。

求树的高度

求第k层节点个数

分析:k-1目的是当到达第k层后,直接返回1到上一层

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-01-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
数据结构(三):二叉树遍历
前序遍历的方式,也就是对每一棵子树,按照根节点、左子树、右子树的顺序进行访问,也就是根-左-右的访问顺序。因为每一棵非空子树,又可拆分为根节点、左子树和右子树,所以可以按照根-左-右的方式,递归访问每棵子树。
zhipingChen
2018/09/13
7050
数据结构(三):二叉树遍历
数据结构初阶 · 链式二叉树的部分问题
链式二叉树我们在C语言阶段已经实现了,这里介绍的是涉及到的部分问题,比如求树的高度,求树的节点个数等,连接部分就手动连接,用一个样例来介绍涉及到的几个问题。
_lazy
2024/10/16
850
数据结构初阶 · 链式二叉树的部分问题
【数据结构】二叉树链式结构的实现
学习二叉树结构,最简单的方式就是遍历。所谓 二叉树遍历 (Traversal) 是按照某种特定的规则,依次对二叉 树中的结点进行相应的操作,并且每个结点只操作一次 。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础
用户11290673
2024/09/25
1310
【数据结构】二叉树链式结构的实现
【数据结构】二叉树的前中后序遍历以及层序遍历(全解)
在前面学习完链式结构的二叉树之后,我们就可以进一步了解二叉树的几种遍历方式了,注意这里就可以深刻的体会到递归的思想了。
Crossoads
2024/10/21
5700
【数据结构】二叉树的前中后序遍历以及层序遍历(全解)
数据结构-二叉树(2)
先使用向下调整的方式建一个大堆,然后再写一个循环,当end=0时结束循环,每次进入循环先交换首尾数据,然后从头开始进行向下调整,每次end--。
用户10923087
2024/01/23
1370
数据结构-二叉树(2)
【数据结构】二叉树
二叉树链式结构的简单实现: 此处为了快速创建一棵二叉树,只是简单创建每一个节点然后把它们连接起来;
YoungMLet
2024/03/01
1350
【数据结构】二叉树
【数据结构】二叉树篇
在学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习相关的基本操作,由于现在大家可能堆二叉树结构掌握还不够深入,为了降低大家的学习成本,本文会手动创建一颗简单的二叉树,目的快速进入二叉树的操作学习。后续可能就要在C++篇章详讲二叉树了。
Yui_
2024/10/16
1070
【数据结构】二叉树篇
数据结构【链试结构二叉树】
🌟摘要:设⼆叉树的根结点所在层数 为1,层序遍历就是从所在⼆叉树的根结点出发,⾸先访问第⼀层的树根结点,然后从左到右访问第2 层上的结点,接着是第三层的结点,以此类推,⾃上⽽下,⾃左⾄右逐层访问树的结点的过程就是层 序遍历。根结点的左⼦树和右⼦树分别⼜是由⼦树结点、⼦树结点的左⼦树、⼦树结点的右⼦树组成的,因此 ⼆叉树定义是递归式的,后序链式⼆叉树的操作中基本都是按照该概念实现的。回顾⼆叉树的概念,⼆叉树分为空树和⾮空⼆叉树,⾮空⼆叉树由根结点、根结点的左⼦树、根结点 的右⼦树组成的。根结点、左⼦树、右⼦树。
逆向-落叶
2024/10/28
1480
数据结构【链试结构二叉树】
【C语言视角】数据结构之~二叉树
前言:总所周知~数据结构的二叉树对于初学者来说是一个十分难理解的知识点。接下来,请阅读本人对二叉树拙劣的理解~
小文要打代码
2024/10/16
2100
【C语言视角】数据结构之~二叉树
数据结构——遍历二叉树
二叉树的遍历:是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。
蜻蜓队长
2018/08/03
4950
数据结构——遍历二叉树
【数据结构】关于二叉树,你必须知道的遍历方法!!!
1. 在计算机编程中,对数组进行遍历是常见操作。例如用循环语句依次访问数组中的每一个元素,以便进行数据处理、统计等操作。比如计算一个整数数组中所有元素的和,就需要遍历这个数组,将每个元素的值依次相加。
用户11288949
2024/09/24
2110
【数据结构】关于二叉树,你必须知道的遍历方法!!!
数据结构与算法二叉树的算法_数据结构c语言二叉树的深度
树的结构类似现实中的树,一个父节点有若干子节点,而一个子节点又有若干子节点,以此类推。
全栈程序员站长
2022/09/23
3860
数据结构与算法二叉树的算法_数据结构c语言二叉树的深度
【数据结构】关于树(二叉树)的基础理论知识,你知道吗???
树是一种非线性 的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。 把
用户11288949
2024/09/24
1470
【数据结构】关于树(二叉树)的基础理论知识,你知道吗???
【数据结构与算法】详解二叉树下:实践篇————通过链式结构深入理解并实现二叉树
在计算机科学中,二叉树是一种重要的数据结构,它以其独特的结构和性质在数据存储、搜索和算法设计中发挥着重要作用。链式结构作为二叉树的一种常见表示方式,通过节点间的指针连接,实现了对二叉树的高效存储和访问。
倔强的石头_
2024/12/06
2890
【数据结构与算法】详解二叉树下:实践篇————通过链式结构深入理解并实现二叉树
[数据结构]——二叉树链式结构的实现
在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,为了降低大家学习成本,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研究二叉树真正的创建方式。
小李很执着
2024/06/15
1200
[数据结构]——二叉树链式结构的实现
【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)
在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,且为了方便后面的介绍,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研究二叉树真正的创建方式。 基于二叉树的链式结构,于是可以先malloc动态开辟出二叉树的每个节点并初始化,然后通过节点中的指针struct BinaryTreeNode* left(指向左树)和struct BinaryTreeNode* right(指向右树),将各个节点连接起来,最后大致模拟出了一棵二叉树,代码如下:
用户11029269
2024/03/19
1270
【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)
前端学数据结构与算法(六):二叉树的四种遍历方式及其应用
上一章我们从0到1的实现了一颗二叉搜索树,以及理解了二叉搜索树的特性与基本操作,这一章介绍关于二叉树的更多操作,也就是树的遍历。主要包括前序遍历、中序遍历、后序遍历、层序遍历,前面三种也叫深度优先遍历(DFS),最后的层序遍历也叫广度优先遍历(BFS),理解这四种遍历方式的不同,再遇到树相关的算法问题时,也就能更加游刃有余。这里不单指二叉搜索树,遍历思想同样适用于多叉树。
飞跃疯人院
2020/10/07
1.5K0
数据结构与算法:链式二叉树
在前序遍历中,我们首先访问根节点,然后是左子树,最后是右子树。 对于上述树的前序遍历,遍历顺序将是:
用户11029103
2024/03/19
1670
数据结构与算法:链式二叉树
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
层序遍历: 除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。 可以参考下图:
用户11029269
2024/03/19
1760
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
递归算法:二叉树前序、中序、后序遍历解析与递归思想深度剖析
🎬 鸽芷咕:个人主页 🔥 个人专栏: 《linux深造日志》 《高效算法》
鸽芷咕
2023/12/25
1.6K0
递归算法:二叉树前序、中序、后序遍历解析与递归思想深度剖析
推荐阅读
相关推荐
数据结构(三):二叉树遍历
更多 >
领券
一站式MCP教程库,解锁AI应用新玩法
涵盖代码开发、场景应用、自动测试全流程,助你从零构建专属AI助手
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档