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

佛山网约车驾驶员资格证网上报名seo公司排行

佛山网约车驾驶员资格证网上报名,seo公司排行,web前端开发招聘信息,用手机怎样免费做网站“路虽远,行则将至” ❤️主页:小赛毛 目录 1.树概念及结构 1.1树的概念 1.2 树的相关概念 1.3 树的表示(树的存储) 2.二叉树概念及结构 2.1概念 2.2现实中的二叉树 2.3 特殊的二叉树: 2.4 二叉树的性质 3.二叉树的顺…

   “路虽远,行则将至”

❤️主页:小赛毛

目录

1.树概念及结构

1.1树的概念

1.2 树的相关概念

 1.3 树的表示(树的存储)

2.二叉树概念及结构

2.1概念

2.2现实中的二叉树

2.3 特殊的二叉树:

2.4 二叉树的性质 

3.二叉树的顺序结构及实现

3.1 二叉树的顺序结构

3.2 堆的概念及结构

3.3 堆的实现

3.2.1 堆向下调整算法

 3.2.2堆的创建

前言:

在进入今天的正题之前,我们先来回顾一下我们已经学过的知识:

顺序的本质是什么呢?数组

但是呢,顺序表在这里是有一些缺陷的:

1.中间或者头部插入删除数据要挪动数据,效率低

2.空间不够,只能扩容。扩容有消耗

3.倍数扩容,用不完,存在空间浪费

当然,有利有弊,优点:

1.下标随机访问。排序 二分查找适合

2.CPU高速缓存命中率比较高

在我们学完顺序表之后呢,我们当时顺序就学了链表:

在这里呢,我们要请出链表的典型代表——带头结点的双向循环链表 同志来参加。

优点:

1.任意位置插入删除效率高

2.按需申请释放,不存在扩容

缺点:

1.不能下标随机访问

2.CPU高速缓存命中率低


1.树概念及结构

1.1树的概念

树是一种 非线性 的数据结构,它是由 n n>=0 )个有限结点组成一个具有层次关系的集合。 把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的
  • 有一个特殊的结点,称为根结点,根节点没有前驱结点
  • 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1T2……Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继
  • 因此,树是递归定义的。

注意:树形结构中,子树之间不能有交集,否则就不是树形结构

1.2 树的相关概念

  • 节点的度:一个节点含有的子树的个数称为该节点的度;如上图:A的为6
  • 叶节点或终端节点:度为0的节点称为叶节点;如上图:BCHI...等节点为叶节点
  • 非终端节点或分支节点:度不为0的节点;如上图:DEFG...等节点为分支节点
  • 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;如上图:AB的父节点
  • 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;如上图:BA的孩子节点
  • 兄弟节点:具有相同父节点的节点互称为兄弟节点;如上图:BC是兄弟节点
  • 树的度:一棵树中,最大的节点的度称为树的度;如上图:树的度为6
  • 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
  • 树的高度或深度:树中节点的最大层次;如上图:树的高度为4
  • 堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:HI互为兄弟节点
  • 节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先
  • 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙
  • 森林:由mm>0)棵互不相交的树的集合称为森林;(并查集里面就是多棵树)

 1.3 树的表示(树的存储)

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了, 既然保存值域,也要保存结点和结点之间 的关系 ,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。我们这里就简单的了解其中最常用的孩子兄弟表示法
下面就给大家展示一下这个贼🐂🍺的方法( 左孩子、右兄弟表示法):
struct TreeNode
{int val;struct TreeNode* firstchild;//第一个孩子节点struct TreeNode* nextbroyher;//指向其下一个兄弟节点
}

双亲表示法(只存储父亲的下标或指针)

在很多地方,双亲表示法一般就是用数组的方式直接玩 

这个地方就可以很容易判断出来有几棵树,有几个兄弟。

于是否,两个节点在不在同一棵树,如何判断?

找根,根相同就在同一棵树


其实呢,在实际生活中,我们用的最多的实际上是二叉树

2.二叉树概念及结构

2.1概念

从上图可以看出:
1. 二叉树不存在度大于 2 的结点 (最多两个孩子 也可以是一个或零个)
2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树
注意:对于任意的二叉树都是由以下几种情况复合而成的:

2.2现实中的二叉树

2.3 特殊的二叉树:

1. 满二叉树 (假设它有h层,每一层都是满的) :一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是2的k次方-1 则它就是满二叉树。
2. 完全二叉树 :完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为 K 的,有n 个结点的二叉树,当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 n 的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

2.4 二叉树的性质 

 

1.若规定根节点的层数为 1 ,则一棵非空二叉树的 i 层上最多有 2^(i-1)个结点.
2. 若规定根节点的层数为 1 ,则 深度为 h 的二叉树的最大结点数是2^h-1
3. 对任何一棵二叉树 , 如果度为 0 其叶结点个数为n0  , 度为 2 的分支结点个数为n2  , 则有 n0=n2 + 1
4. 若规定根节点的层数为 1 ,具有 n 个结点的满二叉树的深度 h= log以 2 为底,n+1 为对数
5. 对于具有 n 个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从 0 开始编号,则对于序号为i 的结点有:
1. i>0 i 位置节点的双亲序号: (i-1)/2 i=0 i 为根节点编号,无双亲节点
2. 2i+1<n ,左孩子序号: 2i+1 2i+1>=n 否则无左孩子
3. 2i+2<n ,右孩子序号: 2i+2 2i+2>=n 否则无右孩子

3.二叉树的顺序结构及实现

3.1 二叉树的顺序结构

  parent = (child-1) / 2

任意位置通过下标可以找父亲或者孩子

那如果不是满二叉树或者完全二叉树的话,还适合这个规律吗?显然不可以

那我们这里可以进行总结:

满二叉树 或者 完全二叉树适合用数组存储


3.2 堆的概念及结构

堆的性质:
堆中某个节点的值总是不大于或不小于其父节点的值;
堆总是一棵完全二叉树。

3.3 堆的实现

3.2.1 堆向下调整算法

 我们在这里先来说明一下:

栈:线性表,后进先出

堆:非线性表,完全二叉树

小堆:树中任意一个父亲都 ≤ 孩子

大堆:树中任意一个父亲都 ≥ 孩子

现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是一个堆,才能调整。
intarray[] = {27,15,19,18,28,34,65,49,25,37};

 

底层:

  • 物理结构:数组
  • 逻辑结构:完全二叉树

小堆,底层数组是否升序呢?不一定

小堆的根是整棵树的最小值

 3.2.2堆的创建

下面我们给出一个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆,现在我们通过算法,把它构建成一个堆。根节点左子树不是堆,我们怎么调整呢?这里我们从倒数的第一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆。
inta[] = {1,5,3,8,7,6}; 

 

http://www.fp688.cn/news/158299.html

相关文章:

  • 怎么制作公司的网站武汉大学人民医院光谷院区
  • 厦门公司注册网站网站外链的优化方法
  • 建房子找哪个网站设计长沙seo管理
  • 怎么做网站的一个横向列表如何做企业网页
  • 免费网站空间怎么办2022年新闻摘抄十条
  • 长沙做网站湖南微联讯点不错上海网站seo优化
  • 大兴网站开发网站建设价格百度网页版链接
  • c 网站开发案例详解营销型企业网站诊断
  • 做网站的常识网站策划是做什么的
  • 服务器做jsp网站教程视频教程国外网站排行
  • 成都网站建设成都app开发互联网营销师报名
  • 做公司网站 国外系统广州seo顾问服务
  • wordpress域名解析橘子seo
  • 南岗哈尔滨网站建设短视频入口seo
  • 网站建设域名怎么收费的不受限制的搜索引擎
  • 做网站主色调选择智能营销系统
  • 唐山房产网站建设福州今日头条新闻
  • 做网站怎么学网站接广告平台
  • 上海品牌网站制作seo sem什么意思
  • 新乡做网站的seo网站优化流程
  • 广州微网站建设哪家好有没有好用的网站推荐
  • 石家庄门户网站制作seo快排
  • 珠海网站制作产品如何推广
  • 北京移动端网站优化推广广告
  • 网站建设网站制作哪个好查权重的软件
  • 如何做做网站新闻头条今日新闻60条
  • wordpress ks主题论坛如何做seo
  • 在常州 做兼职上什么网站海外短视频软件
  • 武汉装饰公司前十名是哪几家seo零基础入门教程
  • 武汉网站seo诊断抖音关键词推广