数据结构(5):树和二叉树

1 树的定义

1.1 树的基本概念

分支可以称为边,结点可以用于存放数据结构。

除了根节点,其他节点只有一个前驱!!!!

互不相交也就是 只有一个前驱结点!

树应用的很广的

1.2 结点之间的关系

直接前驱是父节点,路径是单向的【只能从上往下走】

度为0就是叶子结点,度大于0就是非叶子结点!树的度-各结点的最大值!

1.3 有序树和无序数

家谱按照出生的顺序

1.4 树和森林

m棵不相交的树

2 树的性质

结点数 = 总度数+1 

这个1其实就是根结点

度为m的数和m叉树的区别

度为m的树最多结点

高度为h的m叉树最多结点

就素等比数列

度和叉树

具有n个结点的m叉树的最小高度

3 二叉树概念【高频】

满二叉树 完全二叉树

注意满二叉树的坐标规律!!!!【有利于以后的顺序存储!!】

在满二叉树的基础上去掉序号大的结点!

完全二叉树最多只有一个度为1的结点!!

二叉排序树

搜索就会简单哦!插入一个元素还可以是二叉排序树。二叉排序树可用于元素的排序、搜索!

平衡二叉树

更平衡会得到更高效的搜索效率!!!长的越胖越好

4 二叉树的常考性质

4.1 二叉树

叶子结点的个数 = 二分支结点的个数+1

二叉树的第i层最多结点

高度为h的二叉树最多结点

4.2 完全二叉树

结点为n的完全二叉树高度

给出总结点推出度为0、1、2的结点个数

n0 = n2+1 则n0+n2 = 2n2 +1 那么意思就是n0+n2一定是奇数

总结

4.3 二叉树的存储结构

4.3.1 顺序存储

完全二叉树

非完全二叉树

4.3.2 链式存储

总结

5 二叉树的遍历

5.1 二叉树 先/中/后序遍历

遍历:按照某个次序把所有的结点都访问一下

先序遍历也叫做先根遍历!

分支结点逐层展开法【写序列】

手算的时候一层一层的写!!!!【分支结点逐层展开法!】

中缀表达式是没有界限符的!!!

代码

从你的全世界路过法【写序列】

空间复杂度0(h+1)

A B D G  E C F 第一次路过的时候就访问结点!!!

中序:D G B E A F C  第二次路过的时候访问结点

后序:第三次路过的时候

用从你的全世界路过法:就是画出路径你就懂了:【类似这样的】

应用:求树的深度

5.2 二叉树的层序遍历

代码:

保存的是指针这样节省空间!

5.3 由遍历序列构造二叉树

只有当两个进行组合的时候才可以确定一个二叉树!!!【必须有中序序列

!】

先写左子树 再写根节点 最后写右子树!

只给一个不可以,但是任意两个进行组合就可以!!!

前序+中序

先圈出根结点!!!!

前序的第一个一定是根节点!!!!!

后序+中序

先找根节点:最后一个出现的就是根结点!!!!原理和之前相同!!!

层序+中序

根节点:层次序列里先出现的就是根结点!

如果不要中序序列是不可以的!

6 线索二叉树【难但重要!!】

6.1 线索二叉树的作用

第一个问题:对于普通的二叉树 必须从根节点开始遍历才可以,不能从任意的一个节点出发进行遍历

第二个问题:找到指定结点的前驱和后继是很不方便的

所以给出了中序线索二叉树

6.2 中序线索二叉树

把空链利用起来,一共有n+1个空链【n指的是结点的个数!!!】

意义:找前驱和后继就会很方便,遍历也很方便,因为遍历其实就是不断的找后继结点的过程!

这里的前驱和后继指的是在中序遍历序列中的前驱和后继!!不是父节点子节点哦

对于优点的指向的是后孩子的结点如何找到他的后继呢?【在后边会把这个坑填上!】

6.3 线索二叉树的存储结构

ltag==1说明是线索!

6.4 二叉树的线索化【代码实现!!】

6.4.1 土方法找中序前驱

6.4.2 中序线索化

线索化的过程其实和“土方法”是一样的,只不过每走一步就要判断一下是否有空链有就连上线索!

判断时:

【pre时p的前驱】看pre的右节点是否为空,空的话就连上p;看p的左节点是否为空,空的话连上pre

注意这个过程中没有最后一个结点的右指针指向null,需要做特殊处理!

下面是完整的代码!:

pre定义成局部遍历了,用引用之后会改变pre的值,和在外面定义一个是一样的!

6.4.3 先序线索化

会出现爱的魔力转圈圈的问题

完整代码:【也要对最后一个结点做特殊处理!】

6.4.4 后序线索化

不会出现爱的魔力转圈圈的问题!

6.5 在线索二叉树里找前驱和后继

更方便二点找到前驱和后继!!!

后序后继,和前序前趋 都需要能找到父节点才可以!!!!【用三叉链表或者土办法才可以】

中序后继

当tag=0的时候进行展开,注意展开到挨着“根”就停止了!

当有右孩子的时候,这个结点的后继结点就是p右子树的最左下的结点!!!

中序前驱

左子树的最右下的节点!!时刻确定tag

先序后继

如果有左孩子那么就是左孩子,如果没有左孩子那么只能是右孩子!

先序前驱

当ltag = 0时,就找不到前驱了,只能通过土办法进行寻找,因为没有往回指的指针了!【当可以找到父节点的话此局可解!】

如果能找到父节点的话:

对于3优先往右走,如果可以走通就一直走,走不了就向左拐下去就一直到最后一层就是它的前驱!!!

后序前驱

后序后继

只能用土办法!!!如果可以找到父节点的话此局也可解

7 树和森林

7.1 树的存储结构

二叉树的顺序存储:

是否可以推广到普通的树呢?

7.1.1 树的存储1:双亲表示法【顺序】

拓展:

优缺点:

找父节点【很方便!!!】,找孩子结点【只能遍历一下数组!!!】

7.1.2 树的存储2:孩子表示法【顺序+链式】

firstchild:指向第一个孩子编号!

用一个链表记录一个节点的孩子编号!

拓展:孩子表示法存储森林

服务流程树:

中文服务请按1,英文服务请按2.....按完之后又会接着要求按什么?直到找到具体的服务

7.1.3 树的存储3:孩子兄弟表示法【纯链式存储】

从用孩子兄弟表示法的结果来看很像二叉树!

拓展:孩子兄弟表示法存储森林

树根视为平级的兄弟关系

7.2 树、森林与二叉树的转换【重要】

7.2.1 树转二叉树

一层一层的处理,串冰糖葫芦!

7.2.2 森林转二叉树

7.2.3 二叉树转树

把冰糖葫芦先圈出来,然后 按照二叉树的层数放冰糖葫芦!

7.3 树和森林的遍历

8.2 森林转二叉树

树是一个递归定义的东西!

7.3.1 树的先根遍历【深度优先遍历】

这个路径优先往左走,然后每到一个就visit

7.3.2 树的后根遍历【深度优先遍历】

路径也是优先往左往下走,当第二次路过该节点的时候visit

7.3.3 树的层次遍历【广度优先遍历】

可以发现路径是尽可能一层一层的遍历的!所示可以看作是广度优先遍历

7.3.4 森林的先序遍历

森林这种数据结构适合树相互递归定义的!

注意递归的时候:第二部如果访问到的还是森林的话会回到第一步!

7.3.5 森林的中序遍历[看不懂如何递归的!!!!!!]

8 树与二叉树的应用

8.1 哈夫曼树【数据的压缩】

重要在哈夫曼树的构造!和哈夫曼的应用--哈夫曼编码!

只计算所有叶子节点!

哈夫曼书的定义:

如何构造呢?

更小的先结合!

一共需要合并n-1次,每次合并都会出现一个新的结点则哈夫曼树一共有2n-1个结点!

同样的叶子节点可以构造出不同的哈夫曼树

哈夫曼树的经典应用:哈夫曼编码

有没有比这个方案更有效的方案呢?

能不能更简单呢?

右边的编码可能会导致解码错误!

因此对可变长度编码时,所有的字符集对应的字符必须作为叶子结点不能作为中间的结点!

前缀编码:没有一个编码是另一个编码的前缀!

因此哈夫曼树可以用于数据的压缩!

8.2 并查集

各个集合之间是互不相交的,两个元素只有两种关系:一个是从属于同一个集合,一个是在不同的集合里

怎末用代码实现这样的数据结构呢?

使用森林:同一个集合中的元素组成树!

查:一路向上找到根节点!找根即可

并让一个树称为另一棵树的子树!

树的存储:双亲表示法、孩子表示法、孩子兄弟表示法。【双亲表示法会更适合实现并查集】

双亲表示法可以很快的找到父节点方便进行并和查的操作

8.2.1 存储结构

8.2.2 基本操作

是集合的具体实现

8.2.3 代码实现

【1】初始化

【2】并查

并的操作:是传入两个根节点的编号

【3】时间复杂度

find最坏时间复杂度:o(n),和树的高度有关,则如果对算法进行优化,意思就是让树长的不要那么瘦高!

【4】union优化(让小树合并到大树上就不会增加树的高度了)

大树小树:用根节点的绝对值表示树的结点总数!

树的高度不会超过

8.3 并查集的终极优化

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Infuse Pro for Mac全能视频播放器

Mac分享吧 文章目录 效果一、下载软件二、开始安装1、双击运行软件,将其从左侧拖入右侧文件夹中,等待安装完毕2、应用程序显示软件图标,表示安装成功 三、运行测试安装完成!!! 效果 一、下载软件 下载软件…

什么是公司自建企业邮箱?自建企业邮箱有什么用?

什么是公司自建企业邮箱?公司自建企业邮箱有什么用途?一是品牌统一;二是安全性增强;三是定制化功能;四是控制与灵活性等等。哪些企业适合自建企业邮箱呢?本篇文章将为您一一解释。 一、什么是公司自建企业…

《Milvus Cloud向量数据库指南》——SPLADE:基于BERT的Learned稀疏向量技术深度解析

在自然语言处理(NLP)领域,随着深度学习技术的飞速发展,预训练语言模型如BERT(Bidirectional Encoder Representations from Transformers)已成为推动研究与应用进步的重要基石。BERT通过其强大的上下文感知能力,在多项NLP任务中取得了显著成效,尤其是在文本表示和语义理…

Cannot access org.springframework.context.ConfigurableApplicationContext

Cannot access org.springframework.context.ConfigurableApplicationContext SpringApplication.run曝红 解决方案: File -> Invalidate Cache and Restart 如果对你有用就点个赞!

Platform Designer 自定义IP(用于纯RTL设计)

在开始菜单找到Quartus Prime工具,点击并打开。 点击Quartus菜单File——New: 选择Verilog HDL File,点击OK: 这是新建的.v文件如下: 在新建的.v文件中键入如下Verilog代码: module mux2x1( //模块的开头…

vue element-ui日期控件传参

前端&#xff1a;Vue element-ui <el-form-item label"过期时间" :rules"[ { required: true, message: 请选择过期时间, trigger: blur }]"><el-date-picker v-model"form.expireTime" type"date" format"yyyy-MM-dd&…

计算机实验室排课查询小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;学生管理&#xff0c;教师管理&#xff0c;实验室信息管理&#xff0c;实验室预约管理&#xff0c;取消预约管理&#xff0c;实验课程管理&#xff0c;实验报告管理&#xff0c;报修信息管理&#xff0…

鸿蒙北向开发 DevEco Studio 4.1 下载安装傻瓜式教程

开篇 由于鸿蒙处于快速发展中,鸿蒙的api快速迭代更新,老版本的DevEco studio无法支持更新版本的api,因此华为官网放弃了老版本的维护.直接从华为开发者官网无法下载老版本,当前华为开发者官网已经推出next版本了 DevEco studio3.1安装教程 上述教程提供的华为开发者官网地址已经…

Python --NumPy库基础方法(1)

NumPy Numpy(Numerical Python) 是科学计算基础库&#xff0c;提供大量科学计算相关功能&#xff0c;比如数据统计&#xff0c;随机数生成等。其提供最核心类型为多维数组类型&#xff08;ndarray&#xff09;&#xff0c;支持大量的维度数组与矩阵运算&#xff0c;Numpy支持向…

python编程表白爱心代码,来自程序员的浪漫!

Python爱心表白代码 感觉的紫色要更加浪漫&#xff0c;其中的文字也是可以直接更改的&#xff0c;非常方便 <文末附带精品籽料> 改变爱心的颜色: 在源代码的13-15行位置&#xff0c;可以通过更改16进制颜色色值进行改变爱心的颜色&#xff0c;这里小编改了一点绿色&…

人生低谷来撸C#--018 匿名方法

1、概念 在 C# 中&#xff0c;匿名方法&#xff08;anonymous methods&#xff09;和 Lambda 表达式&#xff08;lambda expressions&#xff09;是两种非常有用的功能&#xff0c;它们允许你在不定义命名方法的情况下编写简短的、内联的代码块。 匿名方法&#xff08;Anonym…

驰骋低代码如何实现对实体的权限控制?

驰骋低代码平台通过一套精细的权限控制机制&#xff0c;实现了对实体&#xff08;如车辆、学生、员工、固定资产等&#xff09;的查询范围权限和操作权限的全面控制。这种权限控制不仅确保了数据的安全性和准确性&#xff0c;还提高了系统的灵活性和可定制性。以下是驰骋低代码…

SpringBoot:JWT+Interceptor 实现基本的登录验证

前置背景 Result类 &#xff1a; package com.example.day724test.Dao;import lombok.AllArgsConstructor; import lombok.Data; import lombok.NoArgsConstructor;//统一响应结果 NoArgsConstructor AllArgsConstructor Data public class Result<T> {private Intege…

Qt+OpenCascade开发笔记(一):occ的windows开发环境搭建(一):OpenCascade介绍、下载和安装过程

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/140604141 长沙红胖子Qt&#xff08;长沙创微智科&#xff09;博文大全&#xff1a;开发技术集合&#xff08;包含Qt实用技术、树莓派、三维、OpenCV…

【数据结构】手把手教你单链表(c语言)(附源码)

&#x1f31f;&#x1f31f;作者主页&#xff1a;ephemerals__ &#x1f31f;&#x1f31f;所属专栏&#xff1a;数据结构 目录 前言 1.单链表的概念与结构 2.单链表的结构定义 3.单链表的实现 3.1 单链表的方法声明 3.2 单链表方法实现 3.2.1 打印链表 3.2.2 创建新…

机械学习—零基础学习日志(高数11——三角函数)

零基础为了学人工智能&#xff0c;真的开始复习高数 三角函数之所以比较困难&#xff0c;是因为过于抽象&#xff0c;距离生活太过遥远&#xff0c;这里搜集一些资料&#xff0c;帮助大家能加深对三角函数的理解。 三角函数作用——能测距离 三角函数从应用层&#xff0c;开…

C++ | Leetcode C++题解之第287题寻找重复数

题目&#xff1a; 题解&#xff1a; class Solution { public:int findDuplicate(vector<int>& nums) {int slow 0, fast 0;do {slow nums[slow];fast nums[nums[fast]];} while (slow ! fast);slow 0;while (slow ! fast) {slow nums[slow];fast nums[fast]…

RuoYi基于SpringBoot+Vue前后端分离的Java快速开发框架学习_2_登录

文章目录 一、登录1.生成验证码2.验证码作用1.大体流程2.代码层面(我们都是从前端开始看起) 一、登录 1.生成验证码 基本思路&#xff1a; 后端生成一个表达式&#xff0c;例如34?7,显而易见后面是答案截取出来题干和答案把题干11&#xff1f;变成图片&#xff0c;变成流&a…

【Qt】QLCDNumber和QProgressBar

目录 QLCDNumber 倒计时小程序 相关属性 QProgressBar 进度条小程序 相关设置 QLCDNumber QLCDNumber是Qt框架中用于显示数字或计数值的小部件。通常用于显示整数值&#xff0c;例如时钟、计时器、计数器等 常用属性 属性说明intValueQLCDNumber显示的初始值(int类型)va…

Python爬虫技术 第13节 HTML和CSS选择器

在爬虫技术中&#xff0c;解析和提取网页数据是核心部分。HTML 和 CSS 选择器被广泛用于定位网页中的特定元素。下面将详细介绍这些选择器如何在 Python 中使用&#xff0c;特别是在使用像 Beautiful Soup 或 Scrapy 这样的库时。 HTML 选择器 HTML 选择器基于 HTML 元素的属性…