算法笔记:二叉树
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,则该节点只有左子节点;
- 完全二叉树的深度为
(n是树中节点的数量)
- 在高度为h的完全二叉树中,节点数最少为
,最多为
- 对于个索引为i的点(索引从1开始计数)
- 父节点(若存在)的索引是
- 左子节点(若存在)的索引是2i
- 右子节点(若存在)的索引是2i+1
- 父节点(若存在)的索引是
满二叉树一定是完全二叉树,而完全二叉树不一定是满二叉树
5 线索二叉树
- 线索二叉树是一种对二叉树的改进,旨在通过线索(也就是额外的指针)加速对树的遍历操作
- 在普通的二叉树中,每个节点有两个子节点:左子节点和右子节点。但有些节点的子节点可能为空,这些空指针字段不存储任何信息
- 线索二叉树通过利用这些空指针字段来存储与当前节点在某种遍历顺序(如前序、中序或后序)下相邻的节点。
- 这样,在遍历树时,就不需要使用栈或递归,从而提高了遍历的速度
- 在线索二叉树中,每个节点有两个额外的标志位,分别表示左指针和右指针是否被用作线索
- 如果左子节点为空,则左指针字段存储该节点在某种遍历顺序下的前驱节点
- 如果右子节点为空,则右指针字段存储该节点在某种遍历顺序下的后继节点

5.1 创建线索二叉树
创建线索二叉树通常需要两次遍历:
- 第一次遍历是普通的前序、中序或后序遍历,用于建立二叉树的基本结构。
- 第二次遍历用于添加线索。这通常通过保存前一个访问的节点并在访问下一个节点时更新其线索来完成。
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 一定会使用指定的空间,varchar是根据数据来定空间 2、 char的插入数据效率理论上比varchar高:varchar是需要通过后面的记录数来计算 使用哪一种类型? 如果确定数据一定是占指定长度,那么使用char类…...
HttpClient默认重试机制
分析&回答 只有发生IOExecetion时才会发生重试InterruptedIOException、UnknownHostException、ConnectException、SSLException,发生这4中异常不重试get方法可以重试3次,post方法在socket对应的输出流没有被write并flush成功时可以重试3次。读/写超…...
论文于祥读及复现——《Multi-level Map Construction for Dynamic Scenes》
论文祥读之——动态场景的多层次地图构建 0. 出发点(暨摘要)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之后,代码这里突然报红了, 首先要淡定,把原先Import的引入删掉,重新引入试试呢,是不是很简单哈哈。 原来,springboot3的路径是: 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 二维数组
目录 前言: 1.字符串 2.创建二维数组 3.使用二维数组 4.易错点 5.思维导图 前言: 我们学习了字符类型char,我们可以用char来表示一个大写或者小写的字母,但真实应用中我们往往使用的是多个字符组成的一个单词或者句子。 …...
通过HFS低成本搭建NAS,并内网穿透实现公网访问
文章目录 前言1.下载安装cpolar1.1 设置HFS访客1.2 虚拟文件系统 2. 使用cpolar建立一条内网穿透数据隧道2.1 保留隧道2.2 隧道名称2.3 成功使用cpolar创建二级子域名访问本地hfs 总结 前言 云存储作为一个新概念,在前些年炒的火热,虽然伴随一系列黑天鹅…...
【SpringMVC】工作流程及入门案例
目录 前言 回顾MVC三层架构 1. SpringMVC简介 …...
【JVM】垃圾收集算法
文章目录 分代收集理论标记-清除算法标记-复制算法标记-整理算法 分代收集理论 当前商业虚拟机的垃圾收集器,大多数都遵循了“分代收集”(Generational Collection)[1]的理论进 行设计,分代收集名为理论,实质是一套符…...
K8s的Pod出现Init:ImagePullBackOff问题的解决(以calico为例)
对于这类问题的解决思路应该都差不多,本文以calico插件安装为例,发现有个Pod的镜像没有pull成功 第一步:查看这个pod的描述信息 kubectl describe pod calico-node-wmhrw -n kube-system 从上图发现是docker拉取"calico/cni:v3.15.1&q…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...

