数据结构-顺序存储二叉树
文章目录
目录
文章目录
前言
一 . 什么是顺序存储二叉树
二 . 模拟实现
前序遍历
总结
前言
大家好,今天给大家讲一下顺序存储二叉树
一 . 什么是顺序存储二叉树
顺序存储二叉树是一种将二叉树的节点按照从上到下、从左到右的顺序存储在数组中的方法。具体来说,顺序存储二叉树将二叉树的根节点存储在数组的第一个位置,然后按照从上到下、从左到右的顺序将二叉树的其他节点依次存储在数组中。
对于任意一个节点的索引为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,命…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...

