当前位置: 首页 > news >正文

网站更换域名/长沙百度首页排名

网站更换域名,长沙百度首页排名,去除wordpress主题版权,58好项目网目录 一. 树,基本术语 二. 二叉树 (1)二叉树 (2)满二叉树 (3)完全二叉树 三. 二叉树的性质 四. 二叉树的存储结构 (1)顺序存储结构 (2)链…

目录

一. 树,基本术语

二. 二叉树

(1)二叉树

(2)满二叉树

(3)完全二叉树

三. 二叉树的性质

四. 二叉树的存储结构

(1)顺序存储结构

(2)链式存储结构


树形结构:结点之间有分支,具有层次关系。

一. 树,基本术语

树的定义:树(Tree)是n (n≥0)个结点的有限集。
(1)若n = 0,称为空树;
(2)若n >0,则它满足如下两个条件:

  • 有且仅有一个特定的称为根(Root)的结点;
  • 其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,....Tm,其中每一个集合本身又是一棵树,并称为根的子树(SubTree)。

树的一些基本术语在下图中展示:

有序树:树中结点的各子树从左至右有次序(最左边的为第一个孩子)。

无序树:树中结点的各子树无次序。

森林:是m(m≥O)棵互不相交的树的集合。

森林与树的关系:把树的根结点删除树就变成了森林。一棵树可以看成是一个特殊的森林。给森林中的各子树加上一个双亲结点,森林就变成了树。

二. 二叉树

(1)二叉树

为何要重点研究每结点最多只有两个“叉”的树?

  • 二叉树的结构最简单,规律性最强;
  • 可以证明,所有树都能转为唯一对应的二叉树,不失一般性。

普通树(多叉树)若不转化为二叉树,则运算很难实现。二叉树在树结构的应用中起着非常重要的作用,因为对二叉的许多操作算法简单,而任何树都可以与二叉树相互转换,这样就解决了。

二叉树:二叉树是n(n≥0)个结点的有限集,它或者是空集(n = 0),或者由一个根结点及两棵互不相交的,分别称作这个根的左子树和右子树的二叉树组成。
二叉树的特点:

  • 每个结点最多有俩孩子(二叉树中不存在度大于2的结点)。
  • 子树有左右之分,其次序不能颠倒。
  • 二叉树可以是空集合,根订以有空的左子树或空的右子树。

注意:二叉树不是树的特殊情况,也不是有序树,而是两个不同的概念。

  • 二叉树结点的子树要区分左子树和右子树,即使只有一棵子树也行区分,说明它是左子树,还是右子树。
  • 树当结点只有一个孩子时,就无须区分它是左还是右的次序。因此二者是不同的。这是二叉树与树的最主要的差别。

也就是二叉树每个结点位置或者说次序都是固定的,可以是空,但是不可以说它没有位置,而树的结点位置是相对于别的结点来说的,没有别的结点时,它就无所谓左右了。

二叉树的五种基本形态如下:

下面我们介绍满二叉树和完全二叉树,这两种特殊的二叉树在顺序存储结构下可以复原。

(2)满二叉树

一棵深度为k且有2^k-1个结点的二叉树称为满二叉树。

特点:1.每一层上的结点数都是最大结数(即每层都满);2.叶子节点全部在最底层; 3.满二叉树在同样深度的二叉树中,结点数,叶子结点数都是最多的。

对满二叉树结点位置进行编号:从根结点开始,自上而下,自左而右。每一结点位置都有元素。

(3)完全二叉树

深度为k的具有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时,称之为完全二叉树。

也可以从满二叉树看完全二叉树:在满二叉树中,从最后一个结点开始,连续去掉任意个结点,即是一棵完全二叉树。一定是连续的去掉! 

特点:1.叶子结点只可能分布在层次最大的两层上;2.对任一结点,如果其右子树的最大层次为i,则其左子树的最大层次必为i或i+1。

三. 二叉树的性质

性质1:二叉树的第i层上最多有2^{i-1}个结点(i>=1),最少有1个结点;

性质2:深度为k的二叉树至多有2^k-1个结点,最少有k个结点;

性质3:对任何一个二叉树T,如果叶子结点数为n0,度为2的结点数为n2,则有:n_0=n_2+1

证明:设总边数为B,结点数为n,显然有:B=n-1,这是由于除了根结点以外,每个结点有且只有一个前驱。

同时,因为结点的度只能为0,1,2,记他们的个数分别是n_0,n_1,n_2,所以有:n=n_0+n_1+n_2B=n_1+2n_2

联立以上三式就可得到:n_0=n_2+1,证毕。

性质4:具有n个结点的完全二叉树的深度是\left \lfloor log_2n \right \rfloor+1,其中\left \lfloor x \right \rfloor表示不超过x的最大整数。

证明:深度为k的完全二叉树,结点个数的范围是:2^{k-1}\leqslant n\leqslant 2^k-1

性质5:对一个具有n个结点的完全二叉树,对一个编号为i的结点:

(1)i>1时,此结点的双亲结点是\left \lfloor i/2 \right \rfloor

(2)此结点的左孩子结点编号是2i,右孩子结点编号是2i+1(如果左右孩子存在);

四. 二叉树的存储结构

(1)顺序存储结构

实现:按满二叉树的结点层次编号,依次存放二叉树中的数据元素。

//二叉树的顺序存储
# define MAXSIZE 100
typedef TElemType SqBiTree[MAXSIZE];
SqBiTree bt;

定义二叉树的顺序存储结构如上所示,使用了一个数组 SqBiTree 来表示二叉树。SqBiTree 是一个 typedef 定义的类型别名,它是一个大小为 MAXSIZE 的数组,数组元素的类型是 TElemTypeTElemType 可以根据具体的需求来定义,表示二叉树节点的数据类型。在这段代码中没有给出 TElemType 的具体定义,需要根据实际情况来确定。通过这段代码,我们可以使用数组 bt 来表示一个二叉树,数组的大小为 MAXSIZE,数组中的元素存储了二叉树的节点数据。这种顺序存储结构的好处是可以快速访问二叉树的任意节点,但是需要提前确定二叉树的最大节点数。

例:根据数组还原二叉树

特点:结点间关系蕴含在数组位置中,浪费空间,适用于满二叉树和完全二叉树。

(2)链式存储结构

二叉树结点的特点:每个结点有左孩子,或者右孩子,所以二叉树的链式结点包含数据域和两个指针域:

typedef struct BiNode{TElemType data;struct BiNode *lchild,*rchild; //左右孩子指针
}BiNode,*BiTree;

有时为了寻找祖先结点,还会增设一个指针*parent,这样结点就有四部分:

lchilddataparentrchild

相关文章:

15.树与二叉树基础

目录 一. 树,基本术语 二. 二叉树 (1)二叉树 (2)满二叉树 (3)完全二叉树 三. 二叉树的性质 四. 二叉树的存储结构 (1)顺序存储结构 (2)链…...

neo4j 图数据库 springboot

一.安装 neo4j社区版在liunx安装部署 https://blog.csdn.net/u013946356/article/details/81736232 二.知识图数据导入 参考:https://notemi.cn/neo4j-import-csv-file-data.html http://openkg.cn/dataset/ch4masterpieces 放在对应的import文件夹下面 导入数据 LOAD C…...

Linux下的系统编程——makefile入门(四)

前言: 或许很多Winodws的程序员都不知道这个东西,因为那些Windows的IDE都为你做了这个工作,但我觉得要作一个好的和professional的程序员,makefile还是要懂。这就好像现在有这么多的HTML的编辑器,但如果你想成为一个专…...

Mybatis的综合案例-学生信息查询系统 用于校验是否真正学习掌握了动态SQL

Mybatis的综合案例-学生信息查询系统 需求一:当用户输入的学生姓名不为空,则只根据学生信息进行查询; 当用户输入的学生姓名为空,且专业不为空,那么就根据学生专业进行学生的查询 需求二:查询所有id值小于5的学生信息…...

力扣:70. 爬楼梯(Python3)

题目: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 来源:力扣(LeetCode) 链接:力扣(LeetCode)官网 - 全球极客…...

陕西广电 HG6341C FiberHome烽火 光猫获取超级密码 改桥接模式 提升网速

光猫默认的路由模式实测在100M宽带下只能跑到60M左右,只有改成桥接模式才能跑满,不损失性能。但是改桥接需要给运营商打电话,有的时候不想麻烦他们,这时获取超级密码进行更改就是一个不错的选择了 分析 之前写了一篇HGU B2 光猫的…...

无涯教程-PHP - 移除的扩展

以下扩展已从PHP 7开始删除- eregmssqlmysqlsybase_ct 以下SAPI已从PHP 7开始删除- aolserverapacheapache_hooksapache2filtercaudiumcontinuityisapimilternsapiphttpdpi3webroxenthttpdtuxwebjames PHP - 移除的扩展 - 无涯教程网无涯教程网提供以下扩展已从PHP 7开始删除…...

笔记:transformer系列

1、和其他网络的比较 自注意力机制适合处理长文本,并行度好,在GPU上,CNN和Self-attention性能差不多,在TPU(Tensor Processing Uni)效果更好。 总结: 自注意力池化层将当做key,value,query来…...

Mysql socket连接测试

配置如下: socket /data/mysql/data/mysql.sock //套接字文件 在数据库没有任何连接的情况下,可以看到3306端口和socket端口都在监听 [mysqlt3-dtpoc-dtpoc-web04 bin]$ netstat -an | grep -i 3306 tcp 0 0 0.0.0.0:3306 0.…...

探究分布式操作系统的本质

探究分布式操作系统的本质 有一位网友问,分布式操作系统的本质是什么,今天就来说说这个话题。 首先,我们需要明确什么是分布式操作系统。 从大范围来理解,分布式操作系统是传统单机操作系统的延伸,可以看作是在多台独…...

opencv-dnn

# utils_words.txt 标签文件 import osimage_types (".jpg", ".jpeg", ".png", ".bmp", ".tif", ".tiff")def list_images(basePath, containsNone):# return the set of files that are validreturn list_file…...

如何选择合适的开源许可证?

🌷🍁 博主猫头虎 带您 Go to New World.✨🍁 🦄 博客首页——猫头虎的博客🎐 🐳《面试题大全专栏》 文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~🌺 &a…...

【前端】深入解析CSS:选择器、显示模式、背景属性和特征剖析

目录 一、前言二、CSS的复合选择器1、后代选择器①、语法②、注意事项 2、子选择器①、语法②、注意事项 3、并集选择器①、语法②、注意事项 4、链接伪类选择器①、语法②、注意事项 三、CSS元素显示模式转换1、转换为块元素display:block2、转换为行内元素display:inline3、转…...

算法训练营第三十四天(8.23)| 动态规划Part04:01背包

目录 Leecode 1049.最后一块石头的重量II Leecode 494.目标和 Leecode 474.一和零 Leecode 1049.最后一块石头的重量II 题目地址:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 题目类型:01背包 class Solution { public:int…...

【python】tkinter使用多进程打包成exe后multiprocessing无法关闭对应进程

这是由于multiprocessing模块在Windows操作系统下使用fork方法创建子进程时会导致打包成exe后无法正常运行的问题。 可以尝试使用freeze_support函数来解决这个问题。freeze_support函数是在Windows操作系统下用于支持multiprocessing模块的函数。 下面是一个示例代码&#x…...

Redis工具类(缓存操作,Object转换成JSON数据)

依赖spring-data-redis-2.4.1.jar Component Data public class RedisUtils {Autowiredprivate RedisTemplate<String, Object> redisTemplate;Resource(name "stringRedisTemplate")private ValueOperations<String, String> valueOperations;/*** 默…...

Linux 下 Java Socket 编程报 java.net.Exception:Permission denied (权限不足)

本人用Linux部署springboot项目时遇见这个错误&#xff0c;原因很简单&#xff0c;就是端口号没有选对。 在linux系统中&#xff0c;端口号再1024以下的需要root权限&#xff0c;只要把端口改成大于1024的就可以了&#xff0c;但避开一些软件的默认端口&#xff0c;如Tomcat的8…...

IDEA项目实践——VUE介绍与案例分析

系列文章目录 IDEA项目实践——JavaWeb简介以及Servlet编程实战 IDEA项目实践——Spring集成mybatis、spring当中的事务 IDEA项目实践——Spring当中的切面AOP IDEWA项目实践——mybatis的一些基本原理以及案例 IDEA项目实践——Spring框架简介&#xff0c;以及IOC注解 I…...

vue-canvas基本使用和注意事项-动画闪烁效果-自适应适配不同分辨率问题

前言 canvas画布是html的新特性&#xff0c;熟悉画布我们可以完成很多拖拽&#xff0c;标注&#xff0c;动画的功能 使用canvas实现一个小例子很容易&#xff0c;但是真正在项目中使用时&#xff0c;我们需要注意的地方有很多 canvas基本原理就是它基于渲染方法&#xff0c;根…...

Jmeter 如何才能做好接口测试?

现在对测试人员的要求越来越高&#xff0c;不仅仅要做好功能测试&#xff0c;对接口测试的需求也越来越多&#xff01; 所以也越来越多的同学问&#xff0c;怎样才能做好接口测试&#xff1f; 要真正的做好接口测试&#xff0c;并且弄懂如何测试接口&#xff0c;需要从如下几…...

电商平台京东平台获得京东商品描述API接口演示案例

京东商品描述API接口可以获取京东商品描述&#xff1a; 详细介绍商品的特点和功能,让消费者能够了解商品的具体用途和效果。 使用简洁明了的语言,避免使用过于专业的术语和长句子,让消费者能够轻松理解。 重点突出商品的卖点和优势,让消费者能够更加清晰地了解商品的价值 …...

《算法竞赛·快冲300题》每日一题:“单位转换”

《算法竞赛快冲300题》将于2024年出版&#xff0c;是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码&#xff0c;以中低档题为主&#xff0c;适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “ 单…...

R语言13-R语言中的数据导入导出和批量导入

数据导入 CSV 文件&#xff1a; 使用 read.csv() 函数导入逗号分隔的文本文件。 data <- read.csv("data.csv")Excel 文件&#xff1a; 使用 readxl 包中的函数 read_excel() 导入 Excel 文件。 install.packages("readxl") # 安装 readxl 包&#…...

【Java】对象与类

【Java】对象与类 文章目录 【Java】对象与类1、学习背景2、定义&使用2.1 创建类2.2 创建对象 3、static关键字3.1 修饰变量3.2 修饰方法3.3 修饰代码块3.4 修饰内部类 4、this关键字5、封装特性5.1 访问修饰符5.2 包的概念 6、构造方法7、代码块7.1 普通代码块7.2 成员代码…...

视频尺寸缩小,一键批量剪辑,轻松制作精简版

大家好&#xff01;在视频剪辑中&#xff0c;有时我们需要将大尺寸的视频缩小&#xff0c;以适应特定的需求和平台要求。为了帮助您轻松制作精简版视频&#xff0c;我们推出了一款全新的工具——视频尺寸缩小批量剪辑软件&#xff01;让您一键批量将视频尺寸缩小&#xff0c;轻…...

leetcode做题笔记94. 二叉树的中序遍历

给定一个二叉树的根节点 root &#xff0c;返回 它的 中序 遍历 。 思路一&#xff1a;模拟题意 void inorder(struct TreeNode*root,int* ans,int *resSize) {if(!root){return ;}inorder(root->left,ans,resSize);ans[(*resSize)] root->val;inorder(root->right…...

UWB高精度人员定位系统源码,微服务+java+ spring boot+ vue+ mysql技术开发

工业物联网感知预警体系&#xff0c;大中小企业工业数字化转型需求的工业互联网平台 工厂人员定位系统是指能够对工厂中的人员、车辆、设备等进行定位&#xff0c;实现对人员和车辆的实时监控与调度的系统&#xff0c;是智慧工厂建设中必不可少的一环。由于工厂的工作环境比较…...

企业党建杂志企业党建杂志社企业党建编辑部2023年第4期目录

卷首语 坚持学思用贯通 知信行统一 (0001) 赵荣地 国企与国资《企业党建》投稿&#xff1a;cn7kantougao163.com 深入推进新时代党的建设的重大部署 (0004) 陈锋 国有企业推进中国式现代化建设的使命任务和实践路径 (0006) 蒋雪群 创新与实践 浅析国企党建与生产经营工作…...

ChatGPT + Flutter快速开发多端聊天机器人App

下载地址&#xff1a;ChatGPT Flutter快速开发多端聊天机器人App 下载地址&#xff1a;ChatGPT Flutter快速开发多端聊天机器人App...

ubuntu18.04复现yolo v8之最终章,realsenseD435i+yolo v8完美运行

背景&#xff1a;上一篇博客我们已经为复现yolov8配置好了环境&#xff0c;如果前面的工作顺利进行&#xff0c;我们已经完成了90%&#xff08;学习类程序最难的是环境配置&#xff09;。 接下来将正式下载yolov8的相关代码&#xff0c;以及进行realsenseD435i相机yolo v8的de…...