当前位置: 首页 > news >正文

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

 🌈个人主页:秦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

 

相关文章:

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

🌈个人主页:秦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…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...

docker详细操作--未完待续

docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...