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

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

news 2025/7/7 7:24:35

《树与二叉树》

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

浏览器访问 AWS ECS 上部署的 Docker 容器（监听 80 端口）

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

编程新知 2025/7/7 1:45:57

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

编程新知 2025/7/6 4:04:07

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

编程新知 2025/6/11 15:21:26

FastAPI 教程：从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

编程新知 2025/7/5 11:09:46

多模态商品数据接口：融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

编程新知 2025/7/7 1:12:07

Qwen3-Embedding-0.6B深度解析：多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

编程新知 2025/6/15 15:47:35

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

编程新知 2025/7/6 21:12:40

Neo4j 集群管理：原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档，本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石，用于构建高可用、可扩展且一致的图数据库服务…...

编程新知 2025/7/4 0:49:28

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

编程新知 2025/7/4 8:43:57

优选算法第十二讲：队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

编程新知 2025/7/6 22:41:36