数据结构和算法-树与二叉树的存储结构以及树和二叉树和森林的遍历

文章目录

  • 二叉树的存储结构
    • 二叉树的顺序存储
    • 二叉树的链式存储
    • 小结
  • 二叉树的先中后序遍历
    • 例题
    • 小结
  • 二叉树的层次遍历
    • 小结
  • 由遍历序列构造二叉树
    • 一个遍历序列即使给定了前中后序，也不能确定该二叉树的形态
    • 可以确定的序列组合
      • 前序+中序
      • 后序+中序
      • 层序+中序
    • 小结
    • 若前序，后序，层序两两组合能吗？
  • 树的存储结构
    • 总览
    • 树的逻辑结构
    • 顺序存储（双亲表示法）
    • 顺序+链式存储（孩子表示法）
    • 链式存储（孩子兄弟表示法）
    • 森林和二叉树的转换（孩子兄弟表示法）
    • 小结
  • 树和森林的遍历
    • 树的先根遍历
    • 树的后根遍历
    • 树的层次遍历
    • 森林的先序遍历
    • 森林的中序遍历
    • 小结

二叉树的存储结构

二叉树的顺序存储

在这里插入图片描述

i所在的层次可回顾上面二叉树的性质
在这里插入图片描述

通过计算出节点对应左孩子或右孩子的节点数然后判断是否在n个节点的范围内
在这里插入图片描述
当非完全二叉树时不适用了，如下图，节点与编号不对应了

在这里插入图片描述

所以，还是按照原来的对应图来存储。判断节点存不存在通过判断是否空的布尔值即可
在这里插入图片描述
弊端：会浪费部分节点
在这里插入图片描述

二叉树的链式存储

n个节点肯定会有n-1个指针域不为空，n+1个指针域为空。
n-1是有n-1条线连接两个节点，所以对应的指针域中也会有n-1个不为空的指针域
在这里插入图片描述
常用的操作
在这里插入图片描述
寻找某个节点的父节点时，需要遍历整个数，依次判断是否某个节点的子节点为对应的节点。
此时节点结构体中加上父节点指针可以避免遍历

在这里插入图片描述

小结

在这里插入图片描述
在这里插入图片描述

二叉树的先中后序遍历

在这里插入图片描述

感觉先中后序主要是根的遍历位置在前中后

在这里插入图片描述

有点递归的思想在里面
先找到根，然后开始按对应的序遍历，如果左右中存在不是叶子节点，则将该节点当作根节点继续按对应的序来遍历

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

例题

在这里插入图片描述

小结

在这里插入图片描述

二叉树的层次遍历

核心：队列非空则头节点出队并访问该节点且将其左，右孩子插入队尾（判断是否有，有的话则插入）
在这里插入图片描述
在这里插入图片描述

小结

在这里插入图片描述

由遍历序列构造二叉树

一个遍历序列即使给定了前中后序，也不能确定该二叉树的形态

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

可以确定的序列组合

在这里插入图片描述

前序+中序

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

后序+中序

都是先判断根结点
在这里插入图片描述
在这里插入图片描述

层序+中序

在这里插入图片描述
在这里插入图片描述

小结

核心：找根节点
在这里插入图片描述

若前序，后序，层序两两组合能吗？

在这里插入图片描述
无法确定，一定要有中序才行

树的存储结构

总览

在这里插入图片描述

树的逻辑结构

在这里插入图片描述

顺序存储（双亲表示法）

在这里插入图片描述
在这里插入图片描述

顺序+链式存储（孩子表示法）

存在指向孩子链表的指针的元素
在这里插入图片描述

链式存储（孩子兄弟表示法）

在这里插入图片描述
左孩子都是原本的孩子节点，右孩子都是原本的兄弟节点
所以B的右孩子的遍历下去的所有右孩子为原来A节点的孩子
在这里插入图片描述

森林和二叉树的转换（孩子兄弟表示法）

把兄弟节点都连起来，然后把兄弟节点与父节点的连线断了就成了
在这里插入图片描述

在这里插入图片描述

小结

在这里插入图片描述

树和森林的遍历

树的先根遍历

类似二叉树的先序遍历 根 左 右
对应的二叉树即对应的孩子兄弟法表示的树且该二叉树的先序遍历与原树的先根遍历相同
在这里插入图片描述

树的后根遍历

类似二叉树的后序遍历 左 右 根
对应的二叉树即对应的孩子兄弟法表示的树且该二叉树的中序遍历与原树的后根遍历相同
在这里插入图片描述

树的层次遍历

后根和先根遍历为深度优先遍历
层次遍历为广度优先遍历
在这里插入图片描述

森林的先序遍历

在这里插入图片描述
或把森林先转化为二叉树
在这里插入图片描述

森林的中序遍历

在这里插入图片描述
或转换为二叉树
在这里插入图片描述

小结

在这里插入图片描述

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

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

相关文章

构建第一个ArkTS应用（纯HarmonyOS应用）

构建第一个ArkTS应用（纯HarmonyOS应用）

1. 安装开发工具 在华为开发者官方上下载HarmonyOS应用专用的开发工具，链接地址：HUAWEI DevEco Studio和SDK下载和升级 | HarmonyOS开发者 要想使用开发工具让项目跑起来，需要10G的磁盘空间。开发工具需要的磁盘空间为2.36G；SDK需…
阅读更多...
springBoot整合task

springBoot整合task

springBoot整合task 文章目录 springBoot整合task开开关设置任务，并设置执行周期定时任务的相关配置 开开关 设置任务，并设置执行周期 Component public class MyBean {Scheduled(cron "0/1 * * * * ?")public void print(){System.out.prin…
阅读更多...
Shutdown Signal: channel error； protocol method: #method＜channel.close＞

Shutdown Signal: channel error； protocol method: #method＜channel.close＞

完整异常信息&#xff1a; Shutdown Signal: channel error; protocol method: #method<channel.close>(reply-code404, reply-textNOT_FOUND - no exchange fanoutExchange in vhost /, class-id60, method-id40) 意思是找不到名字是 fanoutExchange 的虚拟机 就是虚拟机…
阅读更多...
JVM基础篇：垃圾回收

JVM基础篇：垃圾回收

目录 1.前言 1.1C/C的内存管理 1.2Java的内存管理 2.方法区的回收 3.堆回收 3.1引用计数法和可达性分析法 3.2五种对象引用 强引用 软引用 弱引用 虚引用 终结器引用 3.3垃圾回收算法评价标准 ①吞吐量 ②最大暂停时间 ③堆使用效率 3.4垃圾回收算法 ①标记清…
阅读更多...
RabbitMQ 笔记

RabbitMQ 笔记

Message durability 确保消息在server 出现问题或者recovery能恢复&#xff1a; declare it as durable in the producer and consumer code. boolean durable true; channel.queueDeclare("hello", durable, false, false, null);Queue 指定 //使用指定的queue&…
阅读更多...
【古月居《ros入门21讲》学习笔记】14_参数的使用与编程方法

【古月居《ros入门21讲》学习笔记】14_参数的使用与编程方法

目录 说明&#xff1a; 1. 参数模型&#xff08;全局字典&#xff09; 2. 实现过程&#xff08;C&#xff09; 创建功能包 参数命令行的使用 YAML参数文件 rosparam命令 使用示例 编程方法&#xff08;C&#xff09; 配置代码编译规则 编译并运行 编译 运行 3. 实…
阅读更多...
基于springboot + vue体育馆使用预约平台

基于springboot + vue体育馆使用预约平台

qq&#xff08;2829419543&#xff09;获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;springboot 前端&#xff1a;采用vue技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xf…
阅读更多...
Wireshark 协议插件Lua开发 -数据包内嵌协议的解释

Wireshark 协议插件Lua开发 -数据包内嵌协议的解释

概述 因为公司项目涉及的协议打包&#xff0c;协议包内又嵌了一层IP包的奇葩套娃结构&#xff0c;为了方便抓包调试&#xff0c;利用Wireshark的协议插件开发功能&#xff0c;写了一个插件&#xff0c;博文记录以备忘。 环境信息 Wireshark 4.0.3 协议结构体套娃图 插件安装…
阅读更多...
C++基础 -35- string类

C++基础 -35- string类

string类的格式 string a;如下图&#xff0c;使用string类比常规的字符串处理方便很多 而且需要进行的字符串处理&#xff0c;在类中都能完成 #include "iostream"using namespace std;extern "C" {#include "string.h" }int main() {//c的写…
阅读更多...
从零开始：PHP实现阿里云直播的简单方法！

从零开始：PHP实现阿里云直播的简单方法！

1. 配置阿里云直播的推流地址和播放地址 使用阿里云直播功能前&#xff0c;首先需要在阿里云控制台中创建直播应用&#xff0c;然后获取推流地址和播放地址。 推流地址一般格式为&#xff1a; rtmp://{Domain}/{AppName}/{StreamName}?auth_key{AuthKey}-{Timestamp}-{Rand…
阅读更多...
C# 使用HtmlAgilityPack解析提取HTML内容

C# 使用HtmlAgilityPack解析提取HTML内容

写在前面 HtmlAgilityPack是一个HTML解析类库&#xff0c;日常用法就是爬虫获取到内容后&#xff0c;先用XPath获取目标节点&#xff0c;再用正则进行匹配&#xff1b;使用XPath的目的主要是将目标节点或内容限定在一个较小的范围&#xff0c;如果一上来就用正则那效率肯定不…
阅读更多...
Git Bash环境下用perl脚本获取uuid值

Git Bash环境下用perl脚本获取uuid值

在Linux环境下&#xff0c;比如在ubuntu就直接有uuidgen命令直接获取uuid值。在Windows环境下常用的git bash中没有对应的命令&#xff0c;略有不便。这里用脚本写一个uuidgen&#xff0c;模拟Linux环境下的uuidgen命令。 #! /usr/bin/perl use v5.14; use Win32;sub uuidGen {…
阅读更多...
Windows驱动中校验数字签名(使用 ci.dll)

Windows驱动中校验数字签名(使用 ci.dll)

1.背景 对于常规应用程序来说&#xff0c;校验数字签名认证在应用层可以使用 WinVerifyTrust, 在驱动层使用常规的 API无法使用&#xff0c;自己分析数据又太麻烦。 在内核中 ci.dll 包装了数据签名验证相关的功能&#xff0c;我们可以使用该 dll 来实现我们的数字签名验证。 详…
阅读更多...
Blender学习笔记：小车狂奔动画

Blender学习笔记：小车狂奔动画

文章目录 路旁小树汽车尾气移动 教程地址&#xff1a;八个案例教程带你从0到1入门blender【已完结】 小车建模 路旁小树 1 添加摄像机&#xff0c;在小车下面拉一个平面&#xff0c;覆盖到摄像机的观察视窗。复制一层平面&#xff0c;收窄变成小车两侧的路面&#xff0c;编辑…
阅读更多...
vue使用实现录音功能js-audio-recorder

vue使用实现录音功能js-audio-recorder

前言 最近项目中需要实现一个录音上传功能&#xff0c;用于语音评论可以上录音。 下载插件&#xff1a; npm i js-audio-recorder完整代码 <template><div style"padding: 20px;"><h3>录音上传</h3><div style"font-size:14px"…
阅读更多...
图推理：忠实且可解释的大型语言模型推理11.29

图推理：忠实且可解释的大型语言模型推理11.29

推理&#xff1a;忠实且可解释的大型语言模型推理 摘要1 引言&#xff12; 相关工作3 准备工作4 方法4.1 图推理&#xff1a;规划-检索-推理4.2 优化框架4.3 规划模块4.4 检索推理模块 5 实验5.1 实验设置5.2 RQ1&#xff1a;KGQA 性能比较 摘要 大型语言模型&#xff08;LLM&…
阅读更多...
python爬虫AES魔改案例：某音乐素材下载网

python爬虫AES魔改案例：某音乐素材下载网

声明&#xff1a; 该文章为学习使用&#xff0c;严禁用于商业用途和非法用途&#xff0c;违者后果自负&#xff0c;由此产生的一切后果均与作者无关 一、找出需要加密的参数 js运行 atob(‘aHR0cHM6Ly93d3cuYWlnZWkuY29tL3NvdW5kL2NsYXNzLw’) 拿到网址&#xff0c;F12打开调…
阅读更多...
二.运算符

二.运算符

运算符 1.算术运算符2.比较运算符3.逻辑运算符 1.算术运算符 算数运算符主要用于数学运算&#xff0c;其可以连接运算符前后的两个数值或表达式&#xff0c;对数值或表达式进行 - * / 和 取模%运算 1.加减法运算符 mysql> SELECT 100,100 0,100 - 0,100 50,100 50 - …
阅读更多...
制作一个RISC-V的操作系统一-计算机系统漫游

制作一个RISC-V的操作系统一-计算机系统漫游

文章目录 计算机的硬件组成两种架构程序的存储与执行程序语言的设计和进化一个mini计算机 编程语言的进化存储设备的层次结构操作系统 计算机的硬件组成 所有硬件由总线连接起来 两种架构 总线个数不同&#xff0c;Memory储存内容不同 程序的存储与执行 首先编译和链接某…
阅读更多...
windows11 调整鼠标灵敏度方法

windows11 调整鼠标灵敏度方法

首先 我们打开电脑设置 或者在 此电脑/此计算机/我的电脑 右击选择属性 然后 有的电脑 左侧菜单中 直接就有 设备 然后在设备中直接就可以找到 鼠标 选项 调整光标速度即可 如果操作系统和我的一样 可以直接搜索鼠标 然后 选择 鼠标设置 然后 调整上面的鼠标指针速度即可
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023