数据结构-顺序存储二叉树
文章目录
目录
文章目录
前言
一 . 什么是顺序存储二叉树
二 . 模拟实现
前序遍历
总结
前言
大家好,今天给大家讲一下顺序存储二叉树
一 . 什么是顺序存储二叉树
顺序存储二叉树是一种将二叉树的节点按照从上到下、从左到右的顺序存储在数组中的方法。具体来说,顺序存储二叉树将二叉树的根节点存储在数组的第一个位置,然后按照从上到下、从左到右的顺序将二叉树的其他节点依次存储在数组中。
对于任意一个节点的索引为i(i从1开始),其左子节点的索引为2i,右子节点的索引为2i+1。这样,通过数组的索引关系,可以方便地找到节点的父节点、左子节点和右子节点。
顺序存储二叉树的优点是可以使用数组的随机访问特性快速找到节点,不需要通过指针进行遍历。缺点是当二叉树的节点数较少时,可能会浪费较多的存储空间。此外,如果二叉树需要进行频繁的插入和删除操作,顺序存储二叉树的效率会较低。

顺序存储二叉树的特点:
1)顺序二叉树通常只考虑完全二叉树
2)第n个元素的左子节点为 2 * n + 1
3)第n个元素的右子节点为 2 * n + 2
4)第n个元素的父节点为 (n-1) / 2
5)n : 表示二叉树中的第几个元素(按0开始编号如上图所示)
二 . 模拟实现
准备工作
// 编写一个ArrBinaryTree类,实现顺序存储二叉树遍历
class ArrBinaryTree{private int[] arr;// 存放数据节点的数组public ArrBinaryTree(int[] arr){this.arr = arr;}}
需求: 给你一个数组{1,2,3,4,5,6,7} 要求以二叉树前中后序遍历的方式进行遍历

前序遍历
思路分析
- 定义一个指针变量index,初始值为1,表示从根节点开始遍历。
- 从数组中取出索引为index的节点,并对其进行操作(如打印节点值)。
- 将index的值更新为其左子节点的索引,即index = 2 * index。
- 重复步骤2和步骤3,直到index超出数组的范围或者取出的节点为空。
- 如果index超出数组的范围,则遍历结束;否则,将index的值更新为其右子节点的索引,即index = 2 * index + 1。
- 重复步骤2到步骤5,直到index超出数组的范围。
代码实现
public void preOrder(int index){// 如果数组为空或array.length == 0,直接返回if(arr == null || arr.length == 0){System.out.println("二叉树为空");return;}System.out.println(arr[index]);// 左递归if(index*2+1 < arr.length){preOrder(2*index+1);}// 右递归if(index*2+2 < arr.length){preOrder(index*2 +2);}}
过程图解

中序遍历和后序遍历过程和上图无本质区别,直接看代码
/*** 顺序存储二叉树中序遍历* @param index 数组下标*/public void infixOrder(int index) {// 如果数组为空或array.length == 0,直接返回if (arr == null || arr.length == 0) {System.out.println("二叉树为空");return;}// 左递归if(index*2+1 < arr.length){preOrder(2*index+1);}System.out.println(arr[index]);// 右递归if(index*2+2 < arr.length){preOrder(index*2 +2);}}/*** 顺序存储二叉树后序遍历* @param index 数组下标*/public void postOrder(int index){// 如果数组为空或array.length == 0,直接返回if (arr == null || arr.length == 0) {System.out.println("二叉树为空");return;}// 左递归if(index*2+1 < arr.length){preOrder(2*index+1);}if(index*2+2 < arr.length){preOrder(index*2 +2);}System.out.println(arr[index]);// 右递归}
总结
大家根据图解过程应该很好理解,没什么难点,我们下一篇博客见。
相关文章:
数据结构-顺序存储二叉树
文章目录 目录 文章目录 前言 一 . 什么是顺序存储二叉树 二 . 模拟实现 前序遍历 总结 前言 大家好,今天给大家讲一下顺序存储二叉树 一 . 什么是顺序存储二叉树 顺序存储二叉树是一种将二叉树的节点按照从上到下、从左到右的顺序存储在数组中的方法。具体来说,顺…...
mysql学习实践
这里写目录标题 查找重复数据查找重复数据的字段值以及重复的次数如果你只想查找重复数据,而不需要知道重复的次数,可以简化查询如下 根据某个字段查询重复的数据,并取id最大的那条数据(用于商机列表展示)将逗号分隔的…...
键盘控制应用--通过键盘发送控制指令
系列文章目录 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 TODO:写完再整理 文章目录 系列文章目录前言代码原理实现前言 认知有限,望大家多多包涵,有什么问题也希望能够与大家多交流,共同成长! 本文先对键盘控制应用做个简单的介绍,具体内容后…...
python中pytorch的广播机制——Broadcasting
广播机制 numpy 在算术运算期间采用“广播”来处理具有不同形状的 array ,即将较小的阵列在较大的阵列上“广播”,以便它们具有兼容的形状。Broadcasting是一种没有copy数据的expand 不过两个维度不相同,在前面插入维度1扩张维度1到相同的维…...
基于BES平台音乐信号处理之DRC算法实现
基于BES平台音乐信号处理之DRC算法实现 是否需要申请加入数字音频系统研究开发交流答疑群(课题组)?加我微信hezkz17, 本群提供音频技术答疑服务 1 DRC实现 drc.h 2 调用 audio_process.c 3 DRC动态范围控制算法在音乐信号处理中的位置 4 DRC具体细节源码 可参考…...
如何加快香山处理器Chisel->Verilog编译速度
graalvm installation 更换JVM。我们推荐使用GraalVM代替OpenJDK。 使用GraalVM免费版作为JVM编译香山比OpenJDK快10%-20%。 -------------------------------------------------------------------------- https://www.graalvm.org/latest/docs/getting-started/linux/ downl…...
pillow篇---pillow连续打开同一张图片会导致打开失败问题
如果你需要在多次操作同一张图像时避免出现缓存问题,你可以使用 Image.open() 方法的 seek() 方法将文件指针移动到图像数据的开头,以便重新读取图像数据。示例如下: from PIL import Image# 打开图像文件 image Image.open(example.jpg)# …...
详细解说iptables 高阶用法,用来完成哪些高效率网络路由策略场景,iptables 实现域名过滤,Linux如何利用iptables屏蔽某些域名?
详细解说iptables 高阶用法,用来完成哪些高效率网络路由策略场景,iptables 实现域名过滤,Linux如何利用iptables屏蔽某些域名? Linux利用iptables屏蔽某些域名 以下规则是屏蔽以 youtube.com 为主的所有一级 二级 三级等域名。 iptables -A OUTPUT -m string --string &qu…...
面试总结-Redis篇章(十二)——Redis是单线程的,为什么还那么快
Redis是单线程的,为什么还那么快 Redis是单线程的,为什么还那么快什么是IO多路复用 阻塞IO非阻塞IOIO多路复用 Redis是单线程的,为什么还那么快 Redis是纯内存操作,执行速度非常快采用单线程,避免不必要的上下文切换可…...
5.编写程序 超强力方法
5.1 创建战舰游戏 创建一个类似战舰的游戏:攻击网站 有一种棋盘类的战舰游戏,目标是要猜测对方战舰的坐标,然后轮流开炮攻击,命中数发就可以打沉对方的战舰。不过我们不喜欢战争,只要打垮这些达康公司就好(因为与商业…...
超详细DeepLabv3 介绍与使用指南 – 使用 PyTorch 推理
DeepLab 模型首次在 ICLR 14 中首次亮相,是一系列旨在解决语义分割问题的深度学习架构。经过多年的迭代改进,谷歌研究人员的同一个团队在 17 年底发布了广受欢迎的“DeepLabv3”。当时,DeepLabv3 在 Pascal VOC 2012 测试集上实现了最先进的 (SOTA) 性能,在著名的 Cityscap…...
移动应用-Android-开发指南
Android-UI开发指南 Android Studio调试UI设计UI框架布局Layout文本框 android的活动Activity基本概念Activity的生命周期Activity栈创建Activity管理ActivityActivity间传递数据 FragmentAdapterRecyclerViewRecyclerView Adapter(适配器)事件setOnItem…...
免费开源的非标项目型制造BOM一键导入方案介绍
非标项目型制造,每一个订单都会引入很多新料号、新BoM、新工艺路线。实施ERP/MES系统,实现生产管理数字化,第一步就是要导入这些料号、BoM和工艺。项目型制造,大多数订单只生产一次。但在ERP/MES系统中,订单的料号、Bo…...
用合成数据训练车辆姿态估计神经网络
我们的客户希望开发一款应用程序,引导用户通过 AR 指南和自动照片拍摄来拍摄更高质量的汽车照片。 本文重点介绍构建汽车姿态估计组件的技术。 在应用程序中,用户被引导站在与汽车一定的角度和距离,以标准化的方式捕捉最好的照片。 当用户处于…...
【QT开发笔记-基础篇】| 第四章 事件QEvent | 4.5 键盘事件
本章要实现的整体效果如下: QEvent::KeyPress 键盘按下时,触发该事件,它对应的子类是 QKeyEvent QEvent::KeyRelease 键盘抬起时,触发该事件,它对应的子类是 QKeyEvent 本节通过两个案例来讲解这 2 个事件&…...
爬取微博热榜并将其存储为csv文件
🙌秋名山码民的主页 😂oi退役选手,Java、大数据、单片机、IoT均有所涉猎,热爱技术,技术无罪 🎉欢迎关注🔎点赞👍收藏⭐️留言📝 获取源码,添加WX 目录 前言1.…...
国庆中秋特辑(八)Spring Boot项目如何使用JPA
国庆中秋特辑系列文章: 国庆中秋特辑(八)Spring Boot项目如何使用JPA 国庆中秋特辑(七)Java软件工程师常见20道编程面试题 国庆中秋特辑(六)大学生常见30道宝藏编程面试题 国庆中秋特辑&…...
用jad反编译工具查看java接口相关的默认修饰符
接口抽象类复习 -> 默认修饰符是啥 -> jad反编译证明 https://www.cnblogs.com/changrunwei/p/6618117.html 文章目录 背景操作过程反编译前后对比操作截图结论 背景 今天刷到这篇文章,想起之前笔试题总是记不清,所以想证明下。 之前一直不清楚要…...
axios的get请求时数组参数没有下标
开发新项目过程中 发现get请求时 数组参数没有下标 这样肯定是不行的 后端接口需要数组[0]: 7 数组[1]:4这样的数据 原因是因为在请求拦截器没有处理需要的参数 解决方法 在请求拦截器 处理一下参数 import axios, { AxiosError, AxiosInstance, AxiosRequestHeaders } fro…...
bochs 对 Linux0.11 进行调试 (TODO: 后面可以考虑集成 vscode+gdb+qemu)
我在阅读 Linux0.11 源码时,对一个指令 LDS 感到困惑。 看了下 intel 指令集手册,能猜到 LDS 的功能,但不确定。 于是决定搭建调试环境,看看 LDS 的功能是否真如自己猜测。 首先 make debug 运行 qemu-Linux0.11,命…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...
STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

