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

算法笔记:二叉树

1 基本二叉树

  • 二叉树是一种树形数据结构,其中每个节点最多有两个子节点,通常称为“左子节点”和“右子节点”。
    • 二叉树的根是唯一没有父节点的节点,而所有其他节点都有一个父节点和零个或两个子节点。

1.1 基础术语

  • 节点(Node): 二叉树的基本单位。每个节点都有一个关键字(或称为“键值”或“数据”)。
  • 根节点(Root Node): 没有父节点的节点。
  • 叶节点(Leaf Node): 没有子节点的节点。
  • 子树(Subtree): 任何节点都可以视为其下的所有节点组成的一个新树。
  • 深度(Depth): 从根节点到某一节点的简单路径上的边数。
  • d层(Level): 树中所有深度为d的节点的集合。

1.2 二叉树的遍历

以如下二叉树为例

1.2.1 前序遍历

 先访问根节点,然后访问左子树,再访问右子树

ABDHIEJCFKG

1.2.2 中序遍历 

先访问左子树,再访问根节点,最后访问右子树

HDIBEJAFKCG

1.2.3 后序排列

 先访问左子树,再访问右子树,最后访问根节点

HIDJEBKFGCA

1.2.4 层次遍历

逐层的从根节点开始,每层从左至右遍历

ABCDEFGHIJK

2 斜二叉树

只有左子节点或只有右子节点的二叉树称为斜二叉树

3 满二叉树

所有的分支要么左右子节点都有,要么没有子节点,且所有叶子结点都在同一层上

4 完全二叉树

除了最后一层外,每一层都是完全填满的,并且所有节点都尽量向左填充

完全二叉树特点:

  • 叶子结点只能出现在最下两层;
  • 最下层的叶子结点一定集中在左边并且连续;
  • 若结点度为1,则该节点只有左子节点;
  • 完全二叉树的深度为\left \lceil \log_2(n+1) \right \rceil (n是树中节点的数量)
  • 在高度为h的完全二叉树中,节点数最少为2^{h-1},最多为2^h-1
  • 对于个索引为i的点(索引从1开始计数)
    • 父节点(若存在)的索引是\left \lfloor i/2 \right \rfloor
    • 左子节点(若存在)的索引是2i
    • 右子节点(若存在)的索引是2i+1

满二叉树一定是完全二叉树,而完全二叉树不一定是满二叉树

5 线索二叉树

  • 线索二叉树是一种对二叉树的改进,旨在通过线索(也就是额外的指针)加速对树的遍历操
  • 在普通的二叉树中,每个节点有两个子节点:左子节点和右子节点。但有些节点的子节点可能为空,这些空指针字段不存储任何信息
  • 线索二叉树通过利用这些空指针字段来存储与当前节点在某种遍历顺序(如前序、中序或后序)下相邻的节点。
    • 这样,在遍历树时,就不需要使用栈或递归,从而提高了遍历的速度
  • 在线索二叉树中,每个节点有两个额外的标志位,分别表示左指针和右指针是否被用作线索
    • 如果左子节点为空,则左指针字段存储该节点在某种遍历顺序下的前驱节点
    • 如果右子节点为空,则右指针字段存储该节点在某种遍历顺序下的后继节点

5.1 创建线索二叉树

创建线索二叉树通常需要两次遍历

  1. 第一次遍历是普通的前序、中序或后序遍历,用于建立二叉树的基本结构。
  2. 第二次遍历用于添加线索。这通常通过保存前一个访问的节点并在访问下一个节点时更新其线索来完成。

5.2 优缺点

优点

  • 遍历更快:由于已经存储了前驱和后继信息,遍历操作更加高效。
  • 不需要额外的数据结构:不需要使用栈或递归。

缺点

  • 额外的存储开销:需要额外的字段来存储线索和标志位。
  • 修改复杂:插入或删除节点时,需要更新相应的线索,这使得操作更加复杂。、

参考内容:数据结构与算法(八)-二叉树(斜二叉树、满二叉树、完全二叉树、线索二叉树)-腾讯云开发者社区-腾讯云 (tencent.com)

相关文章:

算法笔记:二叉树

1 基本二叉树 二叉树是一种树形数据结构,其中每个节点最多有两个子节点,通常称为“左子节点”和“右子节点”。 二叉树的根是唯一没有父节点的节点,而所有其他节点都有一个父节点和零个或两个子节点。 1.1 基础术语 节点(Node&…...

1. 安装Zookeeper

​ 1.下载 点击下载Zookeeper 单机版安装 安装Zookeeper前需要先安装jdk上传安装包rz解压安装包:tar -zxvf apache-zookeeper-3.6.0-bin.tar.gz -C /opt/app/zookeeper zookeeper目录结构:a. bin: 放置运行脚本和工具脚本b. conf: zookeeper 默认读取配置的目录,里面会有…...

warning: ignoring unsupported character ‘问题修复

rivers/net/wireless/aic8800/Kconfig:1⚠️ ignoring unsupported character 问题修复: 有一次编译内核,看到有下面的warning: jianjian:~/share/kylin/rk-kernel-5.10$ make menuconfigUPD scripts/kconfig/mconf-cfgHOSTCC scripts/…...

【Ant Design】Form.Item创建自定义表单

一、概述 Antd是一个非常强大的UI组件库,里面的Form表单组件也基本能满足我们大多数场景。但是也有需要自定义表单的场景。 Vue2里我们使用v-model,结合子组件的model属性,来实现自定义组件的双向绑定。 Vue3里我们使用v-model,…...

Vision Transformer(VIT 网络架构)

论文下载链接:https://arxiv.org/abs/2010.11929 文章目录 引言1. VIT与传统CNN的比较2. 为什么需要Transformer在图像任务中? 1. 深入Transformer1.1 Transformer的起源:NLP领域的突破1.2 Transformer的基本组成1.2.1 自注意机制 (Self-Atte…...

数学建模--蒙特卡洛模型的Python实现

目录 1.算法思想简介 2.算法应用1:问题一阐述 3.算法应用1:问题一解决 4.算法应用2:问题二阐述 5.算法应用2:问题二解决 1.算法思想简介 #蒙特卡洛算法思想 """ 蒙特卡洛方法的理论其实很类似于概率论中一个比较重…...

MySQL访问和配置

目录 1.使用MySQL自带的客户端工具访问 2.使用DOS访问(命令行窗口WinR → cmd) 3.连接工具(SQLyog或其它) MySQL从小白到总裁完整教程目录:https://blog.csdn.net/weixin_67859959/article/details/129334507?spm1001.2014.3001.5502 1.使用MySQL自…...

note_前端框架Vue的安装和简单入门(Windows 11)

1. Vue安装 (1) 下载安装node.js和npm # 下载msi安装包 https://nodejs.org/en# 点击安装包,按提示安装 # 默认安装nodejs, npm, 在线文档; PATH配置# 确认安装是否成功,在dos中输入 node -v # 验证nodejs是否安装成功 npm -v # 验证nodejs包管…...

SILERGY(矽力杰)功率电子开关 SY6280AAC

SILERGY(矽力杰)功率电子开关 SY6280AAC Low Loss Power Distribution Switch SOT-5 Pacakge 2.4V ~ 5.5V (<6V) 0.6W Max. Current 2A Reverse blocking (no body diode) Programmable current limit ( Ilimits(A) 6800 / Rset(ohm). ) Application Circuit (Reco…...

mysql char 和varchar的区别?

char 和varchar的区别 1、 char 一定会使用指定的空间&#xff0c;varchar是根据数据来定空间 2、 char的插入数据效率理论上比varchar高&#xff1a;varchar是需要通过后面的记录数来计算 使用哪一种类型&#xff1f; 如果确定数据一定是占指定长度&#xff0c;那么使用char类…...

HttpClient默认重试机制

分析&回答 只有发生IOExecetion时才会发生重试InterruptedIOException、UnknownHostException、ConnectException、SSLException&#xff0c;发生这4中异常不重试get方法可以重试3次&#xff0c;post方法在socket对应的输出流没有被write并flush成功时可以重试3次。读/写超…...

论文于祥读及复现——《Multi-level Map Construction for Dynamic Scenes》

论文祥读之——动态场景的多层次地图构建 0. 出发点&#xff08;暨摘要&#xff09;1. 引言2. 相关工作3.主要内容概括3.1 几何地图的构建3.1.1 密集点云地图和八叉图的构建3.1.2 平面地图的构建 3.2 对象地图的构建3.2.1 对象参数化和数据关联3.2.2 对象的更新与优化 4. 实验4…...

IDEA 报 Cannot resolve symbol ‘HttpServletResponse‘ 解决

springboot2版本换成springboot3之后&#xff0c;代码这里突然报红了&#xff0c; 首先要淡定&#xff0c;把原先Import的引入删掉&#xff0c;重新引入试试呢&#xff0c;是不是很简单哈哈。 原来&#xff0c;springboot3的路径是&#xff1a; import jakarta.servlet.http…...

linux-samba-window登不上

登不上查了很久发现是防火墙导致的 sudo firewall-cmd --list-all //查看所有的防火墙信息sudo firewall-cmd --permanent --zonepublic --add-servicesamba //service里添加sambafirewall-cmd --reload //重启 便可以登录了,小问题...

Java Web3J :使用web3j监听、查询、订阅智能合约的事件

前面有文章写如何使用Docker-compose方式部署blockscout浏览器+charts图表,区块链浏览器已经部署成功了,同时我们在链上增加了治理投票流程,如何实时的把治理事件快速同步到浏览器呢?这时就想到了Web3J来监听智能合约的事件,来达到同步事件的效果 目录 Web3J简介功能简介m…...

C语言入门 Day_13 二维数组

目录 前言&#xff1a; 1.字符串 2.创建二维数组 3.使用二维数组 4.易错点 5.思维导图 前言&#xff1a; 我们学习了字符类型char&#xff0c;我们可以用char来表示一个大写或者小写的字母&#xff0c;但真实应用中我们往往使用的是多个字符组成的一个单词或者句子。 …...

通过HFS低成本搭建NAS,并内网穿透实现公网访问

文章目录 前言1.下载安装cpolar1.1 设置HFS访客1.2 虚拟文件系统 2. 使用cpolar建立一条内网穿透数据隧道2.1 保留隧道2.2 隧道名称2.3 成功使用cpolar创建二级子域名访问本地hfs 总结 前言 云存储作为一个新概念&#xff0c;在前些年炒的火热&#xff0c;虽然伴随一系列黑天鹅…...

【SpringMVC】工作流程及入门案例

目录 前言 回顾MVC三层架构 1. SpringMVC简介 …...

【JVM】垃圾收集算法

文章目录 分代收集理论标记-清除算法标记-复制算法标记-整理算法 分代收集理论 当前商业虚拟机的垃圾收集器&#xff0c;大多数都遵循了“分代收集”&#xff08;Generational Collection&#xff09;[1]的理论进 行设计&#xff0c;分代收集名为理论&#xff0c;实质是一套符…...

K8s的Pod出现Init:ImagePullBackOff问题的解决(以calico为例)

对于这类问题的解决思路应该都差不多&#xff0c;本文以calico插件安装为例&#xff0c;发现有个Pod的镜像没有pull成功 第一步&#xff1a;查看这个pod的描述信息 kubectl describe pod calico-node-wmhrw -n kube-system 从上图发现是docker拉取"calico/cni:v3.15.1&q…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...

《Docker》架构

文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器&#xff0c;docker&#xff0c;镜像&#xff0c;k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...

Python 高级应用10:在python 大型项目中 FastAPI 和 Django 的相互配合

无论是python&#xff0c;或者java 的大型项目中&#xff0c;都会涉及到 自身平台微服务之间的相互调用&#xff0c;以及和第三发平台的 接口对接&#xff0c;那在python 中是怎么实现的呢&#xff1f; 在 Python Web 开发中&#xff0c;FastAPI 和 Django 是两个重要但定位不…...

Electron简介(附电子书学习资料)

一、什么是Electron&#xff1f; Electron 是一个由 GitHub 开发的 开源框架&#xff0c;允许开发者使用 Web技术&#xff08;HTML、CSS、JavaScript&#xff09; 构建跨平台的桌面应用程序&#xff08;Windows、macOS、Linux&#xff09;。它将 Chromium浏览器内核 和 Node.j…...

【大厂机试题+算法可视化】最长的指定瑕疵度的元音子串

题目 开头和结尾都是元音字母&#xff08;aeiouAEIOU&#xff09;的字符串为元音字符串&#xff0c;其中混杂的非元音字母数量为其瑕疵度。比如: “a” 、 “aa”是元音字符串&#xff0c;其瑕疵度都为0 “aiur”不是元音字符串&#xff08;结尾不是元音字符&#xff09; “…...

在Android13上添加系统服务的好用例子

在Android13上添加一个自动的system service例子 留好&#xff0c;备用。 --- .../prebuilts/api/30.0/plat_pub_versioned.cil | 76 - .../prebuilts/api/31.0/plat_pub_versioned.cil | 94 - .../prebuilts/api/32.0/plat_pub_versioned.cil | 94 - frameworks/base/co…...