考研数据结构之二叉树(一)(包含真题及解析)
考研数据结构之二叉树(一)
下期预告:后续文章将深入探讨二叉树的遍历算法与高频考点(如平衡二叉树、线索二叉树)。
二叉树是数据结构中的核心内容之一,也是考研高频考点。本文将从定义和存储结构两方面展开,结合具体示例帮助读者建立系统的知识框架。
一、二叉树的定义
二叉树(Binary Tree) 是每个节点最多有两个子树的树形结构,子树分为左子树和右子树,其顺序不可颠倒。具体特点包括:
- 递归性:二叉树由一个根节点和两棵互不相交的左、右子树构成,子树本身也是二叉树。
- 节点限制:每个节点的度(子节点数量)不超过2,且子树有明确的左右之分。
- 特殊形态:二叉树可以是空树(节点数为0),或仅含根节点的单节点树。
示例:
A/ \B C/ \D E
该二叉树中,A为根节点,B为左子树根,C为右子树根,D和E是B的左右子节点。
二、二叉树的存储结构
二叉树的存储结构分为顺序存储和链式存储两种,二者在实现方式和适用场景上有显著差异。
1. 顺序存储结构
使用一维数组按层序遍历顺序存储节点,通过数组下标隐式表达节点间的逻辑关系。
- 存储规则:
- 根节点位于数组下标
0
(或1
,视具体实现而定)。 - 若某节点位于下标
i
,其左子节点位于2i+1
(或2i
),右子节点位于2i+2
(或2i+1
)。
- 根节点位于数组下标
- 适用场景:
适合完全二叉树(如堆结构),此时空间利用率高;但对非完全二叉树可能导致大量空间浪费。
示例:
数组存储完全二叉树:
层序遍历顺序:A, B, C, D, E
数组索引:[A, B, C, D, E]
2. 链式存储结构
通过链表动态分配节点空间,每个节点包含数据域和两个指针域(左、右子节点指针)。
- 节点定义(C语言示例):
typedef struct BiTNode {int data;struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;
- 适用场景:
适合任意形态的二叉树,空间灵活性高,但需额外存储指针域。
示例:
链式存储结构:
A节点的lchild指向B,rchild指向C;
B节点的lchild指向D,rchild指向E。
三、存储结构对比
特性 | 顺序存储 | 链式存储 |
---|---|---|
空间效率 | 非完全二叉树浪费空间 | 灵活,无空间浪费 |
实现复杂度 | 简单,直接通过数组操作 | 需要管理指针,复杂度较高 |
适用场景 | 完全二叉树、堆结构 | 一般二叉树、动态变化的树结构 |
考研数据结构之二叉树(一):定义、存储结构与真题解析
四、真题解析
1. 选择题考点(完全二叉树节点数计算)
题目(改编自):
高度为
h
的完全二叉树最多和最少分别包含多少个节点?
解析:
- 最多节点数:当完全二叉树为满二叉树时,节点数为
2^h - 1
。 - 最少节点数:当最后一层仅有一个节点时,节点数为
2^(h-1)
。
答案:最多2^h - 1
,最少2^(h-1)
。
2. 综合应用题(二叉树的数组存储与遍历)
题目(2022年真题,):
已知二叉树的数组存储结构如下(下标从1开始):
A B C D E # #
请写出其中序遍历序列。
解析:
- 数组存储规则:下标
i
的左子节点为2i
,右子节点为2i+1
。 - 还原二叉树:
A/ \B C/ \ D E
- 中序遍历:左子树 → 根 → 右子树,结果为
D B E A C
。
答案:D B E A C
。
3. 算法设计题(二叉树的繁茂度)
题目(严蔚敏题集,):
定义二叉树的繁茂度为各层节点数的最大值与树的高度的乘积。设计算法计算二叉树的繁茂度。
解析:
- 关键步骤:
- 层次遍历统计每层节点数,记录最大值
maxWidth
。 - 计算树的高度
height
。 - 繁茂度 =
maxWidth * height
。
- 层次遍历统计每层节点数,记录最大值
- 代码框架(C语言):
int茂度(BiTree T) {if (!T) return 0;Queue Q;InitQueue(Q);EnQueue(Q, T);int maxWidth = 0, height = 0;while (!IsEmpty(Q)) {int levelSize = Q.size;maxWidth = max(maxWidth, levelSize);height++;for (int i = 0; i < levelSize; i++) {BiTree node = DeQueue(Q);if (node->lchild) EnQueue(Q, node->lchild);if (node->rchild) EnQueue(Q, node->rchild);}}return maxWidth * height; }
4. 还原二叉树(遍历序列应用)
题目(经典真题,):
已知二叉树的前序序列为
ABDCE
,中序序列为DBAEC
,画出该二叉树并写出后序序列。
解析:
- 前序:
A
为根节点,左子树前序为BD
,右子树前序为CE
。 - 中序:
A
左侧为左子树DB
,右侧为右子树EC
。 - 递归构建:
A/ \B C/ / D E
- 后序序列:
D B E C A
。
五、总结
通过真题解析可见:
- 定义类题目需熟悉完全二叉树、满二叉树的性质(如节点数计算)。
- 存储结构常结合遍历算法(如中序遍历)或数组/链表操作。
- 综合题需灵活运用遍历序列还原二叉树。
相关文章:
考研数据结构之二叉树(一)(包含真题及解析)
考研数据结构之二叉树(一) 下期预告:后续文章将深入探讨二叉树的遍历算法与高频考点(如平衡二叉树、线索二叉树)。 二叉树是数据结构中的核心内容之一,也是考研高频考点。本文将从定义和存储结构两方面展开…...
linux多线(进)程编程——番外1:内存映射与mmap
前言 在修真世界之外,无数异世界,其中某个叫地球的异世界中,一群人对共享内存的第二种使用方式做出了讲解。 内核空间与用户空间 内存空间的划分 Linux操作系统下一个进程的虚拟地址空间被分为用户空间与内核空间 Linux 内核空间在内存管…...
旧版 VMware 虚拟机迁移至 KVM 平台-案例2
项目背景 需将一台旧版 VMware 虚拟机(VMDK 格式)迁移至 KVM 虚拟化平台,具体要求如下: 格式转换:将 VMDK 转换为 QCOW2 格式。磁盘扩容:将原 40GB 磁盘扩展至 60GB。密码重置:修改 aiden 用户…...
六、adb通过Wifi连接
背景 收集是荣耀X40,数据线原装全新的,USB连上之后,老是断,电脑一直叮咚叮咚的响个不停,试试WIFI 连接是否稳定,需要手机和电脑用相同的WIFI. 连接 1.通过 USB 连接手机和电脑(打开USB调试等这些都略过) adb device…...
Kafka使用方式与底层原理解析
一、Kafka简介 Apache Kafka是一个分布式流处理平台,由LinkedIn开发并开源,现已成为实时数据管道和流应用的核心组件。它具备高吞吐量、低延迟、高可扩展性等特点,广泛应用于日志收集、消息系统、流处理等领域。 1.1 Kafka核心概念 Topic&…...
【Python内置函数的深度解析与应用】id
目录 前言:技术背景与价值当前技术痛点解决方案概述目标读者说明 一、技术原理剖析核心概念图解关键技术模块技术选型对比 二、实战演示环境配置要求核心代码实现1. 基础身份验证2. 不可变对象优化3. 对象生命周期追踪 运行结果验证 三、性能对比测试方法论量化数据…...
【Pandas】pandas DataFrame keys
Pandas2.2 DataFrame Indexing, iteration 方法描述DataFrame.head([n])用于返回 DataFrame 的前几行DataFrame.at快速访问和修改 DataFrame 中单个值的方法DataFrame.iat快速访问和修改 DataFrame 中单个值的方法DataFrame.loc用于基于标签(行标签和列标签&#…...
探索QEMU-KVM虚拟化:麒麟系统下传统与云镜像创建虚拟机的最佳实践
随着云计算和虚拟化技术的不断进步,虚拟化在管理服务器、隔离资源以及提升性能方面的好处越来越明显。麒麟操作系统Kylin OS是我们国家自己开发的操作系统,在政府机构和企业中用得很多。这篇文章会教你如何在麒麟操作系统上设置QEMU-KVM虚拟化环境&#…...
pycharm中调试功能讲解
一、调试前的准备工作 1. 准备一段测试代码 先写一个简单的Python脚本(比如计算阶乘),故意留点问题: def factorial(n):result 1for i in range(n):result * ireturn resultprint(factorial(5)) # 预期输出120࿰…...
SimpleITK (sitk) 中查看 DICOM 文件的像素位深(8位或16位)
在 SimpleITK (sitk) 中查看 DICOM 文件的像素位深(8位或16位),可以通过以下方法实现: 方法一:通过 图像像素数组的数据类型 判断 读取 DICOM 文件: 使用 sitk.ReadImage() 加载文件,生成图像对…...
day28图像处理OpenCV
文章目录 一、图像预处理4 边缘填充4.1 边界复制(BORDER_REPLICATE)4.2 边界反射(BORDER_REFLECT)4.3 边界反射101(BORDER_REFLECT_101)4.4 边界常数(BORDER_CONSTANT)4.5 边界包裹&…...
【NLP】 自然语言处理笔记
NLP的全称是Natuarl Language Processing,中文意思是自然语言处理,是人工智能领域的一个重要方向。自然语言处理(NLP)就是在机器语言和人类语言之间沟通的桥梁,以实现人机交流的目的。 人类语言是抽象的信息符号,其中蕴含着丰富的语义信息,人类可以很轻松地理解其中的含…...
LaTeX 的pstricks-add宏绘图练习
练习。 \documentclass[10pt]{article} \usepackage{pstricks-add} \pagestyle{empty} \begin{document} \psset{xunit1.0cm,yunit1.0cm,algebraictrue,dimenmiddle,dotstyleo,dotsize5pt 0,linewidth2.pt,arrowsize3pt 2,arrowinset0.25} \begin{pspicture*}(-16.5581463…...
WITRAN_2DPSGMU_Encoder 类中,门机制
WITRAN_2DPSGMU_Encoder 类中的门机制详解 在 WITRAN_2DPSGMU_Encoder 类中,门机制是核心部分,类似于 LSTM 或 GRU 的门控机制,用于控制隐藏状态的更新和输出。以下是对门机制的详细解析。 1. 门机制的作用 门机制的主要作用是:…...
OSI参考模型和TCP/IP模型
1.OSI参考模型 OSI模型: OSI参考模型有7层,自下而上依次为物理层,数据链路层,网络层,传输层,会话层,表示层,应用层。(记忆口诀:物联网叔会用)。低…...
3D版的VLA:从3D VLA、SpatialVLA到PointVLA——3D点云版的DexVLA,在动作专家中加入3D数据
前言 之前写这篇文章的时候,就想解读下3D VLA来着,但一直因为和团队并行开发具身项目,很多解读被各种延后 更是各种出差,比如从25年3月下旬至今,连续出差三轮,绕中国半圈,具身占八成 第一轮 …...
java: 需要‘)‘ java: 未结束的字符串文字,java: 不是语句,怎么解决
java: 需要’)’ IDE运行当中因为字符串中的JSON串,导致编码不对,IDEA编码识别错误,编译不过,程序运行不起来,解决办法。 第一步,进行修改编码进行尝试 第二步,继续修改编码...
HarmonyOS:使用Refresh组件实现页面下拉刷新上拉加载更多
一、前言 可以进行页面下拉操作并显示刷新动效的容器组件。 说明 该组件从API Version 8开始支持。后续版本如有新增内容,则采用上角标单独标记该内容的起始版本。该组件从API Version 12开始支持与垂直滚动的Swiper和Web的联动。当Swiper设置loop属性为true时&…...
HarmonyOS应用开发的工程目录结构
AppScope > app.json5 应用级的配置信息 AppScope > resources 这个目录下的base>element用于存放全局使用的基本元素,如字符串、颜色和布尔值。base>media目录则存储媒体、动画和布局等资源文件。如果模块下的resources的有同样的资源,那么…...
详解关于VS配置好Qt环境之后但无法打开ui界面
目录 找到Qt安装目录中designer.exe的路径 找到vs中的解决方案资源管理器 右键ui文件,找到打开方式 点击添加 然后把前面designer.exe的路径填到程序栏中,点击确定 然后设置为默认值,并点击确定 当在vs中配置好Qt环境之后,但…...
【JDBC-54.2】深入理解SQL注入攻击及JDBC防护方案
1. SQL注入攻击概述 SQL注入(SQL Injection)是当今Web应用程序中最常见、最危险的安全漏洞之一。它利用了应用程序对用户输入数据处理不当的缺陷,攻击者通过在输入字段中插入恶意的SQL代码片段,欺骗服务器执行非预期的SQL命令。 …...
PCDN通过个人路由器,用更靠近用户的节点来分发内容,从而达到更快地网络反应速度
PCDN(P2P CDN)的核心思想正是利用个人路由器、家庭宽带设备等分布式边缘节点,通过就近分发内容来降低延迟、提升网络响应速度,同时降低传统CDN的带宽成本。以下是其技术原理和优势的详细分析: 1. 为什么PCDN能更快&…...
【软件测试】bug 篇
本章思维导图: 1. 软件测试的生命周期 软件测试贯穿于整个软件的生命周期 流程阶段需求分析测试计划测试设计/开发测试执行测试评估上线运行维护具体工作内容1. 阅读需求文档 2. 标记可测试需求 3. 确定测试类型1. 制定测试范围 2. 选择测试工具 3. 分配资源1. 编写…...
java -jar指定类加载
在 Java 中,使用 java -jar 命令运行 JAR 文件时,默认会加载 JAR 文件的 MANIFEST.MF 文件中指定的 Main-Class。如果你想在运行时指定一个类来加载,可以通过以下方式实现: 方法 1:直接指定类路径和类名 如果你不想使用…...
MVC 模式深度解析与 Spring 框架实践研究
MVC 模式深度解析与 Spring 框架实践研究 摘要 MVC(Model-View-Controller)模式作为软件工程中最重要的架构模式之一,通过将应用逻辑划分为模型、视图和控制器三个独立组件,实现了代码的高内聚低耦合,显著提升了软件的可维护性和可扩展性。本文从 MVC 模式的核心思想出发…...
驱动开发硬核特训 · Day 11(下篇):从 virtio_blk 看虚拟总线驱动模型的真实落地
🔍 B站相应的视屏教程: 📌 内核:博文视频 - 总线驱动模型实战全解析 敬请关注,记得标为原始粉丝。 🔧 在上篇中,我们已经从理论视角分析了“虚拟总线驱动模型”在 Linux 驱动体系中的独特定位。…...
Java实现快速排序算法
用「整理书架」理解快速排序原理 想象你有一堆杂乱的书需要按大小排序,快速排序的步骤可以类比为: 1. 选一本“基准书”(比如最右侧的书) 2. 把书分成三堆: - 左边:比基准小的书 - 中间:基…...
3.3.2 应用层协议设计protobuf(二进制序列化协议)
文章目录 3.3.2 应用层协议设计protobuf(二进制序列化协议)1. 什么是协议设计什么是协议为什么说进程间通信就需要协议,而不是客户端与服务端之间为什么需要自己设计协议 2. 判断消息的完整性->区分消息的边界1.固定长度2. 特定符号3. 固定…...
软件测试过程模型:v模型、w模型、x模型、H模型
软件测试流程 获取测试需求编写测试计划制定测试方案开发和设计测试用例执行测试提交缺陷报告测试分析与评审提交测试报告准备下一版本测试 软件测试过程模型 v模型 【V模型是线性的操作方式】 优点: 验收测试的标准是用户的需求,用户需求对应指导…...
设计模式-代理模式
虚代理 根据需要创建对象...
cocos Spine资源及加载
COCOS Spine 资源加载 创建 Canvas 以及Camera 再进行spine 拖入 提供40个实战酷炫技能spine文件: Spine文件下载...
约翰·麦卡锡:我的人工智能之梦
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 约翰麦卡锡:我的人工智能之梦 一、引言:计算机科学的传奇人物…...
Scrapy结合Selenium实现搜索点击爬虫的最佳实践
一、动态网页爬取的挑战 动态网页通过JavaScript等技术在客户端动态生成内容,这使得传统的爬虫技术(如requests和BeautifulSoup)无法直接获取完整的内容。具体挑战包括: 数据加载异步化:数据并非一次性加载ÿ…...
Oracle数据库数据编程SQL<9.3 数据库逻辑备份和迁移Data Pump (EXPDP/IMPDP) 导出、导入补充>
Oracle Data Pump 是 Oracle 10g 引入的高效数据迁移工具,相比传统的 EXP/IMP 工具,它提供了更强大的功能和显著的性能提升。以下是对 EXPDP 和 IMPDP 工具的全面讲解。 目录 一、高级功能扩展 1. 数据过滤与转换 2. 加密与安全 二、性能调优进阶 1. 并行处理优化 2. …...
Vue 3 + TypeScript 实现一个多语言国际化组件(支持语言切换与内容加载)
文章目录 一、项目背景与功能概览二、项目技术架构与依赖安装2.1 技术栈2.2 安装依赖 三、国际化组件实现3.1 创建 i18n 实例3.2 配置 i18n 到 Vue 应用3.3 在组件中使用国际化内容3.4 支持语言切换 四、支持类型安全4.1 添加类型支持4.2 自动加载语言文件 一、项目背景与功能概…...
RK3506+net9+VS2022跨平台调试C#程序
下载GetVsDbg.sh ,这脚本会下载一个压缩包,然后解压缩,设置x权限等等。但是目标板子连不上,就想办法获取到下载路径,修改这个脚本,显示这个下载链接后,复制一下,用电脑下下来 修改好…...
c# 反射及优缺点
在C#中,反射(Reflection)是一种强大的机制,允许程序在运行时检查其自身的结构(如类型、属性、方法等),以及动态地调用对象的方法或访问其属性。反射主要用于那些在编译时不知道具体类型信息&…...
基于SpringBoot的在线教育系统
作者:计算机学姐 开发技术:SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等,“文末源码”。 专栏推荐:前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏:…...
吴恩达深度学习复盘(16)决策树|节点纯度与熵
决策树简介 决策树算法在很多应用中被使用,机器学习比赛中会经常见到,但在流行病学领域未受到太多关注。 决策树示例 —— 猫的分类 以经营猫收养中心为例,通过动物的耳朵形状、脸型、是否有胡须等特征,来训练一个分类器判断动…...
C++基础精讲-07
文章目录 1. const对象2. 指向对象的指针3. 对象数组4. c中const常见用法总结4.1 修饰常量4.2 修饰指针4.3 修饰函数参数4.4 修饰函数返回值4.5 修饰成员函数4.6 const对象 5. 赋值运算符函数(补充)5.1 概念5.2 默认赋值运算符函数局限5.3 解决办法 1. c…...
100个有用的AI工具 之 生成透明图像LayerDiffuse
Stable Diffusion是开源图像生成界的扛把子,最强的地方在于它的可控性,通过ControlNet,和一系列插件,可以非常精准地控制图像生成的需求。 今天介绍的是SD的一个插件LayerDiffuse,它可以帮助我们用SD生成透明的png图层。我们在用PS抠图的时候,对于头发、毛绒边这种图是非…...
springboot和springcloud的区别
1. 目的与功能 1)Spring Boot: 主要用于快速构建独立的、生产级的 Spring 应用程序。它通过自动配置和嵌入式服务器等特性,简化了微服务的开发、启动和部署,使开发者能够专注于业务逻辑而非繁琐的配置。Spring Boot是一个快速开发的框架,旨在简化Java应用程序的开…...
前端操作document的小方法,主要功能-获取当前页面全部的a标签页,并根据链接中必要的字段进行判断,然后把这些链接放入iframe去打开
首先是一些小方法,有一个问题就是在不同源的页面中无法获取iframe中的dom const isInIframe window.parent ! window.self; console.log(是否在 iframe 中:, isInIframe); console.log(来源页面:, document.referrer); const isSame new URL(document.referrer).o…...
RocketMQ 03
今天是2025/04/14 21:58 day 20 总路线请移步主页Java大纲相关文章 今天进行RocketMQ 6,7,8 个模块的归纳 最近在忙毕设,更新有点慢,见谅 首先是RocketMQ 的相关内容概括的思维导图 6. 安全机制 6.1 ACL 访问控制 核心功能 权限分级:通过…...
基于项目管理的轻量级目标检测自动标注系统【基于 YOLOV8】
🐱 AILabeler 是一个轻量级目标检测标注系统,专为 YOLO 系列模型设计,支持图像上传、标注框管理、类别设置、自动标注(YOLOv8)、导出多格式训练数据等功能。 项目已经发布至https://github.com/as501226107/AILabeler&…...
针对 Java从入门到精通 的完整学习路线图、各阶段技术点、CTO进阶路径以及经典书籍推荐。内容分阶段展开,兼顾技术深度与职业发展
以下是针对 Java从入门到精通 的完整学习路线图、各阶段技术点、CTO进阶路径以及经典书籍推荐。内容分阶段展开,兼顾技术深度与职业发展。 一、学习路线图分阶段详解 阶段1:Java基础入门(3-6个月) 目标:掌握Java核心…...
深度学习总结(13)
选择损失函数 为问题选择合适的损失函数,这是极其重要的。神经网络会采取各种方法使损失最小化,如果损失函数与成功完成当前任务不完全相关,那么神经网络最终的结果可能会不符合你的预期。因此,一定要明智地选择损失函数…...
AI测试引擎中CV和ML模型的技术架构
技术架构概述 1. 数据采集层 此层负责收集各种类型的数据,为后续的模型训练和测试提供基础。对于CV模型,主要采集图像、视频数据,可来源于摄像头、图像数据库等;对于ML模型,采集结构化数据(如表格数据)、非结构化数据(如文本数据)等,数据来源包括业务系统日志、传感…...
业务架构发展历史及相关技术应用介绍
1,单体架构 企业处于发展初期阶段,业务的开发量与用户的访问量较少的情况下,通常情况会将业务编写在一个应用中,由一个web容器完成部署调用。如下图,一个应用中所有的功能模块写在一个war包中,功能模块的代…...
Java栈与队列深度解析:结构、实现与应用指南
一、栈与队列核心概念对比 特性栈 (Stack)队列 (Queue)数据原则LIFO(后进先出)FIFO(先进先出)核心操作push(入栈)、pop(出栈)、peek(查看栈顶)offer(入队)、poll(出队)、peek(查看队首)典型应用函数调用栈、括号匹配、撤销操作任…...