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

数据结构与算法[零基础]---4.树和二叉树

news 来源：原创 2025/8/22 18:13:34

四、树和二叉树

（一）树

1.相关定义

树是由一个或多个结点组成的有限集T，它满足以下两个条件：第一个是有一个特定的结点，作为根结点；第二个其余的结点分成m(m>=0)个互不相交的有限集T0，T1,...,Tn-1。其中每个集合又都是一棵树，称T0,T0，T1,...,Tn-1为根结点的子树
- 树中各结点的度的最大值则称为树的度。树中结点的最大层次称为树的深度。

2.存储结构

（1）标准存储结构：

树的结点内容分为两部分，分别为结点的数据和指向子结点的指针数组。对于N度数，在标准存储结构中指针数组有N个元素。

（2）带逆存储结构：

当程序需从结点返回到其父结点时，在标准存储结构基础上增加一个指向父结点的指针，这种存储形式就是带逆存储结构

3.使用的链表结构

(1)双亲表示法：

利用每个结点只有一个双亲的特点；求结点的孩子时要遍历整个向量

（2）孩子表示法：

把每个结点的孩子都排成一个线性表，用链表储存起来，则n个结点有n个孩子链表，而n个头指针又组成了一个线性表

（3）孩子兄弟表示法：

孩子兄弟表示法(又称二叉树表示法，或二叉链表表示法)：结点中的孩子指针域和兄弟指针域分别指向该结点的第一个孩子和下一个兄弟结点

4.树的遍历

在应用树结构时，常要求按某种次序获得树中全部结点的信息，这种方法的实现叫做树的遍历

（1）树的先序遍历：

首先访问根结点，然后从左到右遍历根结点的各子树（根-->左-->右）

（2）树的后序遍历：

首先从左到右按后序遍历根结点的各子树，然后访问根结点（左-->右-->根）

(3)树的层次遍历：

首先访问处于0层上的根结点，然后从左到右依次访问处于1层、2层上的结点，即自上而下从左到右逐层访问树各层上的结点（上-->下，每层从左-->右）

（二）二叉树

1.相关定义

二叉树是一种特殊的树形结构，其结点是第一每次结点至多只有二颗子树；二叉树的子树有左右之分，其次序不能任意颠倒

2.二叉树的性质

(1)在二叉树的第i层至多2ⁱ⁻²个结点（i>=1）
(2)深度为k的二叉树至多有2ᵏ-1个结点(k>=1)
(3)对任何一颗二叉树，如果其终端结点数为n0，度为2的结点数为n2,则n0=n2+1
(4)具有n个结点的完全二叉树的深度为㏒2n+1

3.二叉树的遍历

(1)先序遍历：

访问根结点；访问根结点的左子树；访问根结点的右子树（根-->左-->右）

（2）中序遍历：

访问根结点的左子树；访问根结点；访问根结点的右子树（左-->根-->右）

（3）后序遍历：

访问根结点的左子树；访问根结点的右子树；访问根结点（左-->右-->根）

（三）真题实例

二叉树的中序遍历是左-->根-->右，所以是DBGF（左子树），根结点A，GICH（右子树），选B

二叉树的中序遍历是左-->根-->右，所以排除A和D选项，A根节点开始遍历肯定错，H在右子树所以也是错的；然后看一下C选项，A结点根结点在最后肯定是错的；所以选B
二叉树的后序遍历是左-->右-->根，我们只要看到根节点A在最后就是答案，选择C
总结：二叉树也是一个重点！！！上面的例题是教资历年的真题，二叉树的遍历在计算机等级证书也是都会考的。所以，一定要背熟先序、中序、后序的遍历方式，具体怎么记，后序就是根结点最后遍历（先按顺序遍历左，右）；先序就是根结点最先遍历（在按顺序遍历左，右）；然后中序就是左，根，右。下一篇文章我会介绍图，也是一个常考点，如果你喜欢这篇文章有帮助到你，不要忘记你的点赞跟关注噢！！

数据结构与算法[零基础]---4.树和二叉树

四、树和二叉树 （一）树 1.相关定义树是由一个或多个结点组成的有限集T，它满足以下两个条件：第一个是有一个特定的结点，作为根结点；第二个其余的结点分成m(m>0)个互不相交的有限集T0，T1,.…...

编程日记 2025/8/22 18:13:34

Sklearn入门之数据预处理preprocessing

、 Sklearn全称:Scipy-toolkit Learn是一个基于scipy实现的的开源机器学习库。它提供了大量的算法和工具，用于数据挖掘和数据分析，包括分类、回归、聚类等多种任务。本文我将带你了解并入门Sklearn下的preprocessing在机器学习中的基本用法。获取方式…...

编程日记 2025/8/22 13:33:49

4.16学习总结 IO流综合练习

爬虫获取网站内的数据，获得完整姓名网站一：姓氏网站二：男生名字网站三：女生名字进行拼接，获取完整的男生女生姓名。 //导包 import org.apache.commons.io.FileUtils; import java.io.*; import java.io.IOEx…...

编程日记 2025/8/17 20:37:42

大模型全景解析：从技术突破到行业变革

目录一、引言：人工智能的新纪元二、大模型发展历史与技术演进 1. 早期探索期（2015-2017）：从"人工智障"到初具规模 RNN/LSTM架构时代（2013-2017） Transformer革命（2017&#xf…...

编程日记 2025/8/20 17:24:18

充电宝项目中的MQTT（轻量高效的物联网通信协议）

文章目录补充：HTTP协议MQTT协议MQTT的核心特性MQTT vs HTTP：关键对比 EMQX项目集成EMQX集成配置客户端和回调方法具体接口和方法处理处理类补充：HTTP协议 HTTP是一种应用层协议，使用TCP作为传输层协议，默认端口是80…...

编程日记 2025/8/20 9:05:01

AgentOps - 帮助开发者构建、评估和监控 AI Agent

文章目录一、关于 AgentOps二、关键集成 🔌三、快速开始 ⌨️2行代码中的Session replays 首类开发者体验四、集成 🦾OpenAI Agents SDK 🖇️CrewAI 🛶AG2 🤖Camel AI 🐪Langchain 🦜&#x1…...

编程日记 2025/8/19 17:02:46

n8n 为技术团队打造的安全工作流自动化平台

AI MCP 系列 AgentGPT-01-入门介绍 Browser-use 是连接你的AI代理与浏览器的最简单方式 AI MCP(大模型上下文)-01-入门介绍 AI MCP(大模型上下文)-02-awesome-mcp-servers 精选的 MCP 服务器 AI MCP(大模型上下文)-03-open webui 介绍是一个可扩展、功能丰富且用户友好的…...

编程日记 2025/8/18 2:45:47

MyBatis：SpringBoot结合MyBatis、MyBatis插件机制的原理分析与实战

🪁🍁 希望本文能给您带来帮助，如果有任何问题，欢迎批评指正！🐅🐾🍁🐥 文章目录一、背景二、Spring Boot项目中结合MyBatis2.1 数据准备2.2 pom.xml依赖增加2.3 applicat…...

编程日记 2025/8/21 8:09:37

【数据结构】3.单链表专题

文章目录单链表的实现0、准备工作1、链表的打印2、尾插3、头插4、尾删5、头删6、查找指定数据的位置7、在指定位置之前插入数据8、在指定位置之后插入数据9、删除指定位置的数据10、删除指定位置之后的数据11、单链表的销毁单链表的实现什么是单链表呢？单链表可…...

编程日记 2025/8/17 21:15:41

Microsoft Certified Professional（MCP）认证考试

1. MCP 认证考试概述 MCP（Microsoft Certified Professional）是微软认证体系中的一项入门级认证，旨在验证考生在微软产品和技术（如 Windows Server、Azure、SQL Server、Microsoft 365）方面的技能。2020 年&#xff0…...

编程日记 2025/8/17 5:28:34

C++学习之游戏服务器开发git命令

目录 1.服务器需求分析 2.面向框架编程简介 3.ZINX框架初始 4.回显标准输入 5.VS结合GIT 6.完善readme范例 7.添加退出功能 8.添加命令处理类 9.添加日期前缀思路 10.添加日期前缀功能 1.服务器需求分析 zinx 描述 zinx 框架是一个处理多路 IO 的框架。在这个框架中提…...

编程日记 2025/8/20 16:36:54

Maven 多仓库与镜像配置全攻略：从原理到企业级实践

Maven 多仓库与镜像配置全攻略：从原理到企业级实践一、核心概念：Repository 与 Mirror 的本质差异在 Maven 依赖管理体系中，repository与mirror是构建可靠依赖解析链的两大核心组件，其核心区别如下： 1. Repositor…...

编程日记 2025/8/17 20:50:17

无锁队列--知识分享

目录无锁队列无锁队列是什么为什么需要无锁队列队列的类型无锁队列的分类 ringbuffer（SPSC） ret_ring（MPMC） 无锁队列无锁队列是什么无锁队列通过原子操作来实现线程安全的队列，属于非阻塞队列 …...

编程日记 2025/8/20 3:52:39

Flask快速入门

1.安装 Flask 要使用 Flask，你需要先安装它。打开终端，运行以下命令： pip install flask 2.创建文件结构 3.app.py from flask import Flask：从 flask 库中导入 Flask 类。app Flask(__name__)：创建一个 Flask 应…...

编程日记 2025/8/21 7:47:48

LeetCode -- Flora -- edit 2025-04-16

1.两数之和 1. 两数之和给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按…...

编程日记 2025/8/21 5:15:33

【Unity笔记】实现可视化配置的Unity按键输入管理器（按下/长按/松开事件 + UnityEvent绑定）

【Unity笔记】实现可视化配置的Unity按键输入管理器适用于角色控制、技能触发的Unity按键输入系统，支持UnityEvent事件绑定、长按/松开监听与启用开关一、引言在 Unity 游戏开发中，处理键盘输入是最常见的交互方式之一。尤其是角色控制、技能释放、菜…...

编程日记 2025/8/20 1:18:03

SpringMVC学习（请求与响应。常见参数类型接收与响应。@RequestParam、@RequestBody的使用）(详细示例)

目录一、请求与响应。(RequestMapping) （1）使用注解RequestMapping对业务模块区分。 StudentController。 TeacherController。 （2）Apifox请求与响应。 "/student/login"。 "/teacher/login"。二、常见参数…...

编程日记 2025/8/19 15:06:22

springboot 切面拦截自定义注解

使用切面来拦截被该注解标记的方法依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-aop</artifactId> </dependency>1. 定义自定义注解 import java.lang.annotation.ElementType; imp…...

编程日记 2025/8/17 20:55:19

QT —— 信号和槽（自定义信号和槽函数）

QT —— 信号和槽（自定义信号和槽函数） 自定义信号和槽函数一、自定义信号函数规范1. 声明位置2. 返回值与实现3. 参数与重载二、自定义槽函数规范1. 声明位置（不同版本差异）2. 返回值与实现3. 参数与重载三、信号发射规范1. 基…...

编程日记 2025/8/17 19:07:30

朋克编码以潮玩语言讲述中国文化｜益民艺术馆展演东方潮力

朋克编码于广州益民艺术馆推出“艺术家潮玩”系列主题展，将传统文化元素融入潮玩设计，并通过数字科技与空间场景创新，讲述中国故事、传递东方美学。展览作品结合太空猿等原创 IP 与“中式元素”视觉符号，引发观众情感共鸣。“我…...

编程日记 2025/8/20 18:37:13

TA学习之路——2.2 模型与材质基础

1.模型基础 1.1 图形渲染管线 1.2 模型实现的原理点连成线，线构成面，面构成模型。 1.2 UV UV例如一个正方体的纸盒展开，平铺在一个二维的坐标系中。模型的每一个顶点在三维空间和二维空间中都能一一对应。在二维坐标系中的顶点对应的位置就是顶点的纹理坐标。因此…...

编程日记 2025/8/20 16:43:37

helm的go模板语法学习

1、helm chart 1.0、什么是helm？ 介绍：就是个包管理器。理解为java的maven、linux的yum就好。安装方法也可参见官网： https://helm.sh/docs/intro/install 通过前面的演示我们知道，有了helm之后应用的安装、升级、查看、停止都…...

编程日记 2025/8/19 11:46:29

Windows 图形显示驱动开发-WDDM 1.2功能—Windows 8 中的 DirectX 功能改进（一）

Windows 8包括 Microsoft DirectX 功能改进，使开发人员、最终用户和系统制造商受益。功能改进在以下几个方面： 像素格式 (5551、565、4444) ：在低功耗硬件配置下，DirectX 应用程序的性能更高。双精度着色器功能：高级…...

编程日记 2025/8/17 11:29:09

软件测试|App测试面试相关问题（2）

一、App 稳定怎么做的?Monkey 怎么用(App 稳定测试)? 稳定性这块，我们当时用的是SDK 自动的一个Monkey 工具进行测试的，其实Monkey工具主要通过模拟用户发送伪随机时间去操作软件，通过执行Monkey 命令，它会自动出报告&#xff…...

编程日记 2025/8/21 12:19:46

模拟电路需要了解的一些基础知识（部分）

基本的单路元件 1. 电阻；特性：阻碍电流流动，消耗电能并转化为热能（遵循欧姆定律）。是无源元件，应用：限流、分压、发热等； 2. 电容；特性：存储电荷和电场能&am…...

编程日记 2025/8/18 21:56:43

[特殊字符] MySQL MCP 开发实战：打造智能数据库操作助手

💡 简介：本文详细介绍如何利用MCP（Model-Control-Panel）框架开发MySQL数据库操作工具，使AI助手能够直接执行数据库操作。 📚 目录引言MCP框架简介项目架构设计开发环境搭建核心代码实现错误处理策略运行和…...

编程日记 2025/8/21 14:49:07

软考备考（一）学习笔记

一、软考介绍计算机软考，计算机技术与软件专业技术资格（水平）考试一年考试两次：一次上旬（5月底），下旬一次（11月初）初级资格：程序员中级资格：软件设计师高级资格：系统架构设计师初级：科目一：计算机硬软件基础知识 150min 笔试、选择科目二：程序设…...

编程日记 2025/8/19 22:46:42

Linux环境变量

目录环境变量基本概念常见环境变量查看环境变量方法测试PATH 测试HOME 和环境变量相关的命令环境变量的组织方式通过代码如何获取环境变量通过系统调用获取或设置环境变量编辑环境变量通常是具有全局属性的实验环境变量基本概念环境变量(environment variables…...

编程日记 2025/8/22 2:22:05

跨浏览器书签同步方案：WebDAV + Floccus插件实操指南

FloccusWebDAV能够帮助把多个不同浏览器书签统一私有化管理，以下是介绍： Floccus 是一个允许用户在不同浏览器和设备之间私密同步书签的扩展，开源地址：https://github.com/floccusaddon/floccusWebDAV是一种基于HTTP的协议&#…...

编程日记 2025/8/18 23:50:52

适配的一套环境为 dmPython2.5.8 dmSQLAlchemy1.4.39 Flask2.0.3 Flask-Cors3.0.10 Flask-SQLAlchemy2.5.1 SQLAlchemy1.4.54 Werkzeug2.2.2其中 # sqlalchemy-dm1.4.39 通过dmdbms目录内文件进行源码安装 (MindSpore) [ma-user python]$pwd /home/syl/dmdbms/drivers/python…...

编程日记 2025/8/19 19:44:28

代码随想录算法训练营Day31

力扣738.单调递增的数字【medium】力扣968.监控二叉树【hard】一、力扣738.单调递增的数字【medium】题目链接：力扣738.单调递增的数字视频链接：代码随想录 1、思路先将整数转为字符串变成可迭代对象，再转为列表从后向前遍历&#xff…...

编程日记 2025/8/22 8:00:43

LeetCode Hot100 刷题笔记（10）—— ACM格式输入输出练习

目录 Trick: 1. 只有输出 2. 单组_AB 3. 多组_AB_EOF形式 4. 多组_AB_T组形式 5. 多组_AB_零尾形式 6. 单组_一维数组 7. 多组_二维数组_T组形式 8. 单组_二维数组 9. 多组_二维数组_T组形式 10. 单组_字符串 11. 多组_字符串_T组形式 12. 单组_二维字符数组 13. 多组_带空格的…...

编程日记 2025/8/22 1:20:01

iPaaS集成平台在制造业有哪些应用场景

在制造业迈向智能化的进程中，“数据不通”“系统割裂”“响应迟缓”等问题如同隐形的锁链，束缚着企业转型升级的步伐。面对设备、系统、供应链之间错综复杂的连接需求，传统定制化开发周期长、成本高，难以满足快速变化的业务需求。…...

编程日记 2025/8/20 23:38:43

【Docker项目实战】使用Docker部署Gitblit服务器

【Docker项目实战】使用Docker部署Gitblit服务器一、Gitblit介绍1.1 Gitblit 介绍1.2 主要特点二、本次实践规划2.1 本地环境规划2.2 本次实践介绍三、本地环境检查3.1 检查Docker服务状态3.2 检查Docker版本3.3 检查docker compose 版本四、下载Gitblit镜像五、部署Gitbli…...

编程日记 2025/8/18 23:02:14

基于瑞芯微RK3562 四核 ARM Cortex-A53 + 单核 ARM Cortex-M0——Linux应用开发手册

前言本文主要介绍TL3562-MiniEVM评估板的AMP(Asymmetric Multi-processing)开发案例，适用开发环境如下： Windows开发环境：Windows 7 64bit、Windows 10 64bit Linux开发环境：VMware16.2.5、Ubuntu20.04.6 64bit U-Boot：U-Boot-2017.09 Kernel：Linux-5.10.209 Lin…...

编程日记 2025/8/20 21:40:41

并查集（力扣1971）

并查集的功能：判断两个节点是否在同一个集合中/将两个节点加入同一集合中。模板如下： #include<iostream> #include<vector> using namespace std; const int n 1e6 5;//视题目具体节点数量而定，比节点数量稍大即可 vector<…...

编程日记 2025/8/19 17:04:41

Pinpoint - 大型分布式系统的 APM（应用性能管理）工具

文章目录一、关于 Pinpoint最新版本（2024/10/23）-- v3.0.1PHP, PYTHON 二、概述支持的模块一、关于 Pinpoint Pinpoint 是一个用于大型分布式系统的 APM（应用性能管理）工具，由 Java / PHP/PYTHON 编写。受 Dapper …...

编程日记 2025/8/17 19:49:33

高级java每日一道面试题-2025年4月10日-微服务篇[Nacos篇]-Nacos的服务健康检查机制是如何工作的？

如果有遗漏,评论区告诉我进行补充面试官: Nacos的服务健康检查机制是如何工作的？ 我回答: Nacos 服务健康检查机制详解 Nacos 的服务健康检查机制是确保服务高可用性和可靠性的核心功能之一。它通过定期检测服务实例的状态来判断它们是否健康，并据此…...

编程日记 2025/8/17 1:56:24

JavaScript:表单及正则表达式验证

今天我要介绍的是在JavaScript中关于表单验证内容的知识点介绍： 关于表单验证，我接下来则直接将内容以及效果显示出来并作注解，这样可以清晰看见这个表达验证的妙用： <form id"ff" action"https://www.baidu.…...

编程日记 2025/8/17 1:45:24

Android 应用数据分布目录结构解析

在Android系统中，/data目录下的几个关键路径有不同的用途，主要涉及应用数据存储和用户媒体文件管理,具体如下： 1. /data/user/0/ 路径别名：等同于 /data/data/（旧路径，仍兼容）。用途&#xff…...

编程日记 2025/8/17 20:34:49

Spring Boot 中的自动配置原理

2025/4/6 向全栈工程师迈进！ 一、自动配置所谓的自动配置原理就是遵循约定大约配置的原则，在boot工程程序启动后，起步依赖中的一些bean对象会自动的注入到IOC容器中。在讲解Spring Boot 中bean对象的管理的时候，我们注入bean对…...

编程日记 2025/8/20 1:35:05

Java内部类详解

在Java中，内部类是一种强大的特性，允许将一个类定义在另一个类的内部。内部类提供了更好的封装性，能够访问外部类的成员，并常用于实现事件监听、适配器模式等场景。本文将深入探讨四种内部类：成员内部类、静态内部类、…...

编程日记 2025/8/17 20:09:59

台账自动统计——餐饮物资管理台账——仙盟共创平台——未来之窗

分类表自动统计创作不易，使用地址：https://mp.weixin.qq.com/s/Ok3wuSYAPhd-6N8DrK7jwg 餐饮物资管理台账自动统计能够实时、精准地呈现库存数量。通过对采购入库、领用出库、盘点盈亏等数据的自动记录与计算，管理者随时可获取准确库存信息…...

编程日记 2025/8/20 1:18:05

Function Calling是什么？

Function Calling（函数调用）是大型语言模型（如GPT、Claude等）中的一项关键功能，允许模型根据用户输入的需求，智能识别并返回结构化函数调用请求，从而与外部工具、API或代码进行交互。以下是详细…...

编程日记 2025/8/22 1:09:38

[学习] C语言数据结构深度解析：八种树结构与应用场景详解（代码示例）

C语言数据结构深度解析：八种树结构与应用场景详解好吧，今天我们来研究树！C语言中的树。树是计算机科学中最重要的非线性数据结构之一，广泛应用于操作系统、数据库、编译器、图形学等领域。本文将通过C语言代码示例&#xff0c…...

编程日记 2025/8/17 19:57:49

【从零实现高并发内存池】Page Cache 从理解设计到全面实现

📢博客主页：https://blog.csdn.net/2301_779549673 📢博客仓库：https://gitee.com/JohnKingW/linux_test/tree/master/lesson 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！ &…...

编程日记 2025/8/20 22:28:54

6 CMD 与 PowerShell 指令大全、C 程序终端运行、字符编码切换指南

1 CMD 与 PowerShell 常用指令在命令行环境中高效运行程序，掌握终端的基本操作命令至关重要。无论是 Windows 系统下的 CMD（命令提示符）还是 PowerShell，它们都配备了一系列实用的命令，助力我们管理文件、执行程序以及…...

编程日记 2025/8/22 4:20:07

为啥mac日历打不开浏览器

问题换了新电脑后，mac上的日历总是没法同步google日历信息，导致经常错过会议尝试mac日历上添加账户，结果到了打开浏览器缓解总是卡住，打不开浏览器（safari） 解决检查默认浏览器设置确保已将所需的浏览…...

编程日记 2025/8/16 19:05:39

spring：注解@PostConstruct、@PreDestroy

这两个注解的功能类似标签中的init-method和destroy-method。分别在构造方法调用之后和实例释放资源之前被调用。注解类： package com.annotation.dao.impl;import org.springframework.context.annotation.Lazy; import org.springframework.context.annotation…...

编程日记 2025/8/20 9:55:22

Androidjetpack之viewmodel的原理分析

前言 viewmodel是jetpack中比较重要的一个组件。如果还没有学习viewmodel不知道怎么写代码什么的，可以看一下我之前写得文章。 jetpack之ViewModel的简单使用https://blog.csdn.net/i_xiang_la_shi/article/details/147218033?fromshareblogdetail&sharetype…...

编程日记 2025/8/21 6:44:07

四、树和二叉树

（一）树

1.相关定义

2.存储结构

（1）标准存储结构：

（2）带逆存储结构：

3.使用的链表结构

(1)双亲表示法：

（2）孩子表示法：

（3）孩子兄弟表示法：

4.树的遍历

（1）树的先序遍历：

（2）树的后序遍历：

(3)树的层次遍历：

（二）二叉树

1.相关定义

2.二叉树的性质

3.二叉树的遍历

(1)先序遍历：

（2）中序遍历：

（3）后序遍历：

（三）真题实例

相关文章：