【数据结构(九)】顺序存储二叉树(2)

文章目录

  • 1. 相关概念
  • 2. 顺序存储二叉树的遍历


1. 相关概念

    从数据存储来看,数组存储方式树的存储方式可以相互转换,即数组可以转换成树,树也可以转换成数组,看右面的示意图。

在这里插入图片描述

转换原则:
    1.上图的二叉树的结点,要求以数组的方式来存放 arr:[1, 2, 3, 4, 5, 6, 6]
     2.要求在遍历数组arr 时,仍然可以以前序遍历,中序遍历和后序遍历的方式完成结点的遍历。

顺序存储二叉树的特点:

在这里插入图片描述

① 顺序二叉树通常只考虑 完全二叉树
② 第 n n n 个元素的左子节点的,编号为 2 ∗ n + 1 2 * n + 1 2n+1,(如上图第2个节点(编号为1的节点)的左子节点的编号为2 * 1+1=3)
③ 第 n n n 个元素的右子节点的编号为 2 ∗ n + 2 2 * n + 2 2n+2 ,(如上图第2个节点(编号为1的节点)的右子节点的编号为2 * 1+2=4)
④ 第 n n n 个元素的父节点的编号为 ( n − 1 ) / 2 (n-1) / 2 (n1)/2,(如上图第2个节点(编号为1的节点)的父节点的编号为(1-1)/2=0)
   其中, n n n:表示二叉树中的第几个元素(按 0 开始编号,如上图所示)

2. 顺序存储二叉树的遍历

需求:
    给一个数组 {1,2,3,4,5,6,7},要求以二叉树前序遍历的方式进行遍历。 前序遍历的结果应当为1,2,4,5,3,6,7。

代码实现:

package tree;public class ArrBinaryTreeDemo {public static void main(String[] args) {// TODO Auto-generated method stubint[] arr = { 1, 2, 3, 4, 5, 6, 7 };// 创建一个ArrayBinaryTreeArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);arrBinaryTree.preOrder();//}}//编写一个ArrayBinaryTree,实现顺序存储二叉树遍历class ArrBinaryTree {private int[] arr;// 存储数据节点的数组public ArrBinaryTree(int[] arr) {this.arr = arr;}// 重载preOrderpublic void preOrder() {this.preOrder(0);}// 编写一个方法,完成顺序存储二叉树的前序遍历/*** * @param index 数组的下标*/public void preOrder(int index) {// 如果数组为空,或者arr.length=0if (arr == null || arr.length == 0) {System.out.println("数组为空,不能按照二叉树的前序遍历");}System.out.println(arr[index]);// 向左递归遍历if (index * 2 + 1 < arr.length) {preOrder(2 * index + 1);}// 向右递归遍历if ((index * 2 + 2) < arr.length) {preOrder(2 * index + 2);}}
}

运行结果:

在这里插入图片描述

八大排序算法中的堆排序,就会使用到顺序存储二叉树, 关于堆排序,放在<<树结构实际应用>> 章节讲解。
    
课后练习:
    完成对数组以二叉树中序,后序遍历方式的代码。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/215716.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【深度学习】注意力机制(五)

本文介绍一些注意力机制的实现&#xff0c;包括CSRA/Spatial Shift/Triplet Attention/Coordinate Attention/ACmix。 【深度学习】注意力机制&#xff08;一&#xff09; 【深度学习】注意力机制&#xff08;二&#xff09; 【深度学习】注意力机制&#xff08;三&#xff…

python 实现 AIGC 大模型中的概率论:生日问题的基本推导

在上一节中&#xff0c;我们对生日问题进行了严谨的阐述&#xff1a;假设屋子里面每个人的生日相互独立&#xff0c;而且等可能的出现在一年 365 天中的任何一天&#xff0c;试问我们需要多少人才能让某两个人的生日在同一天的概率超过 50%。 处理抽象逻辑问题的一个入手点就是…

centos 7.9 二进制部署 kubernetes v1.27.7

文章目录 1. 预备条件2. 基础配置2.1 配置root远程登录2.2 配置主机名2.3 安装 ansible2.4 配置互信2.5 配置hosts文件2.6 关闭防firewalld火墙2.7 关闭 selinux2.8 关闭交换分区swap2.9 修改内核参数2.10 安装iptables2.11 开启ipvs2.12 配置limits参数2.13 配置 yum2.14 配置…

css实现姓名两端对齐

1.1 效果 1.2 主要代码 text-align-last: justify; 1.3 html完整代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0&quo…

【LeetCode刷题-树】-- 116.填充每个节点的下一个右侧节点指针

116.填充每个节点的下一个右侧节点指针 方法&#xff1a;层次遍历 /* // Definition for a Node. class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val _val;}public Node(int _val, Node _left, N…

MeterSphere实战(一)

MeterSphere是一位朋友讲到的测试平台&#xff0c;说这东西是开源的&#xff0c;因为我是做测试的&#xff0c;很乐意了解一些新鲜事物。在我看来&#xff0c;测试就是要专注一些领域&#xff0c;然后要啥都会一点点&#xff0c;接着融会贯通起来&#xff0c;这样就可以万变不离…

RCNN 学习

RCNN算法流程 RCNN算法流程可分为4个步骤 一张图像生成1K~2K个候选区域&#xff08;使用Selective Search方法&#xff09;对每个候选区域&#xff0c;使用深度网络图特征特征送入每一类的SVM分类器&#xff0c;判别是否属于该类使用回归期器细修正候选框位置 1.候选区域的生…

漏洞复现-泛微云桥 e-Bridge SQL注入(附漏洞检测脚本)

免责声明 文章中涉及的漏洞均已修复&#xff0c;敏感信息均已做打码处理&#xff0c;文章仅做经验分享用途&#xff0c;切勿当真&#xff0c;未授权的攻击属于非法行为&#xff01;文章中敏感信息均已做多层打马处理。传播、利用本文章所提供的信息而造成的任何直接或者间接的…

C51单片机中reentrant关键字的使用,关于MULTIPLE CALL TO FUNCTION警告的问题

关于可重入关键字reentrant的使用&#xff1a; 现象&#xff1a; 在一个项目中警告信息如下&#xff0c;提示该函数多次调用&#xff0c;因为该函数在串口中断和主循环中都有被调用。 影响&#xff1a; 如果在使用该函数期间被中断打断&#xff0c;而中断也调用了该函数&a…

文件管理和操作工具Path Finder mac功能介绍

Path Finder mac是一款Mac平台上的文件管理和操作工具&#xff0c;提供了比Finder更丰富的功能和更直观的用户界面。它可以帮助用户更高效地浏览、复制、移动、删除和管理文件&#xff0c;以及进行各种高级操作。 Path Finder mac软件功能 - 文件浏览&#xff1a;可以快速浏览文…

node.js和npm的安装与环境配置(2023最新版)

目录 安装node.js测试是否安装成功测试npm环境配置更改环境变量新建系统变量 安装node.js 1、进入官网下载&#xff1a;node.js官网 我选择的是windows64位的&#xff0c;你可以根据自己的实际情况选择对应的版本。 2、下载完成&#xff0c;安装。 打开安装程序 接受协议 选…

学习-面试java基础-(集合)

String 为什么不可变&#xff1f; 1线程安全 2支持hash映射和缓存。因为String的hash值经常会使用到&#xff0c;比如作为 Map 的键&#xff0c;不可变的特性使得 hash 值也不会变&#xff0c;不需要重新计算。 3出于安全考虑。网络地址URL、文件路径path、密码通常情况下都是以…

降低检索系统搭建门槛,轻松实现 RAG 应用!Zilliz Cloud Pipelines 惊喜上线

Zilliz Cloud 正式上线 Pipelines&#xff01; Zilliz Cloud Pipelines 可以将文档、文本片段和图像等非结构化数据转换成可搜索的向量并存储在 Collection 中&#xff0c;帮助开发者简化工程开发&#xff0c;助力其实现多种场景的 RAG 应用&#xff0c;将复杂生产系统的搭建和…

【已解决】SpringBoot Maven 打包失败:class lombok.javac.apt.LombokProcessor 错误

文章目录 出错原因解决办法总结 最新项目部署的时候&#xff0c;出现了一个maven打包失败的问题&#xff0c;主要是lombok这个组件出的问题&#xff0c;具体的错误信息如下&#xff1a; 我的lombok版本如下&#xff1a; <dependency><groupId>org.projectlombok&l…

Editplus安装教程(附带汉化教程与获取注册码教程)

文章目录 前言一、Editplus简介1. 简介2. 特点和功能 二、Editplus5安装步骤1. 下载EditPlus52. 运行安装程序3. 接受许可协议4. 选择安装位置5. 选择组件6. 完成安装7. 启动EditPlus8. 注册EditPlus 三、Editplus4安装步骤1. 下载EditPlus42. 安装EditPlus43. 注册码获取 四、…

代码随想录算法训练营 | day48 动态规划 198.打家劫舍,213.打家劫舍Ⅱ,337.打家劫舍Ⅲ

刷题 198.打家劫舍 题目链接 | 文章讲解 | 视频讲解 题目&#xff1a;你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金&#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统&#xff0c;如果两间相邻的房屋在同一晚上被…

python实战演练之迎接冬至的第一场雪

写在前面 WINTER IS COMING Python实现大雪纷飞的效果&#xff0c;完整代码在文末哦~ 准备开始 WINTER IS COMING Python是一种高级编程语言&#xff0c;Turtle是Python的一个图形化模块&#xff0c;它可以帮助学习者更好地理解编程概念&#xff0c;同时可以进行图形化编程。 …

论文笔记:A review on multi-label learning

一、介绍 传统的监督学习是单标签学习&#xff0c;但是现实中一个实例可能对应多个标签。这篇文章介绍了多标签分类的定义和评价指标、多标签学习的算法还有其他相关的任务。 二、问题相关定义 2.1 多标签学习任务 假设 X R d X R^d XRd&#xff0c;表示d维的输入空间&am…

C# WPF上位机开发(简易图像处理软件)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 图像处理是工业生产重要的环节。不管是定位、测量、检测还是识别&#xff0c;图像处理在工业生产中扮演重要的角色。而c#由于自身快速开发的特点&a…

Python网络爬虫环境的安装指南

网络爬虫是一种自动化的网页数据抓取技术&#xff0c;广泛用于数据挖掘、信息搜集和互联网研究等领域。Python作为一种强大的编程语言&#xff0c;拥有丰富的库支持网络爬虫的开发。本文将为你详细介绍如何在你的计算机上安装Python网络爬虫环境。 一、安装python开发环境 进…