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

【软考】9.3 二叉树存储/遍历/线索/最优/查找/平衡

news 2026/2/8 3:40:37

《树与二叉树》

  • 二叉树的顺序存储结构
  • 顺序存储只适用于完全二叉树和满二叉树，一般二叉树不适用
  • i =2 的左孩子为 2i =4，右孩子为 2i +1 =5
    在这里插入图片描述
  • 二叉树的链式存储结构
  • 链式存储适用于二叉树；空结点用“∧”表示
  • 二叉链表：左孩子，右孩子
  • 三叉链表：左孩子，双亲结点，右孩子
    在这里插入图片描述
  • 二叉树的遍历
  • 先序（前序）遍历：根，左，右
  • 中序遍历：左，根，右
  • 后序遍历：左，右，根
  • 层次遍历：从上到下，从左到右
    在这里插入图片描述
  • 深度为k的二叉树（满二叉树）至多有 (2^k) -1 个节点
  • 顺序存储：完全二叉树，一般二叉树需补虚节点——> 2^4 -1 = 15
  • 三叉链表：每个节点有3个指针域；——> 1+2+1+0+2+2=8
    在这里插入图片描述
  • 线索二叉树
  • 保存二叉树遍历时某节点的前驱节点和后继节点的信息
  • n个节点的二叉树使用链表存储，则有 n+1 哥空指针域
    在这里插入图片描述
  • 哈夫曼树（最优二叉树）
  • 带权路径长度最短的树
  • 树的路径长度：根节点到每一个叶子节点的路径长度之和
  • 树的带权路径长度：树的所有叶子节点的带权路径长度之和
    在这里插入图片描述
  • 哈夫曼树的求法：
  • 最小权值为叶子节点，其和为父节点，后删除叶子节点，不断循环，直到所有权值用完
  • 哈夫曼树编码：左节点值小于右节点值；左分支设为0，右分支设为1
    在这里插入图片描述在这里插入图片描述
  • 查找二叉树（排序二叉树）
  • 每个节点的所有左孩子节点值都小于父节点值，而右孩子则大于（左 < 根 < 右）
  • 每次查找范围缩小一半，查找效率较高
  • 深度越大，效率越低
    在这里插入图片描述
    在这里插入图片描述
  • 单枝树：深度最大，效率最低
  • 平衡二叉树（AVL树）：深度最小，效率最高；左子树和右子树的高度之差的绝对值不超过1；
    在这里插入图片描述
    在这里插入图片描述
  • 二叉树遍历列速解

已知（先序 / 后序） 与中序，求（后序 / 先序）
在这里插入图片描述

相关文章：

【软考】9.3 二叉树存储/遍历/线索/最优/查找/平衡

《树与二叉树》 二叉树的顺序存储结构 顺序存储只适用于完全二叉树和满二叉树&#xff0c;一般二叉树不适用i 2 的左孩子为 2i 4&#xff0c;右孩子为 2i 1 5 二叉树的链式存储结构 链式存储适用于二叉树&#xff1b;空结点用“∧”表示二叉链表&#xff1a;左孩子&#xff0…...

编程日记 2023/10/15 18:29:24

关于矿井地面电力综合自动化系统的研究与产品选型

安科瑞 崔丽洁 摘要&#xff1a;煤矿供电系统是煤矿生产的重要动力保障 , 一旦电力中断 , 生产将被迫停止 , 同时停电后容易发生瓦斯积聚爆炸、淹井等恶性事故&#xff0c;现有配电室采用不同厂商的保护装 置产品&#xff0c;没有形成有效的监控配电系统&#xff0c;不便于管…...

编程日记 2023/10/15 18:27:22

论文阅读：Offboard 3D Object Detection from Point Cloud Sequences

目录 概要 Motivation 整体架构流程 技术细节 3D Auto Labeling Pipeline The static object auto labeling model The dynamic object auto labeling model 小结 论文地址&#xff1a;[2103.05073] Offboard 3D Object Detection from Point Cloud Sequences (arxiv.o…...

编程日记 2023/10/15 18:26:20

Python学习基础笔记六十八——循环

循环是编程语言常见的流程控制。 Python语句要让计算机反复地做一些事情&#xff0c;就要用到循环语句。 有While和for循环。 while循环&#xff1a; command input("请输入命令:") while command ! exit:print(f输入的命令是{command})command input("请输…...

编程日记 2023/10/15 18:25:19

部署k8s dashboard（这里使用Kubepi）

9. 部署k8s dashboard&#xff08;这里使用Kubepi&#xff09; Kubepi是一个简单高效的k8s集群图形化管理工具&#xff0c;方便日常管理K8S集群&#xff0c;高效快速的查询日志定位问题的工具 部署KubePI&#xff08;随便在哪个节点部署&#xff0c;我这里在主节点部署&#…...

编程日记 2023/10/15 18:22:17

Java Lambda表达式的使用

我们了解了 java Lambda 的概念并可以在匿名类的场合使用 Lambda 语法进行简单替换。本节主要介绍在 Java 中如何使用 Lambda 表达式。 作为参数使用Lambda表达式 Lambda 表达式一种常见的用途就是作为参数传递给方法&#xff0c;这需要声明参数的类型声明为函数式接口类型。…...

编程日记 2023/10/15 18:21:15

【初始C语言8】详细讲解初阶结构体的知识

前言 &#x1f493;作者简介&#xff1a; 加油&#xff0c;旭杏&#xff0c;目前大二&#xff0c;正在学习C&#xff0c;数据结构等&#x1f440; &#x1f493;作者主页&#xff1a;加油&#xff0c;旭杏的主页&#x1f440; ⏩本文收录在&#xff1a;再识C进阶的专栏&#x1…...

编程日记 2023/10/15 18:19:14

＜C++＞ IO流

C语言的输入与输出 在C语言当中&#xff0c;我们使用最频繁的输入输出方式就是scanf与printf&#xff1a; scanf&#xff1a; 从标准输入设备&#xff08;键盘&#xff09;读取数据&#xff0c;并将读取到的值存放到某一指定变量当中。printf&#xff1a; 将指定的数据输出到…...

编程日记 2023/10/15 18:18:13

基于单目相机的2D测量（工件尺寸和物体尺寸）

目录 1.简介 2.基于单目相机的2D测量 2.1 想法&#xff1a; 2.2 代码思路 2.2 主函数部分 1.简介 基于单目相机的2D测量技术在许多领域中具有重要的背景和意义。 工业制造&#xff1a;在工业制造过程中&#xff0c;精确测量是确保产品质量和一致性的关键。基于单目相机的2…...

编程日记 2023/10/15 18:16:11

23面向对象案例1

目录 1、计算连续表达式的一个过程 2、优化后的代码 为什么不能return resultn&#xff1f; 3、用面向对象的方法可以解决冗余的问题&#xff0c;但是还是不能解决result的值可以被随意修改的问题 4、解决不能被随意修改的问题&#xff0c;可以将类属性改成私有变量吗&…...

编程日记 2023/10/15 18:15:09

go语言基础之常量与itoa

视频学习地址&#xff1a;Go零基础入门_在线视频教程-CSDN程序员研修院 一. 常量 定义&#xff1a;常量是一个简单值的标识符&#xff0c;在程序运行时&#xff0c;不会被修改的量。注意&#xff1a;常量中的数据类型只可以是布尔型、数字型&#xff08;整数型、浮点型和复数…...

编程日记 2023/10/15 18:14:09

民宿酒店订房房态商城小程序的作用是什么

外出旅游出差&#xff0c;酒店民宿总是很好的选择&#xff0c;随着经济复苏&#xff0c;各地旅游及外出办公人次增多&#xff0c;酒店成绩随之增加&#xff0c;市场呈现多品牌酒店经营形式。 区别于以前&#xff0c;如今互联网深入各个行业&#xff0c;酒店经营也面临着困境。…...

编程日记 2023/10/15 18:11:07

acwing算法基础之数据结构--栈和队列

目录 1 知识点2 模板 1 知识点 栈&#xff1a;先进后出。先进的就是栈底&#xff0c;后进的就是栈顶。后进先出嘛&#xff0c;所以在栈顶弹出元素。 队列&#xff1a;先进先出。先进的就是队头&#xff0c;后进的就是队尾。先进先出嘛&#xff0c;所以在队头弹出元素。 单调…...

编程日记 2023/10/15 18:10:06

关于导出的Excel文件的本质

上篇文章中提到关于xlsx改造冻结窗格的代码&#xff0c;我是怎么知道要加pane的呢&#xff0c;加下来就把我的心路历程记录一下。 我改造之前也是没有头绪的&#xff0c;我网上查了很多&#xff0c;只告诉我如何使用&#xff0c;但源码里没有针对!freeze的处理&#xff0c;所以…...

编程日记 2023/10/15 18:09:05

Rust中FnOnce如何传递给一个约束Fn的回调

Rust中FnOnce如何传递给一个约束Fn的回调 下面的代码&#xff0c;set_cb(func);会报错&#xff0c;如何包装能够做到这样的效果&#xff1a; fn set_cb<F: Fn() static>(handler: F) {handler(); }fn main() {let join_handle std::thread::spawn(|| {});let func |…...

编程日记 2023/10/15 18:08:02

【JUC】线程通信与等待唤醒机制

文章目录 1. 线程通信2. Object类中的wait和notify方法实现等待和唤醒3. Condition接口中的await和signal方法实现等待和唤醒4. LockSupport实现等待和唤醒4.1 优点 1. 线程通信 多个线程在处理同一个资源&#xff0c;但是处理的动作&#xff08;线程的任务&#xff09;却不相…...

编程日记 2023/10/15 18:07:01

C#面对对象（英雄联盟人物管理系统）

目录 英雄信息类 因为要在两个窗体里面调用字典&#xff0c;所以要写两个类来构建全局变量 添加功能 查询功能 英雄信息类 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace WindowsFormsApp…...

编程日记 2023/10/15 18:06:00

2023年中国分布式光纤传感产量、需求量及行业市场规模分析[图]

分布式光纤传感器中的光纤能够集传感、传输功能于一体&#xff0c;能够完成在整条光纤长度上环境参量的空间、时间多维连续测量&#xff0c;具有结构简单、易于布设、性价比高、易实现长距离等独特优点&#xff0c;常用的分布式光纤传感器有光时域反射仪、布里渊分析仪、喇曼反…...

编程日记 2023/10/15 18:04:59

B2R Raven: 2靶机渗透

B2R Raven: 2靶机渗透 视频参考&#xff1a;ajest &#xff1a;https://www.zhihu.com/zvideo/1547357583714775040?utm_id0 原文参考&#xff1a;ajest &#xff1a;https://zhuanlan.zhihu.com/p/270343652 文章目录 B2R Raven: 2靶机渗透1 启动靶机&#xff0c;查看后网卡…...

编程日记 2023/10/15 18:03:58

SpringBoot-黑马程序员-学习笔记（六）

目录 76.常用计量单位使用 77.bean属性校验 81.测试表现层 82.发送虚拟请求 94.springboot读写redis的客户端 100.ElasticSearch&#xff08;简称ES&#xff09; 一个分布式全文搜索引擎 76.常用计量单位使用 Data Component ConfigurationProperties(prefix "serve…...

编程日记 2023/10/15 18:02:57

＜6＞-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

编程新知 2025/12/11 18:28:17

安宝特方案丨XRSOP人员作业标准化管理平台：AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

编程新知 2026/2/5 17:57:20

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...

编程新知 2025/12/31 17:08:10

C++实现分布式网络通信框架RPC(2)——rpc发布端

有了上篇文章的项目的基本知识的了解&#xff0c;现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...

编程新知 2026/2/5 18:18:58

用递归算法解锁「子集」问题 —— LeetCode 78题解析

文章目录 一、题目介绍二、递归思路详解&#xff1a;从决策树开始理解三、解法一&#xff1a;二叉决策树 DFS四、解法二&#xff1a;组合式回溯写法&#xff08;推荐&#xff09;五、解法对比 递归算法是编程中一种非常强大且常见的思想&#xff0c;它能够优雅地解决很多复杂的…...

编程新知 2025/10/4 7:43:43

ArcPy扩展模块的使用(3)

管理工程项目 arcpy.mp模块允许用户管理布局、地图、报表、文件夹连接、视图等工程项目。例如&#xff0c;可以更新、修复或替换图层数据源&#xff0c;修改图层的符号系统&#xff0c;甚至自动在线执行共享要托管在组织中的工程项。 以下代码展示了如何更新图层的数据源&…...

编程新知 2025/10/2 7:24:40

UE5 音效系统

一.音效管理 音乐一般都是WAV,创建一个背景音乐类SoudClass,一个音效类SoundClass。所有的音乐都分为这两个类。再创建一个总音乐类&#xff0c;将上述两个作为它的子类。 接着我们创建一个音乐混合类SoundMix&#xff0c;将上述三个类翻入其中&#xff0c;通过它管理每个音乐…...

编程新知 2026/1/29 17:39:27

麒麟系统使用-进行.NET开发

文章目录 前言一、搭建dotnet环境1.获取相关资源2.配置dotnet 二、使用dotnet三、其他说明总结 前言 麒麟系统的内核是基于linux的&#xff0c;如果需要进行.NET开发&#xff0c;则需要安装特定的应用。由于NET Framework 是仅适用于 Windows 版本的 .NET&#xff0c;所以要进…...

编程新知 2026/1/24 3:53:21

Redis上篇--知识点总结

Redis上篇–解析 本文大部分知识整理自网上&#xff0c;在正文结束后都会附上参考地址。如果想要深入或者详细学习可以通过文末链接跳转学习。 1. 基本介绍 Redis 是一个开源的、高性能的 内存键值数据库&#xff0c;Redis 的键值对中的 key 就是字符串对象&#xff0c;而 val…...

编程新知 2026/2/5 4:40:48

Qt的学习（二）

1. 创建Hello Word 两种方式&#xff0c;实现helloworld&#xff1a; 1.通过图形化的方式&#xff0c;在界面上创建出一个控件&#xff0c;显示helloworld 2.通过纯代码的方式&#xff0c;通过编写代码&#xff0c;在界面上创建控件&#xff0c; 显示hello world&#xff1b; …...

编程新知 2026/2/6 2:41:56