语言的数据结构:树与二叉树(二叉树篇)
语言的数据结构:树与二叉树(二叉树篇)
- 前言
- 概念
- 特别的二叉树
- 满二叉树
- 完全二叉树
- 存储结构
- 顺序存储
- 链式存储
- 查找方式
前言
上文说到了树,有人认为二叉树是树的每一个分支都有两个子节点。其实这也对。但二叉树在此基础上还做了限制。比如区别了左子树与右子树。也就是说,当二叉树的根只有一个孩子时,也需要知道这个是左孩子还是右孩子。就是因为这个原因,让二叉树的性能相对于树有了明显的提高。也让二叉树成了一个全新的概念,而不是树的一个特别情况而已。
概念
二叉树(Binary Tree) 是树的一种常见形式,它是一棵有序树。它的子节点最多只有两个,分为左子树和右子树,哪怕只有一个子节点,也要区分出是左子树还是右子树,如果颠倒了,就是一棵新的二叉树了。二叉树的度最大为2。
二叉树常被用于实现二叉查找树和二叉堆,树的很多问题都可以通过 B F S 广度优先搜索算法 \color{orange} BFS广度优先搜索算法 BFS广度优先搜索算法或 D F S 深度优先搜索算法( D e p t h F i r s t S e a r c h ) \color{orange}DFS深度优先搜索算法(Depth First Search) DFS深度优先搜索算法(DepthFirstSearch)解决。
特别的二叉树
满二叉树
一个二叉树,如果它有子节点,并且子节点数都是最大值( 在每一层上没有空缺的位置 \color{orange}在每一层上没有空缺的位置 在每一层上没有空缺的位置),则称为满二叉树。一个满二叉树,除了根节点,其余节点数都是2个一起出现的,如 B与C、D与E、F与G。 所以如果满二叉树的层级为K,则
节点数 : 2 k − 1 \ 2^k-1 2k−1 。这个 -1,就是因为根节点只有一个。
如果节点数为N,则
高度 : h = l o g 2 ( N + 1 ) log_2(N+1) log2(N+1)

完全二叉树
满二叉树是完全二叉树特殊情况,当满二叉树从最后的节点依次减少时,形成的就是完全二叉树。完全二叉树从根节点、左子树、右子树的顺序执行,一直到树结束都没有空缺的节点。


存储结构
顺序存储
可以使用数组来存储。但只适用于满二叉树和完全二叉树的情况。否则如果中间缺失了节点,在数组中相应的位置就要空在那里,造成了空间的浪费。之所以F的位置要空在这里,是因为G是C的右子树,而左子树是没有节点的。如果那个位置不空着,则G就表示为左子树了。这也就是用数组存储的不好之处了。
链式存储
用链表来创建树结构。注意:此时用链表来表示树,并非说此时的树就是线性结构。而是用链表重新去定义一种数据结构。此时这个结构只能称作树,而不可以称作链表。
用链表创建树的好处就是左子树与右子树的表示。如上面的示例,直接在每个节点上存储三个信息:1、数据本身的信息,2、左子树的指针,3、右子树的指针。这时G就直接可以表示为C的右子树,而其左子树指向NULL。
// 二叉树节点的结构体定义
typedef struct TreeNode { int val; // 节点的值 struct TreeNode *left; // 左子树 struct TreeNode *right; // 右子树
} TreeNode;
查找方式
对二叉树的查找有三种方式,是按照查找根的点的顺序来区分的。 先序 \color{orange}先序 先序(根节点、左子树、右子树), 中序 \color{orange}中序 中序(左子树、根节点、右子树), 后序 \color{orange}后序 后序(左子树、右子树、根节点)。
前序的访问顺序:A B D E C G
中序的访问顺序:D B E A C G
后序的访问顺序:D E B G C A
相关文章:
语言的数据结构:树与二叉树(二叉树篇)
语言的数据结构:树与二叉树(二叉树篇) 前言概念特别的二叉树满二叉树完全二叉树 存储结构顺序存储链式存储 查找方式 前言 上文说到了树,有人认为二叉树是树的每一个分支都有两个子节点。其实这也对。但二叉树在此基础上还做了限…...
若以框架学习(3),echarts结合后端数据展示,暂时完结。
前三天,参加毕业典礼,领毕业证,顿时感到空落落的失去感,没有工作,啥也没有,总感觉一辈子白活了。晚上ktv了一晚上,由于我不咋个唱歌,没心情,听哥几个唱了一晚上周杰伦&am…...
Spring Boot循环依赖(解决)
类与类之间的依赖关系形成了闭环,就会导致循环依赖问题的产生。举例来说,假设存在两个服务类A和服务类B,如果A通过依赖注入的方式引用了B,且B通过依赖注入的方式引用了A,那么A和B之间就存在循环依赖。 换成如下方法获…...
emqx4.4.3关于如何取消匿名登录,添加认证用户这件事
emqx4.4.3如何取消匿名登录,添加认证用户 emqx版本:4.4.3 背景:使用docker搭建完emqx后,使用 MQTTX 连接总是超时: 检查Java项目 是否有接口:https://XXXX:80/mqtt/auth? 若有,则具体逻辑查询…...
七天速通javaSE:第三天 程序控制结构:练习题
文章目录 前言一、基础1.计算从0~100之间奇数之和和偶数之和2. 用for循环输出0~1000之间能被5整除的数,每行输出三个 二、进阶1. 九九乘法表2.等边三角形 前言 本文主要讲解三种基本程序控制结构的练习题,以期熟练掌握顺序、选择、循环三种基本结构 一、…...
新增题目接口开发
文章目录 1.基本设计2.生成CRUD代码1.生成五张表的代码1.subject_info2.subject_brief3.subject_judge4.subject_multiple5.subject_radio 2.将所有的dao放到mapper文件夹3.将所有实体类使用lombok简化4.删除所有mapper的Param("pageable") Pageable pageable5.删除所…...
国内怎样使用GPT4 turbo
GPT是当前最为熟知的大模型,它优越的性能一直遥遥领先于其它一众厂商,然而如此优秀的AI在中国境内却是无法正常使用的。本文将告诉你4种使用gpt4的方法,让你突破限制顺利使用。 官方售价是20美元/月,40次提问/3小时,需…...
【语义分割】1-标注数据集-【单张图片】labelme标注json文件转mask
声明:我学习了b站:标注自己的语义分割数据集_哔哩哔哩_bilibili 并且复现了,记录了所思所得。 主要是说了: 做语义分割,数据集怎么用labelme标注成json文件,以及,json文件怎么转成mask 流程…...
c++: 理解编译器在背后所做的工作-工具篇
理解C模板以及编译器的优化是深入掌握C编程的重要部分。有一些其他工具和技术可以帮助你更好地理解编译器在背后所做的工作,特别是优化方面。以下是一些有用的工具和技术: 1. Compiler Explorer (Godbolt) Compiler Explorer 是一个非常流行的在线工具…...
Verilog HDL语法入门系列(三):Verilog的语言操作符规则(上)
目录 1.操作符优先级2.Verilog中的大小(size)与符号3.算术操作符4.按位操作符5.逻辑操作符6.逻辑反与位反的对比 微信公众号获取更多FPGA相关源码: 1.操作符优先级 下表以优先级顺序列出了Verilog操作符。 2.Verilog中的大小(size)与符号 Verilog根据表达式中变…...
IT营大地老师是谁,怎么什么都会?
很多学员都很好奇大地老师到底是谁,怎么什么都会?每过一段时间就会出一门新课程,涉足深耕不同的领域。经反馈常有童鞋私聊IT营官网客服咨询这个问题,也有很多人在b站大地老师的免费课程里私信,有好奇也有崇拜ÿ…...
【python013】pyinstaller打包PDF提取脚本为exe工具
1.在日常工作和学习中,遇到类似问题处理场景,如pdf文件核心内容截取,这里将文件打包成exe可执行文件,实现功能简便使用。 2.欢迎点赞、关注、批评、指正,互三走起来,小手动起来! 3.欢迎点赞、关…...
VUE div的右上角的角标/标签
一、效果图 二、代码 <div class"comp-overview"><div class"overview-item" v-for"(item,index) in overviewInfoList" :key"index"><div class"angle_mark"><span>{{item.label}}</span>&…...
WPS复制后转置粘贴
1. WPS复制后转置粘贴 复制-》右键-》顶部第一行-》粘贴行列转置,如下图: 2. Excel office365 本地版 2. Excel office365 在线版...
Shell编程之正则表达式与文本处理器
一,正则表达式 1:正则表达式概述 1.正则表达式的定义 正则表达式(Regular Expression,RegEx)是一种高度灵活的文本处理工具,它结合了字符序列、特殊控制字符(称为元字符)、以及特定…...
linux文本粘贴格式错乱的问题
vi/vim :set paste然后再 insert, 粘贴...
第二节课 6月13日 ssh密钥登陆方式
centos和ubuntu openssh服务的初始安装 一、实验:ubuntu系统激活root用户 ubuntu系统如何激活root用户,允许root用户ssh登陆? 1、ubuntu默认root用户未设置密码,未激活 激活root用户,设置root密码 sudo passwd roo…...
图书馆借阅表
DDL 用户表 (Users) 图书表 (Books) 图书类别表 (BookCategories) 图书与类别关联表 (BookCategoryRelations) 借阅记录表 (BorrowRecords) 供应商表 (Suppliers) 采购记录表 (PurchaseRecords) CREATE TABLE Users (user_id INT PRIMARY KEY AUTO_INCREMENT,username …...
云动态摘要 2024-06-25
给您带来云厂商的最新动态,最新产品资讯和最新优惠更新。 最新产品更新 Web应用防火墙 - 验证码支持微信小程序接入 阿里云 2024-06-25 支持客户从微信小程序场景下接入,提供人机识别的安全防护。 工业数字模型驱动引擎 - iDME控制台换新升级 华为云…...
Docker编译nanopc-t4源码流程介绍
官方文档 Android系统编译 vnc加环境变量配置 https://github.com/friendlyarm/docker-cross-compiler-novnc 下载 git clone https://github.com/friendlyarm/docker-ubuntu-lxde-novnc cd docker-ubuntu-lxde-novnc docker build --no-cache -t docker-ubuntu-lxde-novnc …...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
