NzN的数据结构--二叉树part1

        你叉叉,让你学数据结构你不学;你叉叉,让你看二叉树你不看。 今天我们来一起学习二叉树部分,先赞后看是好习惯

 

一、树的概念及结构

1. 树的概念

        树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。有一个特殊的结点,称为根结点,根节点没有前驱结点

 

        我们可以把一棵树拆解成根和子树。除根节点外,其余结点被分成M(M≥0)个互不相交的T1T2 、……、Tm ,其中每一个集合又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继节点。子树也可以继续被拆解为根和子树的子树。因此,树是递归定义的。

注意:

  • 树形结构中,子树是不相交的,否则就不是树形结构。
  • 除了根结点外,每个结点有且仅有一个父结点。
  • 一棵N个结点的树有N-1条边。

       上面两种都不是树形结构!!!

2. 树的相关概念

节点的度:一个节点含有的子树的个数称为该节点的度。 如上图,A的度为6。

叶节点(终端节点)度为0的节点称为叶节点。 如上图:B、C、H、I...等节点为叶节点。

非终端节点(分支节点)度不为0的节点。 如上图:D、E、F、G...等节点为分支节点。

双亲节点(父节点)若一个节点含有子节点,则这个节点称为其子节点的父节点。 如上图,A是B的父节点。

孩子节点(子节点)一个节点含有的子树的根节点称为该节点的子节点。如上图,B是A的孩子节点。

兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点。

树的度:树中最大的节点的度称为树的度; 如上图:节点的度最大为6,则树的度为6。

节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推。

树的高度(深度)树中节点的最大层次,一般从1开始数,空树的高度为0。

堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点。

节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先。

子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙。

森林:由m(m>0)棵互不相交的树的集合称为森林。

3. 树的表示

        树结构相对线性表就比较复杂了,既然保存值域,也要保存结点和结点之间的关系。树有很多种表示方式:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。

//方法一(容易造成空间浪费)
#define N 6//定义树的度为6
struct TreeNode
{int val;struct TreeNode* subA[N];//开辟结构体指针数组存储孩子
};
//方法二:用顺序表存储孩子的内容
struct TreeNode
{int val;//顺序表struct TreeNode** subA;//这里应该是二级指针//开辟的是指针数组,每个数组的元素是结构体指针int size;int capacity;
};

        我们这里推荐最常用的左孩子右兄弟表示法

//左孩子右兄弟表示法
struct TreeNode
{int val;struct TreeNode* leftChild;//指向左边的第一个孩子struct TreeNode* nextBrother;//指向自己右边的兄弟,最右边的nextBrother指向NULL
};

        如上图,A的leftChild指向B,nextBrother指向空;B的leftChild指向D,nextBrother指向C;C的leftChild指向G,nextBrother指向空等等,以此类推便可以便将整个树串了起来。 

4. 树在实际中的运用(表示文件系统的目录树结构)

二、二叉树概念及结构

1. 概念

        一棵二叉树是结点的一个有限集合,该集合由一个根节点加上两棵别称为左子树和右子树的二叉树组成或者也可能为空。 

        从上图可以看出:二叉树不存在度大于2的结点;二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

注意:二叉树不是只有两棵子树,而是最多有两棵子树。

        对于任意的二叉树都是由以下几种情况复合而成的:

        后面我们会学二叉搜索树,他的要求是左子树数据全小于根,右子树数据均大于根。

       假设二叉搜索树高度为h,则查找次数最多为h次。二叉搜索树也有不足,有些时候会退化成下面这种情况。就需要我们继续学习AVL数和红黑树。

2. 特殊的二叉树 

        满二叉树:一个二叉树,如果每一层的结点数都达到最大值,则这个二叉树就是满二叉树。即如果一个二叉树的层数为k,且结点总数是2^k-1 ,则它就是满二叉树。

        完全二叉树:对于深度为k,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时称为完全二叉树。 满二叉树是一种特殊的完全二叉树。

3. 二叉树的性质

        若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^i-1个结点

        若规定根节点的层数为1,则深度为h的二叉树的最大结点数2^h-1

        对任何一棵二叉树,度为0其叶结点个数比度为2的结点个数多1个

        若规定根节点的层数为1,具有n个结点的满二叉树的深度,h=log_{2}(n+1)

        对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:

  • 若i>0,i 位置节点的双亲序号:\frac{i-1}{2};i=0,i为根节点编号,无双亲节点
  • 若2i+1<n,左孩子序号:2i+1,2i+1≥n,否则无左孩子
  • 若2i+2<n,右孩子序号: 2i+2,2i+2≥n,否则无右孩子

3. 二叉树的存储结构 

二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。

3.1 顺序存储

顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,否则会有空间浪费。现实使用中,只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。

        父子存储的下标规律:

  • leftchild=parent*2+1,rightchild=parent*2+2
  • parent=(child-1)/2

        这样可以直接通过数组下标访问,也可以通过数组还原树。数组存储只适合完全二叉树和满二叉树,否则会造成大量空间浪费。

3.2 链式存储

        链式存储是指用链表来表示二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点分成三个域:数据域和左右指针域。左右指针分别给出该结点左孩子和右孩子所在的链结点的存储地址。

        链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,后面学到高阶数据结构如红黑树等会用到三叉链。

         那本章我们介绍了二叉树入门的一些内容,下一章我们就要正式开始学习二叉树的实现方法,给个三连,敬请关注~~~

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

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

相关文章

合并主分支到子分支

参考&#xff1a;【Git】合并分支出现 Please enter a commit message to explain why this merge is necessary.-CSDN博客 git 如何将主分支(master)合并到子分支上_git 将主分支合并到子分支-CSDN博客 1、先切换到主分支master git checkout master 2、把主分支代码拉到本地…

【Threejs进阶教程-效果篇】1.Threejs文字与css2d/css3d技术

Threejs文字与css2d/css3d技术 学习ThreeJS的捷径学习之前先搞清楚自己想要什么样的效果贴图文字准备一张带文字的png贴图使用sprite来进行贴图实现2D始终面朝相机的文字使用planeGeometry来贴图实现3D文字使用planeGeometry来贴图实现伪3D文字动态贴图文字html2Canvas 文字几何…

Java8关于Function接口

Java学习-Function接口 1 函数式接口简介和学习地址2 两种常见的函数式接口2.1 Runnable&#xff1a;执行接口&#xff0c;不接收参数&#xff0c;也无返回结果。2.2 Consumer&#xff1a;作为消费接口&#xff0c;接收一个参数&#xff0c;无返回结果。 3 初识3.1 定义Functio…

Android详细介绍POI进行Word操作(小白可进)

poi-tl是一个基于Apache POI的Word模板引擎&#xff0c;也是一个免费开源的Java类库&#xff0c;你可以非常方便的加入到你的项目中&#xff0c;并且拥有着让人喜悦的特性。 一、使用poi前准备 1.导入依赖&#xff1a; 亲手测过下面Android导入POI依赖的方法可用 放入这个 …

OSPF实例是什么?

OSPF实例是什么&#xff1f; **OSPF实例指的是一个OSPF路由进程&#xff0c;它是在一个设备上运行的单独的OSPF路由协议实体**。 在详细解释这个概念之前&#xff0c;需要了解OSPF&#xff08;Open Shortest Path First&#xff09;是一种内部网关协议&#xff08;IGP&#x…

hive图形化客户端工具

hive准备 创建测试数据 以root用户登录&#xff0c;使用hive命令启动hive。 创建库 create database testhivedb; 创建表 create table testhivedb.testhivetable( id int ,name string ); 插入数据 insert into testhivedb.testhivetable values (1,cc); insert into…

Vscode连接WSL2当中的jupyter

主要解决办法参考自这篇博客 1. 在WSL当中安装jupyter 这个随便找一篇博客即可&#xff0c;比如这篇&#xff0c;也可以根据现有的环境参考其它博客内容 2. 使用jupyter创建一个虚拟环境 首先激活想要添加的虚拟环境后&#xff0c;输入命令安装库: pip install ipykernel …

HarmonyOS实战开发-如何实现分布式帐号相关的功能。

介绍 本示例主要展示了分布式帐号相关的功能&#xff0c;使用ohos.account.distributedAccount、ohos.account.osAccount等接口&#xff0c;实现了绑定分布式帐号、解绑分布式帐号、更新分布式帐号信息和管理分布式帐号的功能&#xff1b; 效果预览 使用说明 1.首次进入应用会…

Text-Driven Object Detection 关于结合文本的目标检测

1、简单介绍 首先说明&#xff0c;本文目的主要是水一篇CSDN博客&#xff0c;顺便说一下和标题相关的认识。 近几年&#xff0c;在目标检测领域关于多模态的目标检测工作已成了主流&#xff0c;趋势仍在延续&#xff0c;未来仍有很大挖掘空间。这里说的多模态不是简单的多源数…

element-ui使用记录

element-ui的组件名就是类名 样式穿透&#xff08;用来修改没有类名的子组件样式&#xff09; 例如修改头部具名插槽的样式&#xff08;但是无法定位该元素&#xff09; 查看最后生成的html结构中对应的结构&#xff08;这里的头部有类名&#xff0c;可以直接对该类名进行样…

【CicadaPlayer】demuxer_service的简单理解

G:\CDN\all_players\CicadaPlayer-github-0.44\mediaPlayer\SMPMessageControllerListener.cppplayer的demuxer服务类 std::unique_ptr<demuxer_service> mDemuxerService{nullptr};根据option (Cicada::options),可以决定音视频的不同操作,通过 hander可以获得具体使…

SpringCloud Alibaba Sentinel 创建流控规则

一、前言 接下来是开展一系列的 SpringCloud 的学习之旅&#xff0c;从传统的模块之间调用&#xff0c;一步步的升级为 SpringCloud 模块之间的调用&#xff0c;此篇文章为第十四篇&#xff0c;即介绍 SpringCloud Alibaba Sentinel 创建流控规则。 二、基本介绍 我们在 senti…

UltraScale 架构 SelectIO 资源之IODELAY与IOSERDES仿真与使用

平台&#xff1a;vivado2018.3 具体内容见ug571-ultrascale-selectio IDELAYE3 在调试超高速信号的时候&#xff0c;需要使用iodelayiserdes来调试校准输入信号。例如外部某ADC采样率为5GHZ&#xff0c;外部ADC使用2.5GHZ的时钟去采集输入信号。为了实现采集&#xff0c;adc芯…

90天玩转Python—05—基础知识篇:Python基础知识扫盲,使用方法与注意事项

90天玩转Python系列文章目录 90天玩转Python—01—基础知识篇:C站最全Python标准库总结 90天玩转Python--02--基础知识篇:初识Python与PyCharm 90天玩转Python—03—基础知识篇:Python和PyCharm(语言特点、学习方法、工具安装) 90天玩转Python—04—基础知识篇:Pytho…

如何搭建APP分发平台分发平台搭建教程

搭建一个APP分发平台可以帮助开发者更好地分发和管理他们的应用程序。下面是一个简要的教程&#xff0c;介绍如何搭建一个APP分发平台。 1.确定需求和功能&#xff1a;首先&#xff0c;确定你的APP分发平台的需求和功能。考虑以下几个方面&#xff1a; 用户注册和登录&#xff…

Stable Diffusion扩散模型推导公式的基础知识

文章目录 1、独立事件的条件概率2、贝叶斯公式、先验概率、后验概率、似然、证据3、马尔可夫链4、正态分布 / 高斯分布5、重参数化技巧6、期望7、KL散度 、高斯分布的KL散度8、极大似然估计9、ELBO :Evidence Lower Bound10、一元二次方程 1、独立事件的条件概率 A 和 B 是两个…

Vue项目打包成exe文件(electron)

1.将写好的vue项目打包 1.1运行vue ui命令 输出目标文件 如果打开index.html是空白的&#xff0c;而且控制台报错获取xxx资源失败的问题&#xff0c;你需要在vue.config.js 上加一个命令&#xff0c;如果没有你需要创建一个。 2.下载electron官方示例 git clone https://gith…

zdpdjango_argonadmin Django后台管理系统中的常见功能开发

效果预览 首先&#xff0c;看一下这个项目最开始的样子&#xff1a; 左侧优化 将左侧优化为下面的样子&#xff1a; 代码位置&#xff1a; 代码如下&#xff1a; {% load i18n static admin_argon %}<aside class"sidenav bg-white navbar navbar-vertical na…

Python---Numpy线性代数

1.数组和矩阵操作&#xff1a; 创建数组和矩阵&#xff1a;np.array, np.matrix 基本的数组操作&#xff1a;形状修改、大小调整、转置等 import numpy as np# 创建一个 2x3 的数组 A np.array([[1, 2, 3], [4, 5, 6]]) print("数组 A:\n", A)# 将数组 A 转换为矩阵…

趣学前端 | 综合一波CSS选择器的用法

背景 最近睡前习惯翻会书&#xff0c;重温了《HTML5与CSS 3权威指南》。这本书&#xff0c;分上下两册&#xff0c;之前读完了上册&#xff0c;下册基本没翻过。为了对得起花过的每一分钱&#xff0c;决定拾起来近期读一读。 CSS 选择器 在CSS3中&#xff0c;提倡使用选择器…