最新公告
  • 欢迎您光临欧资源网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 前驱内容什么是线性表?数据结构之线性表讲解!(组图)

    对于程序员来说,树形数据结构是一种比较常见的数据结构。今天小编就来介绍一下数字的数据结构,然后介绍一个二叉树的简单C语言实现。

    前身内容

    什么是线性表?数据结构线性表说明!

    评论

    首先,让我们回顾一下什么是数据结构。我们之前介绍过。我们在实际使用数据的时候,会结合一些相关的点来使用,这就是结构化数据。我们还介绍了一种简单的数据结构,其特点是一个数据链接到另一个数据链接到前一个数据。最后,这些数据会像一条线一样连接成一个字符串,就是一个线性表。

    什么是树?

    那么,有没有一个数据可以连接多个数据的情况呢?确实有这样的情况,当每个数据连接到多个数据时,就是一个图(后续文章会介绍)。当每条数据后面有0条或更多条数据,前面指的是一条数据相连时,就是一棵树,像这样:

    c语言实现简体转换繁体_操作系统课程设计报告电梯调度算法c语言实现_红黑树 c语言实现

    树状图是由n(n>=1)个有限节点组成一组层次关系的数据结构。之所以称为“树”是因为它看起来像一棵倒挂的树,也就是根朝上,叶子朝下。

    关于树的结构

    我们之前讲过数据之间的关系。对于线性表,一个数据只能连接到另一个数据。这种关系称为一对一关系,即一个数据只能有一个后继节点。

    对于数字来说,一条数据可能连接到一条数据,也可能连接多条数据,甚至可能根本没有数据。这种关系称为一对多关系。

    对于线性表,由于结构比较简单,数据称为前驱节点,后继节点表示数据之间的关系。然而,在树中,它要复杂得多。下面是一个数的结构说明(以下面的树形图为例):

    c语言实现简体转换繁体_操作系统课程设计报告电梯调度算法c语言实现_红黑树 c语言实现

    1、节点:表示树中的数据元素,由数据项和数据元素之间的关系组成。图中一共有10个节点。

    2、节点度数:节点拥有的子树数。图中节点A的度数为3(注意E、F也符合树的定义(树的定义见下文)所以B的度数为2)。

    3、树的度数:树中每个节点的最大度数(节点A和D的度数最大3)。上图中树的度数为3。

    4、叶节点:度数为0的节点,也称为终端节点。上图中节点E、F、G、H、I、J都是叶子节点。

    5、分支节点:度数不为0的节点,也称为非终端节点或内部节点。上图中节点A、B、C、D为分支节点。

    6、Child:节点子树的根。在上图中,节点 B、C 和 D 是节点 A 的子节点。

    7、Parent:节点的上层节点称为节点的父节点。上图中,节点B、C、D的父节点是节点A。

    8、Ancestor:从根到这个节点的分支上的所有节点。上图中红黑树 c语言实现,节点E的祖先是A和B。

    9、后代:子树中以某个节点为根的任何节点。上图中,除A外的所有节点都是A的后代。

    10、兄弟:同父异母的孩子。在上图中,节点 B、C 和 D 是彼此的兄弟节点。

    11、节点级别(Level of Node):从根节点到树中某个节点的路径上的分支数称为节点的级别。根节点的级别指定为1,其余节点的级别等于其父节点的级别加1。

    12、堂兄弟(Sibling):同级不同父节点。上图中,G和H互为表亲。

    13、树的深度:树中节点的最大层数。在上图中,树的深度为 3。

    14、无序树:树中任意节点的子节点之间的顺序构成一棵不相关的树。通常树是指无序树。

    15、有序树:树中任意节点的子节点都严格按顺序排列的树。二叉树是有序树,因为二叉树中的每个子节点都被精确定义为该节点的左子节点或右子节点。

    16、森林:m(m≥0)树的集合。自然界中树和森林的概念有很大不同,但是数据结构中树和森林的概念不同的是很小。从定义上看,一棵树由一个根节点和m个子树组成,如果删除树的根节点,树就变成了包含m棵树的森林。当然,根据定义,树也称为森林。

    如何判断一个节点是否是一棵树(树的定义)有一个且只有一个节点称为根。如果n>1,则除根节点外的其他节点可分为m(m>0)不相交集T1,T2,T3,T4,…,Tm,其中每个集都是一棵树。树T1 , T2, T3,…, Tm 称为这棵树的子树。树的类型树的类型

    无序树

    树的任何一个节点的子节点都没有顺序关系。

    有序树

    树的任意一个节点的子节点都有顺序关系。

    二叉树

    树的任何节点最多包含两个子树。二叉树遍历:二叉树遍历是指从二叉树的根节点开始,按照一定的顺序依次访问二叉树中的所有节点,使得每个节点都被访问一次且仅访问一次。二叉树的访问顺序可以分为四种:前序遍历、中序遍历、后序遍历、分层遍历

    完全二叉树

    叶子节点都在同一级别,除了叶子节点之外的所有节点都有两个孩子。

    c语言实现简体转换繁体_红黑树 c语言实现_操作系统课程设计报告电梯调度算法c语言实现

    完全二叉树

    完全二叉树

    对于一棵二叉树,假设其深度为d(d>1)。除第d层外的所有节点构成一棵全二叉树,第d层的所有节点为从左到右连续紧密排列,使得二叉树称为完全二叉树;

    红黑树 c语言实现_c语言实现简体转换繁体_操作系统课程设计报告电梯调度算法c语言实现

    完全二叉树

    完全二叉树

    c语言实现简体转换繁体_操作系统课程设计报告电梯调度算法c语言实现_红黑树 c语言实现

    完全二叉树

    c语言实现简体转换繁体_红黑树 c语言实现_操作系统课程设计报告电梯调度算法c语言实现

    霍夫曼树

    具有最短加权路径的二叉树称为霍夫曼树或最优二叉树

    二叉搜索树(二叉搜索树、二叉排序树、BST)[这些都是别名]

    如果任一节点的左子树不为空,则左子树中所有节点的值都小于其根节点的值;如果任一节点的右子树不为空,则右子树中所有节点的值都大于其根节点的值;任意节点的左右子树也是二叉搜索树;没有具有相同键值的节点。

    平衡二叉树

    是一棵空树或其左右子树的高度差绝对值不超过1,左右子树都是平衡二叉树。同时,平衡二叉树必须是二叉搜索树。

    AVL 树

    在计算机科学中,AVL 树是第一个被发明的自平衡二叉搜索树。 AVL树中任意节点的两个子树的最大高度差为1,因此也称为高度平衡树。添加和删​​除可能需要一个或多个树旋转来重新平衡树。 AVL树本质上是一棵二叉搜索树,它的特点是:1.本身就是一棵二叉搜索树。 2.带平衡条件:每个节点左右子树高度差的绝对值(平衡因子)最多为1。也就是说红黑树 c语言实现,AVL树本质上是二分查找具有平衡功能的树(二叉排序树,二叉搜索树)。使用场景:AVL树适用于插入和删除的次数比较少,但查找次数较多的情况。它也用于 Windows 进程地址空间管理。旋转的目的是降低树的高度并使其平衡

    红黑树

    红黑树是一种二叉搜索树,其中每个节点都有一个颜色属性,红色或黑色。除了二叉搜索树强制执行的一般要求之外,对于任何有效的红黑树,我们添加以下附加要求:属性 1. 节点是红色或黑色。属性2. 根节点为黑色。 Properties3. 每个红色节点的两个子节点都是黑色的。 (从每个叶子到根的所有路径上不能有两个连续的红色节点) 属性 4. 从任何节点到每个叶子的所有路径都包含相同数量的黑色节点。使用场景:红黑树多用于搜索、插入、删除操作。红黑树被广泛使用:1. 在 C++ STL 中被广泛使用。 map 和 set 都是用红黑树实现的。 2.著名的linux进程调度Completely Fair Scheduler使用红黑树来管理进程控制块。 3.epoll在内核中实现,使用红黑树管理事件块4.nginx,使用红黑树管理定时器等

    传播树

    Splay Tree,也称为分裂树,是一种二叉排序树,可以在 O(log n) 内进行插入、查找和删除操作。它是由 Daniel Sleator 和 Robert Endre Tarjan 于 1985 年发明的。伸展树上的一般操作都是基于伸展操作:假设你想对一棵二叉搜索树进行一系列搜索操作,为了使整体搜索时间更小,那些经常搜索的条目应该总是位于靠近树的根。的位置。所以我想到了设计一个简单的方法,在每次搜索后重建树,并将搜索到的项目移动到更靠近树根的地方。伸展树应运而生。展开树是一种自调整形式的二叉搜索树,它通过沿从节点到根的路径的一系列旋转将节点移动到根。它的优点是不需要记录冗余信息来平衡树。

    替罪羊树

    替罪羊树是计算机科学中基于部分重构的自平衡二叉搜索树。在替罪羊树上,插入或删除节点的摊销最坏时间复杂度为 O(log n),搜索节点的最坏时间复杂度为 O(log n)。在不平衡二叉搜索树中,每次操作后检查操作路径,找到满足max(size(son_L),size(son_R))>alpha*size(this)的最高节点,重建整个子树。这样就得到了替罪羊树,重建子树的原始根称为替罪羊节点。替罪羊树 替罪羊树是由 Arne Andersson 提出的自平衡二叉搜索树。替罪羊树的主要思想是将不平衡的树压成序列,然后暴力重构平衡树。

    B-tree(B-tree或B-tree)

    m 阶平衡树是平衡的 m 向搜索树。它要么是一棵空树,要么是一棵满足以下性质的树: 1、根节点至少有两个孩子; 2、每个非根节点包含的关键字j个数满足:┌m /2┐ – 1

    站内大部分资源收集于网络,若侵犯了您的合法权益,请联系我们删除!
    欧资源网 » 前驱内容什么是线性表?数据结构之线性表讲解!(组图)

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    欧资源网
    一个高级程序员模板开发平台

    发表评论