大部分为摘录自wiki
树状图是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:
- 每个节点有零个或多个子节点;
- 没有父节点的节点称为根节点;
- 每一个非根节点有且只有一个父节点;
- 除了根节点外,每个子节点可以分为多个不相交的子树;
术语:
- 节点的度:一个节点含有的子树的个数称为该节点的度;
- 树的度:一棵树中,最大的节点的度称为树的度;
- 叶节点或终端节点:度为零的节点;
- 非终端节点或分支节点:度不为零的节点;
- 父亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;
- 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
- 兄弟节点:具有相同父节点的节点互称为兄弟节点;
- 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
- 树的高度或深度:树中节点的最大层次;
- 堂兄弟节点:父节点在同一层的节点互为堂兄弟;
- 节点的祖先:从根到该节点所经分支上的所有节点;
- 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
- 森林:由m(m>=0)棵互不相交的树的集合称为森林;
数的种类:
- 无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树;
- 有序树:树中任意节点的子节点之间有顺序关系,这种树称为有序树;
二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有个结点;深度为k的二叉树至多有个结点;对任何一棵二叉树T,如果其终端结点数为,度为2的结点数为,则。
一棵深度为k,且有个节点称之为满二叉树;深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为完全二叉树。(简单说,就是每一层都是满的二叉树为满二叉树;只有最后一层不满,并且最后一层的节点都是占据了左边的连续位置的二叉树为完全二叉树)
与树不同,树的结点个数至少为1,而二叉树的结点个数可以为0;树中结点的最大度数没有限制,而二叉树结点的最大度数为2;树的结点无左、右之分,而二叉树的结点有左、右之分。
访问二叉树的方法
前(先)序、中序、后序遍历
二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sorted binary tree),是指一棵空树或者具有下列性质的二叉树:
- 若任意节点的左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;
- 任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
- 任意节点的左、右子树也分别为二叉查找树。
- 没有键值相等的节点(英语:no duplicate nodes)。
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合、multiset、关联数组等。
二叉查找树的查找过程和次优二叉树类似,通常采取二叉链表作为二叉查找树的存储结构。中序遍历二叉查找树可得到一个关键字的有序序列,一个无序序列可以通过构造一棵二叉查找树变成一个有序序列,构造树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点,在进行插入操作时,不必移动其它结点,只需改动某个结点的指针,由空变为非空即可。搜索、插入、删除的复杂度等于树高,期望,最坏(数列有序,树退化成线性表)。
虽然二叉查找树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉查找树可以使树高为,如SBT,AVL树,红黑树等.故不失为一种好的动态查找方法.
堆(英语:heap),是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中,调度程序反复提取队列中第一个作业并运行,因为实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。
堆的实现通过构造二叉堆(binary heap),实为二叉树的一种;由于其应用的普遍性,当不加限定时,均指该数据结构的这种实现。这种数据结构具有以下性质。
- 任意节点小于它的所有后裔,最小元在堆的根上(堆序性)。
- 堆总是一棵完全树。
将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
操作:
1.插入节点:从堆尾部插入。然后调整顺序,从堆尾开始逐个和其根元素比较,并调整。
2.删除节点:删除根节点。然后,把堆存储的最后那个节点移到填在根节点处。再从上而下调整父节点与它的子节点:对于最大堆,父节点如果小于具有最大值的子节点,则交换二者。直至当前节点与它的子节点满足堆性质为止。
相关推荐
本文详细罗列归纳了Python常见数据结构,并附以实例加以说明,相信对读者有一定的参考借鉴价值。 总体而言Python中常见的数据结构可以统称为容器(container)。而序列(如列表和元组)、映射(如字典)以及集合...
本文详细罗列归纳了Python常见数据结构,并附以实例加以说明,相信对读者有一定的参考借鉴价值。 总体而言Python中常见的数据结构可以统称为容器(container)。而序列(如列表和元组)、映射(如字典)以及集合...
数据结构教材8种常见排序算法用c++代码编码实现,而且测试过啦,都能够正确运行
其实归纳起来就两类:一是用传统RDBMS为主导的数据库管理数据,oracle、mysql等都是基于传统的关系型数据库,优势就是有更严谨的数据结构,关系型数据库对数据的管理更加规范,数据处理过程中可能出现的非人为误差...
3. 描述主题列表中各数据结构常见的应用。 4. 用高级语言实现用户自定义的数据结构。 5. 比较数据结构的不同实现的性能。 6. 编写使用以下各种数据结构的程序:数组、记录、字符串、链表、栈、队列和哈希表。 7. ...
本书共分8篇,分别为基础篇、数据结构篇、数值计算与趣味数学篇、图形篇、系统篇、常见试题解答篇、游戏篇和综合实例篇,汇集了近200个实例,基本涵盖了目前C语言编程的各个方面。 书中以具体的实例为线索,特别...
全书共分12章:第1章到第4章为介绍性内容,涉及数学归纳法、算法分析、数据结构等内容;第5章提出了与归纳证明进行类比的算法设计思想;第6章到第9章分别给出了4个领域的算法,如序列和集合的算法、图算法、几何算法...
数据挖掘与数据分析 数据挖掘与数据分析 ⼀、数据挖掘和数据分析概述 数据挖掘和数据分析都是从数据中提取⼀些有价值的信息,⼆者有很多联系,但是⼆者的侧重点和实现⼿法有所区分。 数据挖掘和数据分析的不同之处:...
数据结构 273 Array方法类汇总 304 Java数组与集合小结 305 递归 309 对象的序列化 310 Java两种线程类:Thread和Runnable 315 Java锁小结 321 java.util.concurrent.locks包下常用的类 326 NIO(New IO) 327 ...
本书共分8篇,分别为基础篇、数据结构篇、数值计算与趣味数学篇、图形篇、系统篇、常见试题解答篇、游戏篇和综合实例篇,汇集了近200个实例,基本涵盖了目前C语言编程的各个方面。 书中以具体的实例为线索,特别...
由于VBA在语言特性方面并不完备,List 等常见数据结构以及相关算法依赖于使用者进行实现,并且惟一内置的 Dictionary 也需要另外进行引入,使得VBA 比之Python对于新手不甚友好。但是在Windows平台下,Excel的普及...
《C语言实例解析精粹第二版》一书主要讲解C语言编程涉及的各类常见实例,共分8篇,以“基础篇→数据结构篇→数值计算与趣味数学篇→图形篇→系统篇→常见试题解答篇→游戏篇→综合实例篇”具体展开,共汇集220个实例...
本书共分 8 篇,分别为基础篇、数据结构篇、数值计算与趣味数学篇、图形篇、系统篇、常见试题解答篇、游戏篇和综合实例篇,汇集了近 200 个实例,基本涵盖了目前C 语言编程的各个方面。 书中以具体的实例为线索,...
常见问题目录 本光盘的使用方法:点击感兴趣的问题,就可以链接到该问题的答案。所有文件都是用WORD打开的。在点击所要看的问题时,请同时按住Control键(Ctrl)。 第1章 概述 问题1-1:“主机”和“计算机”一样不...
软件设计 概要设计 模块分解,确定软件的结构,模块的功能和模块间的接口,以及全局数据结构的设计 系统分析员、高级程序员 设计说明书、数据说明书、模块开发卷宗 详细设计 设计每个模块的实现细节和局部数据结构...
丰富的 Java 技术栈:基础和框架,线程池和锁优化,SpringBoot 和分布式消息队列,数据结构和常用算法,设计模式和 JVM 等 易学易会:提供了大量的图片说明和代码示例 你会获得什么 收获 Java 技术栈的核心知识点 这...
在使用与数据结构有关的标签进行筛选并完成相关题目时,应侧重对数据结构的常见用法,相应容器的常用成员函数的熟悉和理解。 在使用与算法有关的标签进行筛选时,应使用相应的算法类型完成题目,并归纳总结该类题目...
数据字典通常包括数据项、数据结构、数据流、数据存储和处理过程五个部分。其中数据项是数据的最小组成单位,若干个数据项可以组成—个数据结构。 《数据库技术与应用》第14章数据库设计-习题答案全文共5页,当前为...
(2)必然性,⼤数据所产⽣的数据量必然要求⼈们对数据进⾏归纳总结,对数据的结构和形式进⾏转换处理。 (3)⽚⾯性,数据可视化的⽚⾯性特征要求可视化模式不能替代数据本⾝,只能作为数据表达的⼀种特定形式。 ...
★★★字符串去除字符串首尾空格 ★算法算法需要掌握基本的数据结构,例如栈、队列、链表、树、排序算法等等,建议去 LeetCode 上刷题。不过不要为了刷题而刷题,最重要的是归纳与总结,刷十道不如一道刷十遍。归并...