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

二叉树,二叉查找树,平衡二叉树

一.绪论:


二.数据结构(二叉树):

1.简介:

1)每一个节点(也叫结点)都是一个独立的对象-->当中不仅要存数据值,还要存父节点地址值,左子节点地址值,右子 节点地址值

2)没有父节点或者子节点的节点就记为null


2.遍历方式:(适用于所有二叉树)

a.前序遍历:按照上->中->下的方式遍历

b.中序遍历:(重点)按照左->中->右的方式遍历(也是按小到大)

c.后序遍历:

d.层序遍历:


3.遍历方式的总结:


三.数据结构(二叉查找树):

1.概念:


2.添加节点:

规则:


3.查找结点:

要从根节点*开始查找,之后根据小的在左边,大的在右边进行查找即可


四.数据结构(平衡二叉树):

1.规则:

该二叉树不是平衡二叉树,因为比如节点10的左子树高度为0,节点10的右子树高度为3,高度差为2,已经超过了1

注:规则中的任意节点是指同一个节点的左右子树,不是任意两个节点

2.实例:

该二叉树是平衡二叉树

节点7的左子树高度为2,右子树高度为1,高度差为1,符合规则

其他节点同理


五.数据结构(树)的演变:


六.平衡二叉树的旋转机制->用于保持二叉树的平衡:(平衡时不用旋转)

1.规则1->左旋:

例1:

改正后为:

例2:


2.规则2->右旋:

例1:

例2:


3.触发时机:当添加一个节点后,该树不再是一颗平衡二叉树(如果添加一个节点后仍旧是平衡二叉树,则不触发旋转机制)


七.平衡二叉树需要旋转的四种情况:

1.左左:当根节点左子树的左子树有节点插入,导致二叉树不平衡(一次右旋即可搞定)

例如:

插入节点后:

改正:


2.左右:当根节点左子树的右子树有节点插入,导致二叉树不平衡(不止一次才能搞定->

先局部左旋,再整体右旋)

例如:

插入节点后:

开始旋转:

但仍未平衡,继续旋转:

先要重新进行局部旋转


3.右右:当根节点右子树的右子树有节点插入,导致二叉树不平衡(一次左旋即可搞定)

例如:

添加节点后:


4.右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡(不止一次才能搞定->

先局部右旋,再整体左旋)

例如:

添加节点后:

开始旋转:


相关文章:

二叉树,二叉查找树,平衡二叉树

一.绪论: 二.数据结构(二叉树): 1.简介: 1)每一个节点(也叫结点)都是一个独立的对象-->当中不仅要存数据值,还要存父节点地址值,左子节点地址值,右子 节点地址值 2)没有父节点或者子节点的节点就记为null 2.遍历方…...

《零散知识点 · SpringBoot 整合邮件功能》

📢 大家好,我是 【战神刘玉栋】,有10多年的研发经验,致力于前后端技术栈的知识沉淀和传播。 💗 🌻 CSDN入驻不久,希望大家多多支持,后续会继续提升文章质量,绝不滥竽充数…...

编程小白如何成为大神?大学新生的最佳入门攻略

目录 方向一:选择适合的编程语言 方向二:制定有效的学习计划 方向三:避免常见的学习陷阱 方向四:额外建议 编程已成为当代大学生的必备技能,但面对众多编程语言和学习资源,新生们常常感到迷茫。如何选择…...

使用 PyInstaller 和 Hook 文件打包 APK 解析工具

错误信息如下&#xff1a; Traceback (most recent call last):File "test.py", line 4, in <module>File "<frozen importlib._bootstrap>", line 991, in _find_and_loadFile "<frozen importlib._bootstrap>", line 975, …...

【分布式】分库分表知识点大全

为什么要分库分表 随着业务量的增加导致数据库中数据量的增加&#xff0c;可能拖慢查询的性能&#xff0c;影响业务的可用性&#xff1b;如果数据库采用读写分离&#xff0c;可能会导致从库的延迟较大&#xff0c;主库进行写操作后&#xff0c;从库因为延迟无法及时同步&#…...

FreeRTOS中的定时器:xTimerCreate ,xTimerStart ,xTimerStop

1. 创建定时器 定时器的创建使用 xTimerCreate 函数。该函数有以下参数&#xff1a; pcTimerName&#xff1a;定时器的名字&#xff0c;主要用于调试。xTimerPeriodInTicks&#xff1a;定时器的周期&#xff0c;以系统节拍计时。uxAutoReload&#xff1a;定时器是否自动重载。如…...

【网络安全】文件上传黑白名单及数组绕过技巧

不安全的文件上传&#xff08;Unsafe FileUpload&#xff09; 不安全的文件上传是指Web应用程序在处理用户上传的文件时&#xff0c;没有采取足够的安全措施&#xff0c;导致攻击者可能利用这些漏洞上传恶意文件&#xff0c;进而对服务器或用户造成危害。 目录 一、文件上传…...

4.2、存储管理-页式存储

页式存储和段氏存储会考 页式存储几乎必考&#xff0c;段氏存储可能会考 页式存储 页式存储是操作系统的一种存储管理方式。 因为我们的程序往往是远远大于内存的&#xff0c;所以程序在执行的时候&#xff0c;是不会一次性把所有内容都装入到内存中&#xff0c;它会把程序分…...

60个常见的 Linux 指令

常见60个Linux指令 1.ssh 登录到计算机主机2.ls 列出目录内容3.pwd 当前终端会话所在的完整路径4.cd 切换当前工作目录5.touch 创建空文件或更新文件的时间戳6.echo 终端输出文本或变量值7.nano 在终端中编辑文件8.vim 文本编辑器9.cat 查看、连接和创建文件10.shred 安全删除敏…...

DockerRedis基础

目录 Docker 部署MySQL 镜像和容器 解析命令 Docker基础 常见命令 命令别名 数据卷 命令 自定义镜像 Dockerfile 网络 自定义网络设置静态IP Redis概述 NoSQL&#xff08;非关系型数据库&#xff09; Redis Redis命令行客户端 Redis数据结构 Redis通用命令&…...

oracle读写时相关字符集详解

服务器端操作系统&#xff08;Oracle linux&#xff09;字符集 服务器端数据库字符集 客户端操作系统&#xff08;Oracle linux&#xff09;字符集 客户端工具sqlplus字符集 结论1&#xff1a;客户端工具sqlplus的会话&#xff0c;使用的字符集&#xff0c;是数据库字符集。…...

OverlayFS 文件系统介绍

引言 OverlayFS&#xff08;Overlay Filesystem&#xff09;是 Linux 内核中的一种联合文件系统&#xff08;Union Filesystem&#xff09;&#xff0c;它通过叠加多个目录形成一个单一的文件系统视图。作为 Docker 的默认存储驱动之一&#xff0c;OverlayFS 在提高性能和简化容…...

【C++】用Lua绑定C/C++对象,实现对脚本调用(依赖LuaBridge实现)

【C++】使用LuaBridge为Lua绑定C/C++对象,实现对脚本调用 问题: 如何在C++实现对如下脚本读取,在不改变代码的情况下实现修改脚本打开不同链接? <?xml version="1.0" encoding="utf-8"?> <root><script src="lua:lua_demo&quo…...

Java面试——Tomcat

优质博文&#xff1a;IT_BLOG_CN 一、Tomcat 顶层架构 Tomcat中最顶层的容器是Server&#xff0c;代表着整个服务器&#xff0c;从上图中可以看出&#xff0c;一个Server可以包含至少一个Service&#xff0c;用于具体提供服务。Service主要包含两个部分&#xff1a;Connector和…...

2024年7月个人工作生活总结

本文为 2024年7月工作生活总结。 研发编码 “康威定律&#xff08;Conway’s Law&#xff09;”思考 康威定律是 50 年前&#xff08;1967 年&#xff09;由 梅尔文康威 提出的&#xff0c;最初的说法如下&#xff1a; Any organization that designs a system (defined broa…...

快速方便地下载huggingface的模型库和数据集

快速方便地下载huggingface的模型库和数据集 方法一&#xff1a;用于使用 aria2/wgetgit 下载 Huggingface 模型和数据集的 CLI 工具特点Usage 方法二&#xff1a;模型下载【个人使用记录】保持目录结构数据集下载不足之处 方法一&#xff1a;用于使用 aria2/wgetgit 下载 Hugg…...

JAVA小白学习日记Day10

1.线程锁 使用Runnable接口和Lambda表达式&#xff1a; 在 EasyThreadA 类的 mainA 方法中&#xff0c;通过创建 Runnable 实例 run&#xff0c;并使用Lambda表达式。 EasyThreadA::method 绑定到 run 上。然后创建两个线程 a 和 b&#xff0c;分别启动它们&#xff0c;它们会…...

分布式相关理论详解

目录 1.绪论 2.什么是分布式系统&#xff0c;和集群的区别 3.CAP理论 3.1 什么是CAP理论 3.2 一致性 3.2.1 计算机的一致性说明 1.事务中的一致性 2.并发场景下的一致性 3.分布式场景下的一致性 3.2.2 一致性分类 3.2.3 强一致性 1.线性一致性 a) 定义 a) Raft算法…...

Linux基础知识之Shell命令行及终端中的快捷键

1.察看历史命令快捷键 按键 操作 ctrl p 返回上一次输入命令字符 ctrl n 返回下一次输入命令字符 ctrl r 输入单词甚至词组搜索匹配历史命令 alt p 输入字符查找与字符相接近的历史命令 alt . 向之前执行的命令的最后一个参数轮循, 并将之添加到当前光标之后…...

研究生选择学习Android开发的利与弊?

在开始前刚好我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「Android的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&#xff01;产品经理可以学学Axure快…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节&#xff08;如内存地址值没有用二进制&#xff09; 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么&#xff1a;保存在堆中一块区域&#xff0c;同时在栈中有一块区域保存其在堆中的地址&#xff08;也就是我们通常说的该变量指向谁&…...

基于 HTTP 的单向流式通信协议SSE详解

SSE&#xff08;Server-Sent Events&#xff09;详解 &#x1f9e0; 什么是 SSE&#xff1f; SSE&#xff08;Server-Sent Events&#xff09; 是 HTML5 标准中定义的一种通信机制&#xff0c;它允许服务器主动将事件推送给客户端&#xff08;浏览器&#xff09;。与传统的 H…...

【Docker 02】Docker 安装

&#x1f308; 一、各版本的平台支持情况 ⭐ 1. Server 版本 Server 版本的 Docker 就只有个命令行&#xff0c;没有界面。 Platformx86_64 / amd64arm64 / aarch64arm(32 - bit)s390xCentOs√√Debian√√√Fedora√√Raspbian√RHEL√SLES√Ubuntu√√√√Binaries√√√ …...

Windows开机自动启动中间件

WinSW&#xff08;Windows Service Wrapper 是一个开源的 Windows 服务包装器&#xff0c;它可以帮助你将应用程序打包成系统服务&#xff0c;并实现开机自启动的功能。 一、下载 WinSW 下载 WinSW-x64.exe v2.12.0 (⬇️ 更多版本下载) 和 sample-minimal.xml 二、配置 WinS…...