【数据结构】二叉树(遍历,递归)
🌈个人主页:秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343
🔥 系列专栏:《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482
目录
二叉树遍历规则
前序遍历
中序遍历
后序遍历
递归结构遍历
前序
中序
求节点个数
求叶子节点个数
求树的高度
求第k层节点个数
前言
💬 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到上一层
我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=3cd3jqfe6fwg0
相关文章:

【数据结构】二叉树(遍历,递归)
🌈个人主页:秦jh__https://blog.csdn.net/qinjh_?spm1010.2135.3001.5343🔥 系列专栏:《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm1001.2014.3001.5482 目录 二叉树遍历规则 前序遍历 …...
《微信小程序开发从入门到实战》学习八十五
6.15 设备API 6.15.2 添加联系人API 使用wx.addPhoneContact接口可以在用户的手机通讯录中添加联系人信息。用户可以选择“新增联系人”或“添加到已有联系人”。该接口接受Object参数,参支持属性如下所示: firstName:必填,名字…...
设计模式——命令模式
命令模式(Command Pattern)是一种行为型设计模式,它将一个请求封装为一个对象,使发出请求的对象和执行请求的对象解耦。这样可以方便地对请求排队、记录日志、撤销/重做操作以及支持可扩展性。 原理 命令接口(Comman…...

Modbus协议学习第三篇之协议通信规则
导语 本篇博客将深入介绍Modbus协议的一些内容,主要包括通讯方式和通讯模型的介绍 Modbus通讯方式 Modbus协议是单主机、多从机的通信协议,即同一时间,总线上只能有一个主设备,但可以有一个或者多个从设备(最多好像是2…...

git仓库使用说明
Git软件使用 1.先下载git相关软件 下载地址: Git - Downloading Package (git-scm.com) 下载其中一个安装 2.打开gitee网站,注册账号 3.打开个人中心,选择ssh公钥,查看如何生成公钥 4.生成公钥后,添加相应的公钥 …...
边缘计算和联邦学习的联系
1. 什么是边缘计算? 边缘计算(Edge Computing)是一种计算模型,其主要思想是将计算、存储和数据处理能力推送到离数据源近的边缘设备,而不是依赖于远程的云服务器。这样做的目的是减少数据传输延迟、提高响应速度&…...
机器学习算法理论:贝叶斯
贝叶斯定理对于机器学习来说是经典的概率模型之一,它基于先验信息和数据观测来得到目标变量的后验分布。具体来说,条件概率(也称为后验概率)描述的是事件A在另一个事件B已经发生的条件下的发生概率,公式表示为P(A|B)&a…...
229.【2023年华为OD机试真题(C卷)】手机App防沉迷系统(模拟-JavaPythonC++JS实现)
🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(Java&Python&C++&JS分别实现),详细代码讲解,助你深入学习,深度掌握! 文章目录 一. 题目-手机App防沉迷系统二.解题思路三.题解代码Pyth…...

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

K8s-架构
一、K8s节点划分 K8s集群包含Master(控制节点)和Node(工作节点),应用部署在Node节点上。 集群架构图: 二、Master节点 Master节点分成四个组件:scheduler、ApiServer、Controller Manager、ETCD。类似三层结构,controller&#…...
C++ 并发编程 | 进程与线程
一、进程与线程 1、进程 1.1、定义 操作系统中最核心的概念就是进程,进程是对正在运行中的程序的一个抽象,是系统进行资源分配和调度的基本单位。进程是一种抽象的概念,一般由程序、数据集合和进程控制块三部分组成,如下&#x…...

基于Python实现身份证信息识别
目录 前言身份证信息识别的背景与意义自动识别身份证的需求实现环境与工具准备Python编程语言OpenCV图像处理库Tesseract OCR引擎身份证信息识别算法原理图像预处理步骤(图像裁剪、灰度化 、二值化、去噪)信息提取与解析Python代码实现通过OCR提取身份证号码代码解析身份证信息…...

深度学习记录--正则化(regularization)
什么是正则化? 正则化(regularization)是一种实用的减少方差(variance)的方法,也即避免过度拟合 几种正则化的方法 L2正则化 又被称为权重衰减(weight dacay) 在成本函数中加上正则项: 其中 由于在w的更新过程中会递减,即权…...

Java的便捷输入方法及解析
在 Java 中,有多种便捷的输入方法可以从用户那里获取输入。下面是一些常见的便捷输入方法及解析: 使用 Scanner 类:在上述示例中,首先导入了 java.util.Scanner 类,创建了一个 Scanner 对象,并使用 System…...

抖音矩阵云混剪系统源码(免授权版)多平台多账号一站式管理,附带系统搭建教程
搭建教程 MySQL 5.6 PHP 7.2 Apache 数据库名称 juzhen Nginx环境切换伪静态 1、解压安装包到项目根目录,找到application/database.php 更换自己的数据库密码 2、阿里云现有的配置不要动 其他按照文档进行添加 3、项目访问目录:public 4、域名…...

【Linux】权限的深度解析
前言:在此之前我们学习了一些常用的Linux指令,今天我们进一步学习Linux下权限的一些概念 💖 博主CSDN主页:卫卫卫的个人主页 💞 👉 专栏分类:Linux的学习 👈 💯代码仓库:卫卫周大胖的学习日记&a…...
c++函数怎么返回多个值
文章目录 使用结构体或类:定义一个结构体或类,其中包含了所有需要返回的值。然后在函数中返回这个结构体或类的实例。 struct Result {int value1;double value2;char value3; };Result myFunction() {Result r;r.value1 1;r.value2 2.0;r.value3 a;r…...
《剑指 Offer》专项突破版 - 面试题 15 : 字符串中的所有变位词(C++ 实现)
题目链接:LCR 015. 找到字符串中所有字母异位词 - 力扣(LeetCode) 题目: 输入字符串 s1 和 s2,如何找出字符串 s2 的所有变位词在字符串 s1 中的起始下标?假设两个字符串中只包含英文小写字母。例如&…...
03 SpringMVC响应数据之接收Cookie和请求头+原生API+共享域对象操作
下载postman,测试传json数据 1. 接收cookie 用CookieValue注解将cookie值绑定到控制器中的handler参数。 Controller类中的一个handler GetMapping("/CookieTest") public void handle(CookieValue("cookie的id(name)") String cookie) { //... }2. 接收…...

数据仓库(3)-模型建设
本文从以下9个内容,介绍数据参考模型建设相关内容。 1、OLTP VS OLAP OLTP:全称OnLine Transaction Processing,中文名联机事务处理系统,主要是执行基本日常的事务处理,比如数据库记录的增删查改,例如mysql、oracle…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...

【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...

遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...

Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
用鸿蒙HarmonyOS5实现中国象棋小游戏的过程
下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...
MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释
以Module Federation 插件详为例,Webpack.config.js它可能的配置和含义如下: 前言 Module Federation 的Webpack.config.js核心配置包括: name filename(定义应用标识) remotes(引用远程模块࿰…...
规则与人性的天平——由高考迟到事件引发的思考
当那位身着校服的考生在考场关闭1分钟后狂奔而至,他涨红的脸上写满绝望。铁门内秒针划过的弧度,成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定",构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...