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

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

news 2026/1/11 6:08:52

《树与二叉树》

  • 二叉树的顺序存储结构
  • 顺序存储只适用于完全二叉树和满二叉树，一般二叉树不适用
  • 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

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

编程新知 2026/1/9 13:51:48

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

编程新知 2026/1/8 20:15:27

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

编程新知 2025/12/10 6:18:55

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

编程新知 2025/8/25 19:12:45

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

编程新知 2025/12/31 16:08:24

Go 并发编程基础：通道（Channel）的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

编程新知 2025/12/4 8:54:35

Xcode 16 集成 cocoapods 报错

基于 Xcode 16 新建工程项目&#xff0c;集成 cocoapods 执行 pod init 报错 ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchro…...

编程新知 2026/1/10 9:02:12

ubuntu中安装conda的后遗症

缘由: 在编译rk3588的sdk时&#xff0c;遇到编译buildroot失败&#xff0c;提示如下&#xff1a; 提示缺失expect&#xff0c;但是实测相关工具是在的&#xff0c;如下显示&#xff1a; 然后查找借助各个ai工具&#xff0c;重新安装相关的工具&#xff0c;依然无解。 解决&am…...

编程新知 2026/1/9 16:26:00

ffmpeg（三）：处理原始数据命令

FFmpeg 可以直接处理原始音频和视频数据&#xff08;Raw PCM、YUV 等&#xff09;&#xff0c;常见场景包括&#xff1a; 将原始 YUV 图像编码为 H.264 视频将 PCM 音频编码为 AAC 或 MP3对原始音视频数据进行封装&#xff08;如封装为 MP4、TS&#xff09; 处理原始 YUV 视频…...

编程新知 2025/10/5 16:18:49

【Linux】使用1Panel 面板让服务器定时自动执行任务

服务器就是一台24小时开机的主机&#xff0c;相比自己家中不定时开关机的主机更适合完成定时任务&#xff0c;例如下载资源、备份上传&#xff0c;或者登录某个网站执行一些操作&#xff0c;只需要编写 脚本&#xff0c;然后让服务器定时来执行这个脚本就可以。 有很多方法实现…...

编程新知 2026/1/9 4:11:37