数据结构详解

基本数据结构与算法交流数据结构详解全文共163页，当前为第1页。CONTENTS绪论1线性表2栈与队列3串4树5图6排序算法7数据结构详解全文共163页，当前为第2页。1绪论什么是数据结构数据结构的基本概念抽象数据类型基本概念算法效率的度量数据结构详解全文共163页，当前为第3页。什么是数据结构数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程关系对象关系操作数学软件硬件对象关系操作数据结构详解全文共163页，当前为第4页。为什么学习数据结构

程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。数据结构详解全文共163页，当前为第5页。

算法+数据结构=程序6数据结构的重要性：结构化编程（代表语言TurboC）：程序=（算法）+（数据结构）面向对象编程(代表语言Java、Delphi、c++)：对象=（算法+数据结构）

程序=对象+对象程序设计:为计算机处理问题编制一组指令集算法:处理问题的策略数据结构：问题的数学模型数据结构详解全文共163页，当前为第6页。登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片按书名按作者名按分类号数据结构实际应用——索引索引数据结构详解全文共163页，当前为第7页。8树……..……..…...…...…...…...数据结构实际应用——人机对弈数据结构详解全文共163页，当前为第8页。FBDDAE54798612282数据结构实际应用——最短路径图C数据结构详解全文共163页，当前为第9页。数据结构详解全文共163页，当前为第10页。数据结构详解全文共163页，当前为第11页。数据结构实际应用——HashMap数据结构详解全文共163页，当前为第12页。数据结构详解全文共163页，当前为第13页。抽象数据类型基本概念数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素(dataelement)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(Dataitem)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性等）。数据对象（Dataobject）——是性质相同的数据元素的集合，是数据的一个子集（如整数数据，字母数据等）。三者之间的关系：数据>数据元素>数据项例：班级通讯录>个人记录>姓名、年龄……数据结构详解全文共163页，当前为第14页。数据结构涵盖的内容数据结构详解全文共163页，当前为第15页。算法效率的度量Q1.什么是算法？算法的设计原则？Q2.算法效率的衡量方法与准则？Q3.算法的存储空间需求？问题：数据结构详解全文共163页，当前为第16页。程序设计实质＝好算法＋好结构答：算法是解决某一特定类型问题的有限运算序列。是一系列输入转换为输出的计算步骤。常用时间复杂度来衡量Q1.什么是算法？如何评判一个算法的好坏？算法有5个基本特性：算法评价有4个指标：有穷性、确定性、可行性、输入和输出运行时间、占用空间、正确性和简单性常用空间复杂度来衡量数据结构详解全文共163页，当前为第17页。Q2算法效率的衡量方法和准则通常有两种衡量算法效率的方法:1.事后统计法缺点：1．必须执行程序

2．其它因素掩盖算法本质（如计算机的硬件、软件等环境因素，有时掩盖算法本身优劣）数据结构详解全文共163页，当前为第18页。2.事前分析估算法（1）算法选用的策略（2）数据的规模（3）编写程序的语言（4）编译程序产生的机器代码的质量（5）计算机执行指令的速度算法执行时间相关的因素：数据结构详解全文共163页，当前为第19页。时间复杂度的计算O(1)O(n)O(n2)intsum=0,n=100; /*执行一次*/sum=(1+n)*n/2; /*执行一次*/Printf(“%d”,sum); /*执行一次*/intsum=0,n=100; /*执行一次*/for(i=1;i<=n;i++){ /*执行n+1次*/sum=sum+I; /*执行n次*/}printf(“%d”,sum); /*执行1次*/intsum=0,n=100; /*执行一次*/for(i=1;i<=n;i++){ /*执行n+1次*/for(j=1;j<=n;j++){x++; /*执行n2次*/sum=sum+x;}}printf(“%d”,sum); /*执行1次*/数据结构详解全文共163页，当前为第20页。时间复杂度的计算推导大O阶：1.用常数1取代运行时间中的所有加法常数2.在修改后的运行次数函数中，只保留最高阶项3.如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶数据结构详解全文共163页，当前为第21页。2线性表2.1线性表的逻辑结构2.2线性表的顺序存储结构2.3线性表的链式存储结构数据结构详解全文共163页，当前为第22页。（a1,a2,…ai-1，ai,ai＋1

，…,an）2.1

线性表的类型定义1.线性表的定义：零或多个数据元素的有限序列n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点数据结构详解全文共163页，当前为第23页。线性结构的基本特征:3.除最后元素在外，均有唯一的后继；4.除第一元素之外，均有唯一的前驱。在数据元素的非空有限集中线性表是一种最简单的线性结构

1.集合中必存在唯一的一个“第一元素”；2.集合中必存在唯一的一个“最后元素”

；数据结构详解全文共163页，当前为第24页。例1分析26个英文字母组成的英文表

（A,B,C,D,……,Z）姓name性别年龄班级011810205于春梅女18电信016班011810260何仕鹏男18电信017班011810284王爽女18通信011班011810360王亚武男18通信012班：：：

：：例2分析学生情况登记表数据元素都是记录;元素间关系是线性数据元素都是字母;元素间关系是线性同一线性表中的元素必定具有相同特性数据结构详解全文共163页，当前为第25页。2.线性表的类型定义数据结构详解全文共163页，当前为第26页。2.2线性表的顺序存储结构2.2.1顺序表的表示2.2.2顺序表的实现2.2.3顺序表的运算效率分析数据结构详解全文共163页，当前为第27页。2.2.1顺序表的表示指的是用一段地址连续的存储单元依次存储线性表的数据元素顺序存储定义：顺序存储示意图：可用数组来实现数据结构详解全文共163页，当前为第28页。线性表顺序存储特点：1.

逻辑上相邻的数据元素，其物理上也相邻；2.

若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为C字节，则表中任一数据元素的存放地址为： LOC(ai+1)=LOC(ai)+C

LOC(ai)=LOC(a1)+C*（i-1）

数据结构详解全文共163页，当前为第29页。2.2.2顺序表基本操作修改、插入、删除、查找、排序1)修改通过数组的下标便可访问某个特定元素并修改。核心语句:

V[i]=x;显然，顺序表修改操作的时间效率是T(n)=O(1)数据结构详解全文共163页，当前为第30页。2)插入在线性表的第i个位置前插入一个元素实现步骤：(n为表长）将第n至第i位的元素向后移动一个位置；将要插入的元素写到第i个位置；表长加1。数据结构详解全文共163页，当前为第31页。实现步骤：(n为表长）将第i至第n位的元素向前移动一个位置；表长减1。3)删除删除线性表的第i个位置上的元素数据结构详解全文共163页，当前为第32页。2.2.3顺序表的运算效率分析最好情况：插入在最后一个位置，O(1)最坏情况：插入在第一个位置，O(n)平均情况：平均移动n/2时间复杂度为O(n)插入时间效率分析:数据结构详解全文共163页，当前为第33页。2.2.3顺序表的优缺点优点无须为表示表中元素之间的逻辑关系而增加额外的存储空间可以快速地存取表中任一位置的元素缺点插入和删除操作需要移动大量元素当线性表长度变化较大时，难以确定存储空间的容量造成存储空间的“碎片”数据结构详解全文共163页，当前为第34页。2.3线性表的链式存储结构2.3.1链表的表示2.3.2链表的实现{单链表，循环链表，双向链表}数据结构详解全文共163页，当前为第35页。特点：逻辑上相邻，物理上不一定相邻链表中第一个结点的存储位置叫头指针每个存储结点都包含两部分：数据域和指针域(链域)线性链表的最后一个结点指针为空，通常用NULL或^表示2.3.1链表的表示存储结构：如下图示意数据结构详解全文共163页，当前为第36页。有时为了方便操作，会在单链表的第一个结点前附设一个结点，叫做头结点头结点数据域可不存储任何信息，也可存储线性表长度等附加信息数据结构详解全文共163页，当前为第37页。2.3.2链表的实现1.单链表2.循环链表3.双向链表数据结构详解全文共163页，当前为第38页。1.单链表空链表：读取或修改：数据结构详解全文共163页，当前为第39页。1.单链表插入：数据结构详解全文共163页，当前为第40页。1.单链表删除：数据结构详解全文共163页，当前为第41页。1.单链表单链表和顺序存储结构对比数据结构详解全文共163页，当前为第42页。2.循环链表将单链表中断结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表空循环链表：添加、删除操作与单链表对应操作相同数据结构详解全文共163页，当前为第43页。3.双向链表单链表的每个结点中，再设置一个指向其前驱结点的指针域，这样的链表简称循环链表空双向链表：数据结构详解全文共163页，当前为第44页。3.双向链表插入：删除：数据结构详解全文共163页，当前为第45页。3.1栈（Stack）3.2队列（Queue）

3栈和队列1.基本介绍2.抽象数据类型3.顺序存储结构4.链式存储结构1.基本介绍2.抽象数据类型3.顺序存储结构4.链式存储结构数据结构详解全文共163页，当前为第46页。3.1栈（Stack）1.基本介绍2.抽象数据类型3.顺序存储结构4.链式存储结构数据结构详解全文共163页，当前为第47页。例如：栈S=(a1,a2,a3,……….,an-1,an

)插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。an称为栈顶元素a1称为栈底元素强调：插入和删除都只能在表的一端（栈顶）进行！栈是仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶/top；表头(a1端)称为栈底/base子弹夹就是典型的栈数据结构详解全文共163页，当前为第48页。栈的抽象数据类型定义数据结构详解全文共163页，当前为第49页。栈的顺序存储结构栈的顺序存储称为顺序栈，它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶的位置数据结构详解全文共163页，当前为第50页。顺序栈的入栈操作——例如用堆栈存放（A，B，C，D）AACBABAtoptoptoptoptop低地址L高地址MBCD数据结构详解全文共163页，当前为第51页。顺序栈出栈操作——例如从栈中取出‘B’DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址M数据结构详解全文共163页，当前为第52页。共享栈思考：两个相同类型的栈，各自开辟了数组空间，极有可能第一个栈满了，而另一个栈还有很多存储空间，如何解决这个问题？共享栈：将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸优点：有效利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才会发生上溢，存取时间复杂度均为O(1)数据结构详解全文共163页，当前为第53页。栈的链式存储结构采用链式存储的栈称为链栈。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的优点：便于多个栈共享存储空间，和提高其效率，且不存在栈满上溢的情况链栈的操作与链表类似，在此不做详细讨论对于带头结点和不带头结点的链栈，具体的实现方面有所不同需要注意数据结构详解全文共163页，当前为第54页。3.2队列（Queue）1.基本介绍2.抽象数据类型3.顺序存储结构4.链式存储结构数据结构详解全文共163页，当前为第55页。队列（Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。它是一种先进先出（ＦＩＦＯ）的线性表。例如：队列Q=(a1

,a2,a3,……….,an-1,an)在队尾插入元素称为入队；在队首删除元素称为出队。队头队尾问：为什么要设计队列？它有什么独特用途？离散事件的模拟（模拟事件发生的先后顺序,例如CPU芯片中的指令译码队列）；操作系统中的作业调度（一个CPU执行多个作业）；3.简化程序设计。答：数据结构详解全文共163页，当前为第56页。队列的抽象数据类型数据结构详解全文共163页，当前为第57页。队列的顺序存储结构队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针front和rear，队头指针指向队头元素，队尾指针指向队尾元素的下一个位置。Q(队尾)(队首)fronta1a2a3dataa40.......99rear队尾后地址e数据结构详解全文共163页，当前为第58页。顺序队列的入队操作：afrontrearrearfrontfrontfrontrearrear空队5个元素入队出队1次出队3次bcdebcdee数据结构详解全文共163页，当前为第59页。队列顺序存储结构的不足假溢出！数据结构详解全文共163页，当前为第60页。解决方案：循环队列将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上看成一个环，称为循环队列数据结构详解全文共163页，当前为第61页。a3a2a10123N-1rearfront循环队列（臆造）新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案有三：①使用一个计数器记录队列中元素个数（即队列长度）；②加设标志位，删除时置1,插入时置0,则可识别当前front=rear属于何种情况③人为浪费一个单元，则队满特征可改为front=(rear+1)%N；顺序队列a3a2a1frontrear0123..N-1数据结构详解全文共163页，当前为第62页。队空条件:front=rear(初始化时：front=rear)队满条件：front=(rear+1)%N(N=maxsize)队列长度（即数据元素个数）：L=（N＋rear－front）%NJ2J3

J1J4

J5frontrear

实际中常选用方案3（人为浪费一个单元）：即front和rear二者之一指向实元素，另一个指向空闲元素。

在具有n个单元的循环队列中，队满时共有N-1个元素左图中队列maxsizeN=6左图中队列长度L=5数据结构详解全文共163页，当前为第63页。队列的链式存储结构队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表空队列：数据结构详解全文共163页，当前为第64页。队列的链式存储结构入队：出队：数据结构详解全文共163页，当前为第65页。串（String）4.1串的基本概念4.2串的比较4.3串的抽象数据类型4.4串的存储结构4.5串的匹配算法数据结构详解全文共163页，当前为第66页。串长：串中字符个数（n≥0）.n=0时称为空串。空串：零个字符的串。空白串：由一个或多个空格符组成的串。字串：串s中任意个连续的字符序列叫s的子串;s叫主串。字串的位置：子串的第一个字符的序号。字符位置：字符在串中的序号。串相等：串长度相等，且对应位置上字符相等。

串是由零个或多个字符组成的有限序列，又名叫字符串例如：串S=“a1a2a3……….an-1an

”数据结构详解全文共163页，当前为第67页。4.2串的比较给定两个串：s=“a1a2……an”,t=“b1b2……bm”,当满足一下条件之一时，s<t。1.n<m，且ai=bi(i=1,2,……，n)例如：s=“hap”,t=“happy”,s<t2.存在某个k<=min(m,n),使得ai=bi(i=1,2,……，k-1),ak<bk例如：s=“happen”,t=“happy”,前四个字母相同，两串第五个字母，s串‘e’的ASCII码是101，而字母‘y’的ASCII码是121，显然e<y，所以s<t数据结构详解全文共163页，当前为第68页。4.3串的抽象数据类型数据结构详解全文共163页，当前为第69页。4.4串的存储结构定长顺序存储表示——用一组地址连续的存储单元存储串值的字符序列堆分配存储表示——用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。串的块链存储表示——链式方式存储首先强调：串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。链式存储顺序存储数据结构详解全文共163页，当前为第70页。定长顺序存储：

用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。堆分配存储：

仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。数据结构详解全文共163页，当前为第71页。讨论：法1存储密度为

；法2存储密度为

；显然，若数据元素很多，用法2存储更优—称为块链结构链式存储：用链表存储串值，易插入和删除。法1：链表结点（数据域）大小取1法2：链表结点（数据域）大小取n(例如n=4)1/29/15=3/5存储密度=串值所占的存储位/实际分配的存储位A.B.C.INULL……BACD.FEGH.#I##NULL数据结构详解全文共163页，当前为第72页。73算法目的：确定主串中所含子串第一次出现的位置（定位）

——即如何实现Index(S,T,pos)函数4.3串的模式匹配算法模式匹配(PatternMatching)即子串定位运算（Index函数）两种模式匹配算法： 1.朴素模式匹配算法 2.KMP模式匹配算法数据结构详解全文共163页，当前为第73页。朴素模式匹配算法(BF算法)简单的说，就是对主串的每一个字符作为字串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做小循环，直到匹配成功，或全部遍历完为止。若匹配成功，则将S中与T匹配的子序列第一个字符的序号返回举例：主串S=“goodgoogle”,字串T=“google”数据结构详解全文共163页，当前为第74页。树和二叉树（Tree&BinaryTree）5.1树的基本概念5.2树的抽象数据类型5.3树的存储结构5.4二叉树5.5树和森林5.6赫夫曼树及其应用数据结构详解全文共163页，当前为第75页。5.1树的基本概念树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中：(1)有且仅有一个特定的称为根(Root)的结点；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、……、Tm,其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)数据结构详解全文共163页，当前为第76页。注意1.n>0时根结点是唯一的，不可能存在多个根结点2.m>0时子树的个数没有限制，但它们一定是互不相交的5.3树的基本概念数据结构详解全文共163页，当前为第77页。结点分类结点的度：结点拥有的子树叶结点(终端结点)：度为0的结点分支结点(非终端结点)：度不为0的结点树的度：树内各结点的度的最大值5.3树的基本概念数据结构详解全文共163页，当前为第78页。结点间关系结点的子树的根称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称兄弟(Silbing)。结点的祖先是从根结点到该结点所经分支上的所有结点。以某结点为根的子树中任一结点都称为该结点的子孙。对于H来说，D、B、A都是它的祖先对B来说，D、G、H、I都是它的子孙5.3树的基本概念数据结构详解全文共163页，当前为第79页。树的分层结点的层次(Level)：从根开始定义起，根为第一层，根的孩子为第二层,以此类推。堂兄弟：双亲在同一层的结点。结点的深度：是从根节点开始自顶向下逐层累加结点的高度：从叶节点开始自底层向上逐层累加树的深度(Depth)或高度：树中结点最大层次5.3树的基本概念数据结构详解全文共163页，当前为第80页。树的其他概念D、E、F互为堂兄弟当前树的深度为4如果书中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。路径长度：路径上所经过的边的个数森林是m(m>=0)棵互不相交的树的集合5.3树的基本概念数据结构详解全文共163页，当前为第81页。树的性质1)树中的结点数等于所有结点的度数加12)度为m的树中第i层上至多有mi-1个结点（i>=1）3)高度为h的m叉树至多有(mh-1)/(m-1)个结点4)具有n个结点的m叉树的最小高度为[logm(n(m-1)+1)]5.3树的基本概念数据结构详解全文共163页，当前为第82页。树与线性表的对比5.3树的基本概念数据结构详解全文共163页，当前为第83页。5.3树的抽象数据类型数据结构详解全文共163页，当前为第84页。5.3树的存储结构说到存储，我们会想起顺序存储和链式存储两种结构。简单的顺序存储结构不能满足树的实现要求充分利用顺序存储和链式存储的特点，可以实现对树的存储结构的实现存储结构：①双亲表示法②孩子表示法③孩子兄弟表示法数据结构详解全文共163页，当前为第85页。5.3树的存储结构①双亲表示法思路：用一组连续空间来存储树的结点，同时在每个结点中附设一个指示器，指示其双亲结点在链表中的位置。parentsdata结点结构dataparents1树结构

23n数据结构详解全文共163页，当前为第86页。缺点：求结点的孩子时需要遍历整个结构。5.3树的存储结构①双亲表示法实际中权限菜单的结构设计。数据结构详解全文共163页，当前为第87页。存储结构的设计是一个非常灵活的过程。一个存储结构设计的是否合理，取决于基于该存储结构的运算是否合适、是否方便，时间复杂度好不好等5.3树的存储结构①双亲表示法拓展长子域数据结构详解全文共163页，当前为第88页。5.3树的存储结构②孩子表示法思路：将每个结点的孩子结点都用单链表链接起来形成一个线性结构，则N个结点就有N个孩子链表（叶子结点的孩子链表为空表）优缺点：寻找子女的操作非常直接，而寻找双亲需要遍历N个结点abecdfhgdefghgfedcbah12345678bc数据结构详解全文共163页，当前为第89页。5.3树的存储结构③孩子兄弟表示法思路：用二叉链表来表示树，但链表中的两个指针域含义不同。左指针指向该结点的第一个孩子；右指针指向该结点的下一个兄弟结点。nextsiblingdatafirstchild指向左孩子指向右兄弟数据结构详解全文共163页，当前为第90页。abecdfhgbacedfgh③孩子兄弟表示法5.3树的存储结构数据结构详解全文共163页，当前为第91页。5.4二叉树为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。1. 二叉树的基本概念2. 二叉树的性质3. 二叉树的存储结构数据结构详解全文共163页，当前为第92页。1.二叉树的基本概念定义：是n（n≥0）个结点的有限集合，该集合或者为空集，或者由一个根结点以及至多两棵互不相交的、分别称为左子树和右子树的二叉树组成。5.4二叉树特点：

每个结点最多有两棵子树

左右子树有顺序，次序不能任意颠倒

即使树中某结点只有一棵子树，也要区分它是左子树还是右子树数据结构详解全文共163页，当前为第93页。5.4二叉树

具有3个结点的二叉树可能有几种不同形态？普通树呢？2、二叉树的五种基本形态1.空二叉树2.只有一个根结点3.根结点只有左子树4.根结点只有右子树5.根结点既有左子树又有右子树

数据结构详解全文共163页，当前为第94页。满二叉树：一棵高度为h，并且含有2h-1个结点的二叉树称为满二叉树，即树中的每一层都含有最多的结点5.4二叉树121234567111089131415满二叉树按层序编号：约定编号从根结点（根结点编号为1）起，自上而下，自左向右。这样每个结点对应一个编号，对编号为i的结点，如果有双亲，其双亲为[i/2]，如果有左孩子，则左孩子为2i；如果有右孩子，则右孩子为2i+13、特殊二叉树——满二叉树数据结构详解全文共163页，当前为第95页。4、特殊二叉树——完全二叉树完全二叉树：设一个高度为h，有n个结点的二叉树，当且仅当其每一个结点都与高度为h的满二叉树编号为1~n的结点一一对应时，称为完全二叉树5.4二叉树12345671089完全二叉树特点：1.叶子结点只能出现在最下两层2.倒数第二层，若有叶子结点，一定都在右部连续位置3.去掉最后一层，则必为满二叉树数据结构详解全文共163页，当前为第96页。5、特殊二叉树——二叉排序树、平衡二叉树

二叉排序树：一棵二叉树或空二叉树，或者是具有如下性质的二叉树：左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点的关键字均大于根结点的关键字。左子树和右子树又各是一棵二叉排序树5.4二叉树平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1数据结构详解全文共163页，当前为第97页。1.二叉树性质性质1：在二叉树的第i层上至多有2i-1个结点(i>=1)5.4二叉树性质2：深度为k的二叉树至多有2k-1个结点(k>=1)性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1性质4：具有n个结点的完全二叉树的深度为[log2n]+1([x]表示不大于x的最大整数)数据结构详解全文共163页，当前为第98页。2.二叉树性质性质5：如果对一棵有n个结点的完全二叉树(其深度为[log2n]+1)的结点按层编号（从第1层到第[log2n]+1层，每层从左到右），对任一结点i(1<=i<=n)有： 1）如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点[i/2] 2）如果2i>n，则结点i无左孩子(结点i为叶子结点)；否则其左孩子是结点2i 3）如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+15.4二叉树数据结构详解全文共163页，当前为第99页。5.4二叉树3.二叉树的存储结构顺序存储结构按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。可按照完全二叉树的编号，把不存在的结点设置为缺点：①浪费空间；②插入、删除不便顺序存储结构一般只用于完全二叉树数据结构详解全文共163页，当前为第100页。5.4二叉树3.二叉树的存储结构链式存储结构（二叉链表）数据结构详解全文共163页，当前为第101页。二叉树的遍历是指从根结点出发，按照某种次序一次访问二叉树中所有的结点，使得每个结点被访问一次且仅被访问一次二叉树遍历方法：①前序遍历②中序遍历③后续遍历④层序遍历5.4二叉树4.遍历二叉树数据结构详解全文共163页，当前为第102页。①前序遍历规则：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树5.4二叉树4.遍历二叉树数据结构详解全文共163页，当前为第103页。②中序遍历规则：若二叉树为空，则空操作返回，否则从根结点开始(注意并不是先访问根结点)，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树5.4二叉树4.遍历二叉树数据结构详解全文共163页，当前为第104页。③后序遍历规则：若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。4.遍历二叉树5.4二叉树数据结构详解全文共163页，当前为第105页。④层序遍历规则：若二叉树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。5.4二叉树4.遍历二叉树数据结构详解全文共163页，当前为第106页。④层序遍历规则：若二叉树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。5.4二叉树4.遍历二叉树数据结构详解全文共163页，当前为第107页。5.3树和森林树转换为二叉树1.加线：在所有兄弟结点之间加一条连线2.去线：对书中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子系欸但之间的连线3.层次调整：以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。数据结构详解全文共163页，当前为第108页。5.3树和森林树转换为二叉树数据结构详解全文共163页，当前为第109页。5.3树和森林森林转换为二叉树步骤：1.把每个树转换为二叉树2.第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树森林是由若干棵树组成的，所以完全可以理解为，森林中的每一棵树都是兄弟，可以按照兄弟的处理办法来操作数据结构详解全文共163页，当前为第110页。5.3树和森林森林转换为二叉树数据结构详解全文共163页，当前为第111页。5.3树和森林二叉树转换为树步骤：1.加线。若某结点的左孩子结点存在，则将左孩子的n个右孩子结点用线连接起来2.去线。删除原二叉树中所有结点与其右孩子结点的连线3.层次调整，使之结构层次分明二叉树转换为树是树转换为二叉树的逆过程，也就是反过来做而已数据结构详解全文共163页，当前为第112页。5.3树和森林二叉树转换为树数据结构详解全文共163页，当前为第113页。5.3树和森林二叉树转换为森林步骤：1.从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除，直到所有的右孩子连线都删除为止，得到分离的二叉树2.将每棵分离后的二叉树转换为树判断一棵二叉树能够转换成一棵树还是森林，标准很简单，就是只要看这棵树的根结点有没有右孩子，有就是森林，没有就是一棵树数据结构详解全文共163页，当前为第114页。5.3树和森林二叉树转换为森林数据结构详解全文共163页，当前为第115页。5.4哈夫曼树哈夫曼树的引例效率相对低效率相对高数据结构详解全文共163页，当前为第116页。5.4哈夫曼树哈夫曼树的定义在许多实际应用中，树中结点常常被赋予一个表示某种意义的数值，称为该结点的权。从树根结点到任意结点的路径长度与该结点上权值的乘积称为该结点的带权路径长度树中所有的叶结点的带权路径长度之和称为该树的带权路径长度记为Wi是第i个叶结点所带的权值；li是该叶结点到根结点的路径长度在含有N个带权叶子结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树，也称为最优二叉树数据结构详解全文共163页，当前为第117页。5.4哈夫曼树带权路径长度计算(a)WPL=7*2+5*2+2*2+4*2=36(a)WPL=7*3+5*3+2*1+4*2=46(a)WPL=7*1+5*2+2*3+4*3=35(c)中树的WPL最小，它为哈夫曼树数据结构详解全文共163页，当前为第118页。5.4哈夫曼树哈夫曼树的构造给定N个权值分别为w1，w2,…，wn的结点，通过哈夫曼算法构造出最优二叉树1.将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F2.构造一个新结点，并从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和3.从F中删除刚才选出的两棵树，同时将新的到的树加入F中4.重复步骤2和3，直至F中只剩下一棵树为止数据结构详解全文共163页，当前为第119页。5.4哈夫曼树哈夫曼树的构造过程数据结构详解全文共163页，当前为第120页。5.4哈夫曼树哈夫曼树的特点1.每个初始结点最终都称为叶结点，并且权值越小的结点到根结点的路径长度越大2.构造过程中共新建了N-1个结点（双分支结点），因此哈夫曼树中结点总数为2N-13.每次构造都选择2棵树作为新结点的孩子，因此哈夫曼树中不存在度为1的结点

数据结构详解全文共163页，当前为第121页。图6.1图的基本概念6.2图的存储及基本操作(邻接矩阵法；邻接表法；邻接多重表法；十字链表法)6.3图的遍历(深度优先搜索；广度优先搜索)6.4图的基本应用(最小生成树；最短路径)数据结构详解全文共163页，当前为第122页。6.1图的基本概念图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系(边)集合。若V={v1,v2,……,vn},用|V|表示图G中顶点的个数，也称为图G的阶，E={(u,v)|u∈V,v∈V},用|E|表示图G中边的条数注意：线性表可以是空表，树可以是空树，但图不可以是空图图中不能一个顶点也没有，但边集E可以为空数据结构详解全文共163页，当前为第123页。6.1图的基本概念有向图：若E是有向边(也称为弧)的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v,w>，其中v,w是顶点，v称为弧尾，w称为弧头，称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。123

G=(V,E)V={1,2,3}E={<1,2>,<2,1>,<2,3>}数据结构详解全文共163页，当前为第124页。6.1图的基本概念无向图：若E是无向边(简称边)的有限集合时，则图G为无向图。边：是顶点的无序对，记为(v,w)或(w,v)。因为(v,w)=(w,v),其中v,w是顶点，可以说顶点w和顶点v互为邻接点。边(v,w)依附于顶点w和v，或者说边(v,w)和顶点v,w相关联。1234

G=(V,E)V={1,2,3,4}E={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}数据结构详解全文共163页，当前为第125页。6.1图的基本概念简单图：一个图G如果满足：1.不存在重复边；2.不存在顶点到自身的边，则称图G为简单图。(数据结构中仅讨论简单图)DBCA数据结构详解全文共163页，当前为第126页。6.1图的基本概念多重图：若图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则G为多重图。(多重图的定义和简单图是相对的)DBCA数据结构详解全文共163页，当前为第127页。6.1图的基本概念无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n(n-1)/2条边。有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n(n-1)条有向边DBCADBCA无向完全图有向完全图数据结构详解全文共163页，当前为第128页。6.1图的基本概念子图：设有两个图G1=(V1,E1)和G2=(V2,E2)，若V2是V1的子集，则称G2是G的子图。注意：

并非V和E的任何子集都能构成G的子图，因为这样的子集可能不是图，也就是说，E的子集中的某些边关联的顶点可能不在这个V的子集中DBCADBCDBCADCA数据结构详解全文共163页，当前为第129页。6.1图的基本概念连通：在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。连通图：若图G中任意两个顶点都是连通的，则称图G为连通图。否则称为非连通图。ABCDEFABCD非连通图连通图数据结构详解全文共163页，当前为第130页。6.1图的基本概念连通分量：无向图中的极大连通子图称为连通分量。如果一个图有n个顶点，并且有小于n-1条边，则此图必为非连通图注意： 1.要是子图 2.子图要是连通的 3.连通子图含有极大顶点数 4.具有极大顶点数的连通子图包含依附于

这些顶点的所有边数据结构详解全文共163页，当前为第131页。6.1图的基本概念图1是一个无向非连通图，但是它有两个连通分量，即图2和图3。图4尽管是图1的子图，但是它却不满足连通子图的极大顶点数，因此它不是图1的无向图的连通分量ABCDEF图1ABCD图2EF图3ABD图4数据结构详解全文共163页，当前为第132页。6.1图的基本概念强连通：在有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的强连通图：若图中任何一对顶点都是强连通的，则此图称为强连通图。DBCA123判断是否是强连通图数据结构详解全文共163页，当前为第133页。6.1图的基本概念强连通分量：有向图中极大强连通子图称为有向图的强连通分量DBCADBA图1图2图2是图1的强连通分量数据结构详解全文共163页，当前为第134页。6.1图的基本概念生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n，则它的生成树含有n-1条边。对于生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林数据结构详解全文共163页，当前为第135页。6.1图的基本概念顶点的度：以该顶点为一个端点的边的数目对于无向图，顶点v的度是指依附于该顶点的边的条数，记为TD(v)对于有向图，顶点v的度分为入度和出度，入度是以顶点v为终点的有向边的数目，记为ID(v)；而出度是以顶点v为起点的有向边的数目，记为OD(v)。顶点v的度等于其入度和出度之和，即TD(v)=ID(v)+OD(v)数据结构详解全文共163页，当前为第136页。6.1图的基本概念边上的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。网：边上带有权值的图称为带权图稀疏图：边数很少（相对的）的图称为稀疏图稠密图：边数很多（相对的）的图称为稠密图一般当图G满足|E|<|V|*log|V|时，可以将G看成是稀疏图数据结构详解全文共163页，当前为第137页。6.1图的基本概念路径长度:顶点Vp到顶点Vq之间有一条路径是指顶点序列Vp，Vi1，Vi2，……，Vim，Vq。路径上边的数目称为路径长度。回路或环:第一个顶点和最后一个顶点相同的路径称为回路或环。如果一个图有n个顶点，并且有大于n-1条边，则此图一定有环。简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。