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

 🌈个人主页:秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343
🔥 系列专栏:《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482

9efbcbc3d25747719da38c01b3fa9b4f.gif​​​

目录

二叉树遍历规则

前序遍历

中序遍历

 后序遍历

递归结构遍历

前序

中序

 求节点个数

求叶子节点个数

 求树的高度

求第k层节点个数


 

   前言

    💬 hello! 各位铁子们大家好哇。

             今日更新了树的遍历,递归的相关内容
    🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

 

 

二叉树遍历规则

 96d32642d8a84c4ebf74196ef008bbcd.png

前序遍历

b28f36f85639469fadbe096c03fa4a4a.png

注意:N代表空

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

中序遍历

09e83b933bc94d548cd26a671eeb44ba.png

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

 后序遍历

3c98f79128c14fff912af81648b28e2a.png

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

递归结构遍历

b2facb22c58d4d609ca6fbd66e6b99ed.png

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

前序

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

81509a0a105c4d41b89705dbb81b6c66.png

 下图是递归的流程图:

a26ea1dfd4b24b27a32db0fed03a5494.png

 

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

9c841bd49bbe46499c8ef0b2595e2a51.png

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

中序

9023cdf60a0346c488a9fa4c9b53e825.png

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

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

 求节点个数

d4b0a845cfef4a39a76d1a05a896f7b0.png

递归过程图如下:

bcfc8cac340642e287068a69d1d65328.png 

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

求叶子节点个数

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

 

 求树的高度

a3ea9e5f2dcc4eceb4845b07cc2f1106.png

求第k层节点个数

6d8b92852b064615ad96fd1eca9f8b2c.png 

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

我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=3cd3jqfe6fwg0

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/331509.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Pure-admin框架 Pure-table中获取所选中的内容的信息

最近在尝试使用Pure-admin框架来进行开发,正好遇到了多选表格需要获取选中项的id的情况,因为平台介绍说是二次封装 element-plus 的 Table ,直接拿el-table的方法来试 在table上设置属性ref"multipleTableRef" let idArr [];mult…

使用Python的pygame库实现下雪的效果

使用Python的pygame库实现下雪的效果 关于Python中pygame游戏模块的安装使用可见 https://blog.csdn.net/cnds123/article/details/119514520 先给出效果图: 源码如下: import pygame import random# 初始化pygame pygame.init()# 设置屏幕尺寸 width…

C# 线程间操作无效: 从不是创建控件的线程访问它--多线程操作

我们在用线程操作的时候,可能会出现异常:线程间操作无效: 从不是创建控件richTextBox1的线程访问它。因为windows窗体控件不是线程安全的,如果几个线程操作某一控件的状态,可能会使该控件的状态不一致,出现争用或死锁状…

springBoot项目打包发布

打包 项目代码编写完成后&#xff0c;在pom.xml文件中引用打包的插件&#xff1a; <!-- 打包插件坐标--><build><plugins><!--打包插件--><plugin><groupId>org.springframework.boot</groupId><artifactId>spring-boot-mave…

洗地吸拖一体机什么牌子好?性能超好的洗地机推荐

科技时代的快速发展带来了大量智能清洁家电&#xff0c;其中近年兴起的洗地机为我们的生活带来了极大便利。然而&#xff0c;市面上涌现出众多品牌和型号的洗地机&#xff0c;让人眼花缭乱&#xff0c;难以做出选择。笔者在这里推荐几款性能超好的洗地机推荐&#xff0c;希望能…

137基于matlab的面和线接触的滑块润滑

基于matlab的面和线接触的滑块润滑&#xff0c;基于有限差分法求解面接触滑块润滑的油膜厚度、油膜压力&#xff0c;输出三维可视化结果。程序已调通&#xff0c;可直接运行。 137 matlab油膜压力油膜厚度 (xiaohongshu.com)

在机关单位上班的你,需要掌握这些网络安全知识!

没有网络安全&#xff0c;就没有国家安全。网络安全和保密防护&#xff0c;是机关单位日常工作中不可忽视的重要问题。尤其在涉密单位工作的人员&#xff0c;因工作性质特殊&#xff0c;不仅要了解非涉密网络的安全操作常识&#xff0c;更要重点了解涉密网络的规范行为要点&…

linux docker-compose安装失败解决

1.去github下载到本地 https://github.com/docker/compose/releases/ 2.上传到linux 服务器 mv dokcer-compose-linux-x86_64 /usr/loacal/bin/docker-compose 3.给权限 chmod x /usr/local/bin/docker-compose 4.查看是否安装成功 docker-compose -version 5.卸载 …

鸿蒙原生应用/元服务实战-AGC团队账户

多人及内外结合去开发运营鸿蒙原生应用元服务时&#xff0c;需要用到团队账户&#xff0c;AGC提供了强大的团队角色与权限分工能力。 团队帐号是开发者联盟为实名开发者提供的多个成员帐号登录与权限管理服务。当前团队帐号支持成员参与应用市场&#xff08;付费推广、应用内付…

【Git相关问题】修改代码提交push时的用户名字

最简方法如下&#xff1a; 直接修改Git的用户配置文件 .gitconfig&#xff0c;这个配置文件的路径一般是 C:\Users\本机用户名\.gitconfig 用记事本或编辑器打开&#xff0c;在[user]下即可修改用户名name或邮箱email 参考&#xff1a; 使用Git进行版本控制&#xff0c;不同…

如何实现固定公网地址远程访问本地部署的Termux MySQL数据库

文章目录 前言1.安装MariaDB2.安装cpolar内网穿透工具3. 创建安全隧道映射mysql4. 公网远程连接5. 固定远程连接地址 前言 Android作为移动设备&#xff0c;尽管最初并非设计为服务器&#xff0c;但是随着技术的进步我们可以将Android配置为生产力工具&#xff0c;变成一个随身…

实验一 安装和使用Oracle数据库

&#x1f57a;作者&#xff1a; 主页 我的专栏C语言从0到1探秘C数据结构从0到1探秘Linux菜鸟刷题集 &#x1f618;欢迎关注&#xff1a;&#x1f44d;点赞&#x1f64c;收藏✍️留言 &#x1f3c7;码字不易&#xff0c;你的&#x1f44d;点赞&#x1f64c;收藏❤️关注对我真的…

(C语言)冒泡排序

一、运行结果&#xff1b; 二、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>//实现buble_sort函数&#xff1b; void buble_sort(int arr[], int sz) {//初始化变量值&#xff1b;int i 0;//嵌套循环冒泡排序&#xff1b;//外层循环&…

Mybatis面试题(一)

MyBatis 面试题 1、什么是 Mybatis&#xff1f; 1、Mybatis 是一个半 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;它内部封装了 JDBC&#xff0c;开发时只需要关注 SQL 语句本身&#xff0c;不需要花费精力去处理加载驱动、创建连接、创建statement 等繁杂的过程…

LeetCode 104. 二叉树的最大深度

104. 二叉树的最大深度 给定一个二叉树 root &#xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;3示例 2&#xff1a; 输入&#xff1…

Comdlg32.dll文件丢失怎么?Comdlg32.dll修复方法

很用人在打开软件或游戏的时候&#xff0c;电脑会弹出对话框“程序无法运行&#xff0c;因为Comdlg32.dll文件找不到&#xff0c;请尝试重新安装程序已解决问题”&#xff0c;这是怎么回事呢&#xff1f; 首先&#xff0c;我们先来了解“Comdlg32.dll文件”是什么&#xff1f; …

配置zabbix监控平台

目录 内容纯手敲&#xff0c;难免有误&#xff0c;若发现请私信我。 配置zabbix监控平台 一、进入官网 ​编辑​ 二、配置zabbix-server&#xff08;服务端&#xff09; 1.下载zabbix的yum源 2.安装Zabbix服务器、前端、代理 3.安装Zabbix前端 4.编辑文件/etc/yum.rep…

【vue】ant-col多列栅格式的表单排列方式布局异常:

文章目录 一、效果&#xff1a;二、解决&#xff1a;三、问题&#xff1a; 一、效果&#xff1a; 二、解决&#xff1a; 在row中添加布局类型&#xff1a;type“flex” 三、问题&#xff1a; 后期正式环境还是存在该问题 >>>.ant-form-item {max-height: 32px; }多…

【MATLAB基础绘图第19棒】绘制小提琴图

MATLAB绘制小提琴图 小提琴图&#xff08;Violin Plot&#xff09;案例1&#xff1a;基础绘制参考 小提琴图&#xff08;Violin Plot&#xff09; 小提琴图&#xff08;Violin Plot&#xff09;可用于展示多组数据的分布状态和概率密度。 出自论文-J2020-Drought hazard trans…

关系运算符

Oracle从入门到总裁:https://blog.csdn.net/weixin_67859959/article/details/135209645 补充: 如果要想对所选择的数据行进行控制&#xff0c;那么可以利用 WHERE 子句完成&#xff0c;此时的 SQL 语法结构变为如下形式 先系统性介绍下: ● 关系运算&#xff1a; >、、&…