《数据结构(C语言描述)》教学课件电子教案全书整套课件幻灯片.ppt

21世纪高等院校规划教材数据结构（C语言描述）第一章第一章学习数据结构课程学习数据结构课程的意义学习重点学习重点n掌握学习本课程的意义n掌握本课程的主体框架和讨论范围n掌握如何对算法进行描述和分析引入：引入：一般情况下，用计算机解决一个实际问题时，都是先对具体问题抽象，建立问题的求解模型，然后设计相应的算法，编写程序并上机调试，最后解决问题。n1.1实例：高校选修课程管理实例：高校选修课程管理n1.2数据结构的主要内容数据结构的主要内容n1.3算法和算法分析算法和算法分析n本章总结本章总结1.1实例：高校选修课程管理实例：高校选修课程管理n1.1.1问题描述问题描述n1.1.2问题的分析问题的分析n1.1.3学习本课程的意义学习本课程的意义1.1.1问题描述问题描述 表1-1是一所学校学生选修课程的选修情况登记表。要求用计算机来完成对学生选修课程的全程管理。通常必备的功能有登记登记，修改修改、查查询询和打印打印等。在本例中重点完成查询功重点完成查询功能能。学号学号姓名姓名系别系别选修课程名选修课程名学学分分成绩成绩课程名课程名课程代码课程代码等级等级分数分数0351103王杰王杰计算机计算机摄影技术摄影技术50130351212李丽李丽计算机计算机电脑音乐电脑音乐50210351220商立商立计算机计算机摄影技术摄影技术50130432233赵燕赵燕机械机械三维动画三维动画30320432118张欣张欣机械机械三维动画三维动画30320322140王芳王芳材料材料证券投资证券投资2053表表1-1某某学校学生选修课程情况登记表学校学生选修课程情况登记表1.1.2问题的分析问题的分析利用计算机解决实际问题的步骤：利用计算机解决实际问题的步骤：n第一步：从具体问题抽象出一个适当的数据模型。n第二步：进行算法设计。n第三步：实现抽象数据类型定义，即从编程语言的角度确定抽象数据类型的存储形式和确定抽象数据类型中每一种操作的具体实现算法。n第四步：编制相应的程序代码并进行调试。第一步：抽象数据模型一般包括三三部部分分：处理的数据对象、对象间的关系和需要实现的操作。常用以下格式描述：常用以下格式描述：ADT选修课程数据对象：数据对象：D=ai|ai记录类型，i=1,2,n,n0数据关系：数据关系：R=Ri|Ri记录间关系，i=1,2,m,m0基本操作：基本操作：DengjiList(&L)完成功能：对学生选修情况进行登记EditList(&L)完成功能：对选修情况登记表进行修改LocateList(&L,查询条件)完成功能：根据给定的查询条件，从登记表中查找满足条件的记录PrintList(L)完成功能：打印学生选修情况登记表ADT选修课程第二步：根据上面给定的抽象数据类型定义，写出实现各种操作的算法描述算法描述。下面以查询操作为例给出伪代码表示：intLocateList(选修课程&L,查询条件)对给定的查询条件进行分析，确定是对表中哪个数据项进行查询；对表中元素按给定的查询条件进行查询；若查询成功，返回记录的位置；否则返回0值，表示表中不存在满足给定条件的记录；第三步：确定表中的记记录录的的类类型型（结构体），表在内存中存储方式存储方式（按输入顺序存放）。具体定义如下：struct kechengsrtuct/选修课程名类型定义选修课程名类型定义char *kechengming;/课程名int kechengdaima;/课程代码;struct chengjistruct /成绩类型定义成绩类型定义char *dengji;/成绩等级int fenshu;/分数;struct student /表中学生记录类型定义表中学生记录类型定义long int num;/学号char*name;/姓名char*xibie;/系别kechengstruct kechent;int xuefen;/学分chengjistruct chengji;表在内存中的存储类型定义：表在内存中的存储类型定义：struct sqlist student *A;/将记录顺序存放在一个一维数组中将记录顺序存放在一个一维数组中int len;/表中记录的个数表中记录的个数;结论：结论：数据结构的实质就是一门研究非数值计算问题的程序设计中计算机的操作对象操作对象以及它们之间的关系关系和运算运算操作操作的一门学科。1.1.3学习本课程的意义学习本课程的意义n数据结构作为一门独立的课程在国外是从1968年开始设立的。n瑞士著名计算机科学家N.Wirth提出的著名公式“程序程序=算法算法+数据结构数据结构”。n数据结构是一门介于数学、计算机硬件和软件三者之间的核心课程。n用一句话概括用一句话概括：本课程就是从实际问题抽象出数据类型的手段。主要研究计算机所处理的数据对象、对象间存在的关系及进行的各种操作。1.2数据结构的主要内容数据结构的主要内容n1.2.1基本概念和术语n1.2.2数据结构定义n1.2.3逻辑结构的表示方法1.2.1基本概念和术语基本概念和术语n数据数据是对客观事物的符号表示，是一种信息的载体，是所有能输入到计算机中并被识别、存储和加以处理的信息的总称。n数据元素数据元素是数据的基本单位。一个数据元素也可以由若干个数据项数据项组成。n数据对象数据对象是性质相同的数据元素的集合，是数据的一个子集。n数据类型数据类型是对计算机中表示的数据对象、对象特征及该数据对象上的一组操作的描述。n抽象数据类型抽象数据类型是指一个数学模型及定义在该数学模型上的一组操作。定义取决于它的逻辑特性，与其在计算机内部如何表示（存储）和实现无关。1.2.2数据结构定义数据结构定义n数据结构数据结构是指相互间存在一种或多种特定关系的数据元素的集合。数据数据具有相同属性的数据元素的集合；结构结构数据元素间存在的一种或多种关系。n对一个给定的数据结构进行分析时，一般从它的逻辑结构、存储结构及对数据元素所进行的操作三个方面进行讨论。（本课程的主要讨论（本课程的主要讨论点）点）逻逻辑辑结结构构是对给定数据结构的一种描述方式，是从实际问题抽象出来的数据模型。主要描述数据元素，及元素之间存在的逻辑关系。通常按按元元素素间间存存在在的的逻逻辑辑关关系系的的不不同同特征特征，将数据结构分为四类分为四类：集合结构集合结构 线性结构线性结构 树型结构树型结构图型结构图型结构集合结构：集合结构：数据元素之间除了同属于一个集合之外，没有其他关系的数据结构。例子：从大街上随意的找五个人组成一个小组，编号分别为1、2、3、4、5，则这五个人之间除了属于同一组以外，相互间不存在任何的关系。组成集合的数据组成集合的数据元素之间不存在任元素之间不存在任何的关系何的关系线性结构：线性结构：数据元素之间存在“一对一”线性关系的数据结构。学号学号姓名姓名系别系别学分学分0351103王杰王杰计算机计算机30351212李丽李丽计算机计算机1例：例：学生基本情况登记表中每条学生记录都按一定的顺序排列，除了第一条和最后一条以外，每条记录都只有唯一的前驱和后继元素。元素之间是元素之间是1 1：1 1关系，关系，都只有唯一的前驱和都只有唯一的前驱和唯一的后继唯一的后继树型结构：树型结构：数据元素之间存在“一对多一对多”逻辑关系的数据结构。例：例：一个大学的人事档案管理。每个系有多个专业，但一个专业只能属于一个系；一个专业有多名学生，但一个学生只能属于一个专业元素之间的关系是元素之间的关系是1 1：n n，每个元素都只每个元素都只有唯一的前驱元素，有唯一的前驱元素，但可以有多个后继元但可以有多个后继元素素图型结构：图型结构：数据元素之间存在“多对多多对多”逻辑关系的数据结构。例：例：五个城市间的交通图。从1可以直达5，也可以经过2、3到达5，或也可以经过2、4到5。元素之间的关元素之间的关系是系是m:nm:n，每个每个元素都可以有元素都可以有多个前驱元素多个前驱元素和多个后继元和多个后继元素素存存储储结结构构又又称称物物理理结结构构，就是数据结构在计算机中的存储方式。它包括数据元素在计算机中的存储方式，还包括元素之间关系在内存中的表示。根据存存储储空空间间的的不不同同分分配配方方式式将数据结构分为两类：顺序存储顺序存储链式存储链式存储第一方面第二方面 顺序存储：顺序存储：所有元素存放在一片连续的连续的存储空间中，逻辑上相邻的元素在内存中的物理逻辑上相邻的元素在内存中的物理位置也是相邻的位置也是相邻的。注意：注意：元素存放在连续的存储空间中，元素之间的逻辑关系由在内存中的物理位置来体现。例：对一个由例：对一个由（1 1，2 2，3 3，4 4，5 5）五个元素组）五个元素组成的数据结构采成的数据结构采用顺序存储，则用顺序存储，则内存中的存储示内存中的存储示意图如下所示：意图如下所示：元素1元素2元素3元素4元素5起始地址 链式存储：链式存储：所有元素存放在可以不连续可以不连续的存储单元中，以结点的形式结点的形式存在，每个结点除了保存数据元素信息外，还通过指针来保存元通过指针来保存元素之间的关系素之间的关系。注意：注意：既元素存储在不连续的存储单元中，元素间的关系通过结点中的指针信息来体现。元素1元素4元素3元素2例：对一个由（例：对一个由（1 1，2 2，3 3，4 4）四个元素组）四个元素组成的数据结构采用链成的数据结构采用链式存储，则内存中的式存储，则内存中的存储示意图如下所示：存储示意图如下所示：1.2.3逻辑结构的表示方法逻辑结构的表示方法n二元组表示法二元组表示法表示形式为：D=（K，R）其中，K=a1,a2,an，为数据元素的集合R=r1,r2,rm，为元素之间关系的集合r1=|其中，其中，x,yK K 序偶表示：元素x和元素y之间存在关系，并且称元元素素x为为元元素素y的的前前驱驱，元元素素y为为元元素素x的的后后继继。如果元素x既是元素y的前驱，也是元素y的后继，既且，则用（x,y）形式表示。n图形表示法图形表示法用圆圆圈圈来代表数据元素，用带带箭箭头头的的连连线线来表示元素之间的关系，如图所示。二元组表示法：二元组表示法：D1=(K,R)D1=(K,R)其中，其中，K=a,b,c,d,e K=a,b,c,d,e R=r R=r r=,r=,1.3算法和算法分析算法和算法分析n1.3.1算法定义n1.3.2算法分析1.3.1算法定义算法定义n算法算法是对特定问题求解步骤的一种描述，是一组指令的有限序列，其中每一条指令都代表解题过程中的一个或者多个操作。n算法特点算法特点：有穷性、确定性、可行性、输入、输出n算法描述算法描述可以有多种方式，如：用流程图描述、用自然语言描述、还可用数学语言或特定的符号进行描述。本书中所有算法都是用用C语言语言来进行描述。1.3.2算法分析算法分析算法的设计要求算法的设计要求如下：正确性正确性可读性可读性健壮性健壮性 效率与低存储量的需求效率与低存储量的需求 其中，效率指的是算法执行的时间。存储量需求指的是算法执行过程中所需要的最大存储空间，通常主要考虑算法所需的辅助存储空间。这四个设计要求中最主要的是算法的执执行时间行时间和执行时所占的存储空间所占的存储空间大小。算法的执行时间算法的执行时间是指一个算法在计算机上运行时所花费的时间。=简单操作所需要的时间简单操作的次数影响算法执行时间的两个因素：影响算法执行时间的两个因素：（1）每个简单操作执行时所需时间与机器有关，而与算法无关。讨论算法中包含的算法中包含的简单操作的执行次数简单操作的执行次数。（2）另外一个与算法的执行时间相关的是问题的规模问题的规模。通常算法的执行时间用时间复杂度时间复杂度表示：T(n)=O(f(n)T(n)=O(f(n)其中，n n为问题的规模为问题的规模T T（n n）为时间复杂度为时间复杂度 此式子表示，随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。所以只要求出简单操作的次数关于要求出简单操作的次数关于n n的增长的增长率即可，然后用率即可，然后用n n的最高数量级来表示算法的最高数量级来表示算法的时间复杂度的时间复杂度。例：例：for(j=1;j=n;j+)for(k=1;k=m;k+)+x;s+=x;分析：分析：各个简单操作的执行次数如下所示：for(j=1;j=n;j+)/次次数数为为1+（n+1）+nfor(k=1;k=n;k+)/执执行行次次数数为为（1+（n+1）+n）n+x;/执行次数为执行次数为n*n s+=x;/执行次数为执行次数为n*n简单操作的执行次数之和为：4n2+4n+2，用用n n的最高数量级表示的最高数量级表示，时间复杂度为：O O（n n2）。衡量一个算法性能的另一个标准就是算算法法执执行行时时所所占占的的存存储储空空间间的的大大小小。一般一个算法所占的存储空间包括存储算法所占用的存储空间、算法的输入/输出数据所占用的存储空间和程序运行过程中临时占用的存储空间这三个方面。其中，只有算法执行过程中所占的临时空间与算法有着密切关系。通常一个算法在执行过程中所占用的临时存储空间的大小由空间复杂度来衡量，空间复杂度来衡量，记作：S（n n）=O=O（f f（n n）其中，n n为为问问题题的的规规模模；S S（n n）为为空空间间复复杂杂度度。通常用n的最高数量级来表示。本章总结：本章总结：n本章介绍了学习数据结构课程的意义、本课程的主题框架及相关内容和如何对算法进行评价。n数据结构主要研究计算机所处理的数据对象、研究计算机所处理的数据对象、对象之间存在的各种关系及进行的各种操作对象之间存在的各种关系及进行的各种操作，是用计算机来解决实际问题与编写相应程序两者之间的纽带。n数据结构从定义上可以理解为数据+结构。其中，数据指的是所要处理的若干个数据元素的数据指的是所要处理的若干个数据元素的集合集合；结构指的是数据元素之间的关系结构指的是数据元素之间的关系。按逻辑结构可分为集合结构、线性结构、树型结构和图型结构四种。按存储结构可分为顺序存储和链式存储两种。算法算法是解决问题步骤的一种描述，它有有有穷性、确定性、可行性、输入和输出穷性、确定性、可行性、输入和输出等五个特点。一个好的算法应该满足正确性、可读性、正确性、可读性、健壮性和效率与低存储量需求健壮性和效率与低存储量需求等四个要求，其中算法的执行效率和低存储量需求是衡量一个算法的最主要的标准。通常用时间复杂度来衡用时间复杂度来衡量算法的执行时间，用空间复杂度来衡量算法量算法的执行时间，用空间复杂度来衡量算法执行过程中所占用的临时存储空间的大小执行过程中所占用的临时存储空间的大小。它们都是问题的规模问题的规模n n的一个函数的一个函数，所以用n的最高数量级来表示。第第5章章 数组数组n数组的基本概念和存储结构数组的基本概念和存储结构n稀稀疏疏矩矩阵阵的的定定义义、表表示示方方法法、存存储储结结构构及及基本操作的实现算法基本操作的实现算法n特殊矩阵的存储特殊矩阵的存储n广广义义表表的的定定义义、链链式式存存储储结结构构，以以及及相相应应操作的实现算法。操作的实现算法。第第5章章 数组数组n5.1数组数组n5.2数学中的应用数学中的应用n5.3广义表广义表n本章总结本章总结5.1 数组数组n5.1.1一维数组一维数组n5.1.2多维数组多维数组5.1.1 一维数组一维数组n一一维维数数组组在数组结构中可以看成是一一个个线线性性表表或一个向量向量，通常分配一块连续的存储单元连续的存储单元。n在C语语言言中，一维数组an的存储单元是从a0至an1的一块连续的存储空间，设a0的的存存储储地地址址LOC（a0），数据元素所所占占的的存存储储单单元元为为k个个字字节节，则任一元素ai的首字节地址LOC（ai）：LOC（ai）=LOC（a0）+i*k(0in)5.1.2 多维数组多维数组多维数组的定义：多维数组的定义：1行向量形式行向量形式Amn=A，则A=（a0，a1，ai，am 1）一维数组一维数组其中，aj=（aj,0，aj,1，aj,n-1）（0jm）是一个行行向向量量形形式式的的线线性性表表。就是以以行行序序为为主主序序的存储方式。2 2 列向量形式列向量形式A Amnmn=A=A，则则A A=（a a0 0，a a1 1，a ai i，a an n1 1），其其中中，a ap p=（a a0,0,p p，a a1,1,p p，a am-1,m-1,p p）(0p(0pn)n)是是一一个个列列向向量量形形式式的的线线性性 表表，如如式式 子子（5-5-3 3）所所示示。是是以以列列序序为主序的存储结构。为主序的存储结构。数组的存储结构数组的存储结构 对对于于二二维维数数组组来来说说，设设数数组组的的第第一一个个元元素素a a0,0,0 0的的地地址址LOCLOC（a a0,0,0 0），每每个个元元素素所所占占的的存存储储单单元元为为k k，则则二二维维数数组组中中任任一元素一元素a ai i，j j的存储地址：的存储地址：LOCLOC（a ai,ji,j）=LOC=LOC（a a0,00,0）+（i*ni*nj j）*k n*k n为为列数列数 n维数组维数组ad1d2dn的数据元素存储位置的计算公式：的数据元素存储位置的计算公式：5.2 数学中的应用数学中的应用n5.2.1稀疏矩阵稀疏矩阵n5.2.2特殊矩阵特殊矩阵5.2.1 稀疏矩阵稀疏矩阵 稀疏矩阵的概念稀疏矩阵的概念 稀疏矩阵的三元组线性表表示稀疏矩阵的三元组线性表表示 稀疏矩阵的顺序存储方式稀疏矩阵的顺序存储方式 稀疏矩阵的链式存储方式稀疏矩阵的链式存储方式 稀疏矩阵各种操作的实现稀疏矩阵各种操作的实现 稀疏矩阵的概念：稀疏矩阵的概念：在一个阶数较大的矩阵在一个阶数较大的矩阵中非零元素个数中非零元素个数s s相对于矩相对于矩阵元素的总个数阵元素的总个数t t非常小非常小，即，即 s ts sublist)+1其它情况其它情况 实现算法：实现算法：（略）时时间间复复杂杂度度为为O O（n n），其其中中n n为为广广义义表表中中所所有有结结点点的的个个数数。该算法的空间复杂度为该算法的空间复杂度为O O（m m），），m m为广义表的深度为广义表的深度。建立广义表建立广义表 分分析析：建建立立广广义义表表过过程程可可以以通通过过递递归归实实现现。将将广广义义表表分分解解成成表表头头和和表表尾尾，而而表表头头和和表表尾尾若若仍仍是是广广义义表表，则则继继续续分分解解为表头和表尾。为表头和表尾。创建过程就是建立表头和建立表尾创建过程就是建立表头和建立表尾。区分表头和表尾中的元素是单元素还是表元素的方法：区分表头和表尾中的元素是单元素还是表元素的方法：（1 1）如如果果 i i为为“（）”，表表示示这这是是一一个个空空的的表表元元素素，字字符串长度为符串长度为2 2；（2 2）如果）如果 i i长度为长度为1 1，表明它是一个单元素；，表明它是一个单元素；（3 3）如果长度）如果长度11，这是一个表元素。，这是一个表元素。前两种情况就可作为递归过程的结束条件。前两种情况就可作为递归过程的结束条件。实现算法：实现算法：（略）（略）时间复杂度和空间复杂度：时间复杂度和空间复杂度：0（n），），n广义表中字符个数广义表中字符个数输出广义表输出广义表分分析析：设GL为表头指针，则输出时，需要对子表进行递归调用。当GL结点为表表结结点点时时，应首先输出作为一个表的起起始始符符号号“（”。然后再输出以sublist为表头指针的表表；当GL结点为原原子子结结点点时时，则应输出该元元素素的的值值。当以sublist为表头指针的表输出结束后，应在其最后输出一个作为表表终终止止符符的的“）”。当GL结点输出结束后，若存在后继结点，则应首先输出一个逗逗号号作作为为分隔符分隔符，然后再递归输出由next指针所指向的后继表后继表。实现算法：实现算法：（略）时间复杂度时间复杂度和空间复杂度：空间复杂度：0（n），n广义表中结点个数。本章总结：本章总结：一一维维数数组组在内存中开辟一块连续的存储单元存储数据，适合于随机查找。多多维维数数组组可以看成是一维数组的推广，也是一个线性表，表中的每个数据元素本身也是一个线性表表中的每个数据元素本身也是一个线性表。稀稀疏疏矩矩阵阵是指非非零零元元素素个个数数相相对对于于矩矩阵阵元元素素的的总总个个数数十十分分小小的的矩矩阵阵。稀疏矩阵的存储方法有三三种种：第一种是三元组表示法，第二种是行逻辑链式存储，第三种是十字链式存储。稀疏矩阵的基本操作有五种，都采用了顺序存储方式。特特殊殊矩矩阵阵是指非非零零元元素素或或零零元元素素的的分分布布有有一一定定规规律律的的矩矩阵阵。为了节省存储空间可以对特殊矩阵进行压缩存储。广广义义表表的元素分为原原子子和和子子表表，是一种递递归归结结构构。表中所含元素的个数称为长长度度。表中括号嵌套的最大次数称为深深度度。常用的基本操作有求广义表的长度、深度、创建和输出广义表等，操操作的共同点是都通过递归实现作的共同点是都通过递归实现。第第6 6章章 树树学习重点：学习重点：n树树和和二二叉叉树树的的概概念念、性性质质和和相相互互间间的转换方法的转换方法n树和二叉树的遍历方法和实现算法树和二叉树的遍历方法和实现算法n哈哈夫夫曼曼树树、线线索索二二叉叉树树和和二二叉叉排排序序树的构造方法与应用树的构造方法与应用第第6章章 树树n6.1实例实例1：文件目录管理：文件目录管理n6.2树的逻辑结构树的逻辑结构n6.3树的遍历树的遍历n6.4实例实例2：通信中电文编码：通信中电文编码n6.5二叉树定义、存储结构二叉树定义、存储结构n6.6二叉树遍历二叉树遍历n6.7树与二叉树的转换树与二叉树的转换n6.8应用举例应用举例n本章总结本章总结6.1 实例实例1：文件目录管理：文件目录管理n6.1.1 6.1.1 问题描述问题描述 n6.1.2 6.1.2 问题的分析问题的分析 n6.1.3 6.1.3 实现算法实现算法6.1.1 问题描述问题描述 在操作系统中对文件进行访问时提供按名存取机制按名存取机制，只需给出文件名，就可以访问到相应的文件，而无需知道文件的存储位置。如何实现按名存取机制呢？如何实现按名存取机制呢？6.1.2 问题的分析问题的分析文件系统文件系统将这些说明部分的全部信息集中起来构成文件文件控制块（控制块（FCB），文件目录由文件控制块组成。再将所有的文件目录组合在一起构成一个目录文件，目录文件以树型目录结构存储。树型目录结构树型目录结构中文件目录的第一级系统目录系统目录为树的根结点，定义为根目录根目录，文件目录的第二级和以下各级目录均为树的分支结点分支结点（非终结点），均定义为子目录子目录，只有树的叶子结点叶子结点（终结点）才为文件文件。所以实现文实现文件的按名存取，就是从目录结构的根目录开始直到所件的按名存取，就是从目录结构的根目录开始直到所要找的文件为止要找的文件为止 。6.1.3 实现算法实现算法实现算法：（略）实现算法：（略）结论：结论：文件目录结构是一种文件目录结构是一种树型结构树型结构，目录树中的根目，目录树中的根目录是树的录是树的根结点根结点，根目录下各级子目录和文件是树的，根目录下各级子目录和文件是树的其余结点其余结点。对处在同一层的各个子目录和文件进行比。对处在同一层的各个子目录和文件进行比较可以发现各个子目录和文件都只有一个较可以发现各个子目录和文件都只有一个共同的上一共同的上一级目录级目录，而同一层的各个子目录可以有，而同一层的各个子目录可以有任意多个下级任意多个下级子目录和文件子目录和文件。文件目录结构中的各个目文件目录结构中的各个目录和文件都满足树型结构的特征。录和文件都满足树型结构的特征。6.2 6.2 树的逻辑结构树的逻辑结构n6.2.1 6.2.1 树的逻辑结构树的逻辑结构 n6.2.2 6.2.2 树的相关术语树的相关术语6.2.1 树的逻辑结构树的逻辑结构树树或者是一棵空空树树，或者是一棵非非空空树树。一棵非空树由n（n0）个结点结点来组成。它满足以下条件：l有且仅有一个根结点有且仅有一个根结点，它没有前驱结点 l其余结点构成m(m=0)棵互互不不相相交交的的树树，称为该树的子树子树。每棵子树又是一棵树（递归定义递归定义）。逻逻辑辑结结构构：一棵树由若若干干个个结结点点组成，元素以结点的形式存在；关关系系：树的各个结点间是一一对对多多的关系，即除根结点外，所有结点有有且且仅仅有有一一个个前前驱驱结结点点，所有结点或者没有后继结点，或者有任意多个后继结点或者没有后继结点，或者有任意多个后继结点。6.2.2 树的相关术语树的相关术语根根结结点点：唯一没有前驱的结点。所有非空树，都有唯一的一个根结点。结结点点的的度度：结点所拥有的子树的个数，或者结点所拥有的后继结点的个数。树树的的度度是指树中所有结点的度的最大值。终终端端结结点点（叶子结点）：度为0的结点，或者树中没有后继的结点。非非终终端端结结点点（分支结点）：度不为0的结点，或者指有后继的结点。父父结结点点、孩孩子子结结点点：对一个结点来讲，它的前驱结点是它的父结点（双亲结点）；它的后继结点是它的孩子结点（子结点）。兄兄弟弟结结点点是是指指父父结结点点相相同同的的结结点点，即即前前驱驱结结点点是是相相同同的结点。的结点。结点的深度是指该结点在树中所处的结点的深度是指该结点在树中所处的层数层数，根结点所，根结点所在的层为第一层。树的深度是指树中结点的在的层为第一层。树的深度是指树中结点的最大层次最大层次数数。有有序序树树是是指指构构成成树树的的各各子子树树，从从左左到到右右有有一一定定顺顺序序，不能互相交换的树。不能互相交换的树。无无序序树树是是指指构构成成树树的的各各子子树树是是无无顺顺序序的的，可可以以互互相相交交换的树。换的树。森林是指若干棵森林是指若干棵互不相交互不相交的树。的树。6.3 树的遍历树的遍历n6.3.1 6.3.1 先根遍历先根遍历 n6.3.2 6.3.2 后根遍历后根遍历 n6.3.3 6.3.3 按层遍历按层遍历 树的遍历指的是树的遍历指的是按照某一种顺序访问树按照某一种顺序访问树中的所有结点，并且每个结点只访问一次。中的所有结点，并且每个结点只访问一次。树的遍历顺序：树的遍历顺序：先根遍历先根遍历（先序遍历）、（先序遍历）、后根遍历后根遍历（后序遍历）和（后序遍历）和按层遍历按层遍历。6.3.1 先根遍历先根遍历先根遍历先根遍历指如果树非空果树非空，则按下列规则进行遍历：l先访问树的根结点。先访问树的根结点。l从从左左到到右右访访问问根根结结点点的的所所有有子子树。树。l对子树也按先根遍历顺序来访对子树也按先根遍历顺序来访问所有的结点。问所有的结点。6.3.2 后根遍历后根遍历后根遍历后根遍历指如果树非空果树非空，则按下列规则进行遍历：l先从左到右访问根结点的所有子树。先从左到右访问根结点的所有子树。l l后访问树的根结点。后访问树的根结点。l 对子树也按后根遍历顺序来访问所对子树也按后根遍历顺序来访问所有的结点。有的结点。6.3.3 按层遍历按层遍历按层遍历按层遍历指如果树非空果树非空，则按下列规则进行遍历：l从从第第一一层层开开始始，从从上上到到下下顺顺序序遍遍历历各各层层，同一层从左到右访问各个结点。同一层从左到右访问各个结点。l 树的根结点所在层定义为第一层，依次类树的根结点所在层定义为第一层，依次类推。推。6.4 实例实例2：通信中电文编码：通信中电文编码n6.4.1 6.4.1 问题的描述问题的描述 n6.4.2 6.4.2 问题的分析问题的分析 n6.4.3 6.4.3 实现算法实现算法6.4.1 问题的描述问题的描述n在电信科技日新月异的今天，人们早已淡忘了，曾经风靡一时的电报电报。电报的原文发送时，都按一定的规则翻译成编码，以编码的形式传送。收到的电文中，每个文字的下面都会有一个数字编码。n下面介绍的也是一种电报的编码方法编码方法：发送的电文发送的电文翻译成翻译成0和和1的数字序列的数字序列。6.4.2 问题的分析问题的分析n电报电报主要依靠将传送的文字转换成由二进制数组成将传送的文字转换成由二进制数组成的字符串进行传送的字符串进行传送。n第一种解决方法：将所有传送的文字都转换成等长转换成等长的二进制字符串来传送的二进制字符串来传送，接收者只需按等长进行译码。n第二种解决方法：对电文中出现的字符设计长度不设计长度不等等的字符编码，对电文中出现次数比较多的字符采出现次数比较多的字符采用尽可能短的字符编码用尽可能短的字符编码，则传送的信息的长度就可以减少了。前缀编码（哈夫曼编码）前缀编码（哈夫曼编码）：每个字符的编码都不是另一个字符的编码的前缀。构造字符哈夫曼编码的方法：构造字符哈夫曼编码的方法：将将每每个个字字符符按按在在代代码码中中出出现现的的次次数数为为出出现现频频率率，构成一个频率集合构成一个频率集合，然后画一棵满足以下条件的，然后画一棵满足以下条件的树树：l l从从频频率率集集合合中中，每每次次选选择择出出现现频频率率最最小小的的两两个个字字符符构构成成一一棵棵树树，所所构构成成树树的的父父结结点点的的值值等等于于这这两两个字符的频率之和个字符的频率之和。l l将将选选中中的的两两个个字字符符的的频频率率从从频频率率集集中中删删除除，并将它们的并将它们的父结点加到频率集合中父结点加到频率集合中。重复上述两个过程，直到频率集合中重复上述两个过程，直到频率集合中只剩一个元只剩一个元素为止素为止。编码规则：从树的根结点起，编码规则：从树的根结点起，左边的孩子结点的左边的孩子结点的编号为编号为0，右边的孩子结点的编号为，右边的孩子结点的编号为1，对所有的子树，对所有的子树也按这个规则编码。所画的树称之为哈夫曼树，频率也按这个规则编码。所画的树称之为哈夫曼树，频率称之为权值。称之为权值。6.4.3 实现算法实现算法实现算法：实现算法：（略）结论：结论：哈夫曼树的每个结点最多有两个孩子结哈夫曼树的每个结点最多有两个孩子结点，结点度的最大值为点，结点度的最大值为2，这种树称为二叉树，这种树称为二叉树，两个孩子结点分别称为左孩子结点和右孩子两个孩子结点分别称为左孩子结点和右孩子结点。结点。6.5 二叉树定义、存储结构二叉树定义、存储结构n6.5.1 6.5.1 二叉树的定义二叉树的定义n6.5.2 6.5.2 二叉树的性质二叉树的性质 n6.5.3 6.5.3 二叉树的存储结构二叉树的存储结构6.5.1 二叉树的定义二叉树的定义二叉树定义二叉树定义（递归定义）：或者是一棵空空二二叉叉树树，或者是一棵非非空空二二叉叉树树。一棵非空二叉树由n（n0）个个结结点点组成。它满足以下条件：l有且仅有一个根结点，它没有前驱结点有且仅有一个根结点，它没有前驱结点 l其其余余结结点点构构成成两两棵棵互互不不相相交交的的子子树树，称为该树的左子树和右子树左子树和右子树。每棵子树又是一棵二叉树每棵子树又是一棵二叉树。特点：特点：每个结点最多只能有两个孩子结点最多只能有两个孩子结点，也就是说二叉树中不存在度大于度大于2的结点的结点。Root(BT)求根结点。求根结点。ParentBT(BT,elem)求父结点。求父结点。LchildBT(BT,elem)和和RchildBT(BT,elem)求求左左、右孩子结点。右孩子结点。CreateBT(BT,R,n)创建一棵二叉树。创建一棵二叉树。DepthBT(BT)求层数。求层数。PreOrdetBT(BT)先根遍历。先根遍历。InOrdetBT(BT)中根遍历。中根遍历。PostOrdetBT(BT)后根遍历。后根遍历。LeverOrdetBT(BT)按层遍历。按层遍历。二叉树的基本操作：二叉树的基本操作：6.5.2 二叉树的性质二叉树的性质 性质性质1：如果计二叉树的根结点所在层为第一层，则第第k层的结点数最多为层的结点数最多为2k-1个个。性质性质2：层数为k的二叉树的最大结点数为最大结点数为2k-1个个。性性质质3：在一个二叉树中，度为0的结点的个数为n0，度为2的结点的个数为n2，则n0=n2+1。性质性质4：具有：具有n个结点的完全二叉树的层数为：个结点的完全二叉树的层数为：或或。满满二二叉叉树树是是指指层层数数为为k的的有有2k-1个个结结点点的的二二叉叉树树，既既每层都保持它的最大结点数每层都保持它的最大结点数，每层结点都是满的。，每层结点都是满的。完全二叉树是指如果一棵层数为完全二叉树是指如果一棵层数为k的的n个结点的二叉个结点的二叉树的树的所有结点都与层数为所有结点都与层数为k的满二叉树中编号为的满二叉树中编号为1 1 n n的的结点一一对应结点一一对应，则称此二叉树为完全二叉树。，则称此二叉树为完全二叉树。性性质质5 5：对对一一棵棵有有n n个个结结点点的的完完全全二二叉叉树树来来讲讲，编编号号为为i i的结点满足以下条件：的结点满足以下条件：（1 1）如如果果i=1i=1，则则结结点点i i是是根根结结点点，无无父父结结点点；如如果果i1i1，则父结点的编号是则父结点的编号是 。（2 2）如如果果2 2inin，则则结结点点i i没没有有左左孩孩子子结结点点的的叶叶子子结结点点；否则其左孩子结点的编号是否则其左孩子结点的编号是2 2i i。（3 3）如果如果2 2i+1ni+1n，则则结点结点 i i没有右孩子结点；否则没有右孩子结点；否则其右孩子结点的编号是其右孩子结点的编号是2 2i+1i+1 。6.5.3 二叉树的存储结构二叉树的存储结构存在两种存储方式：存在两种存储方式：顺序存储方式顺序存储方式 链式存储方式链式存储方式 用一组连续的存储空间来存放一棵用一组连续的存储空间来存放一棵二叉树的所有结点。结点存放时对二叉二叉树的所有结点。结点存放时对二叉树中的树中的所有结点都按满二叉树中结点编所有结点都按满二叉树中结点编号来顺序编号号来顺序编号，将，将编号当成存储结点的编号当成存储结点的数组元素的下标数组元素的下标来处理。来处理。顺序存储方式：顺序存储方式：指存储二叉树中的指存储二叉树中的全部结点信息及结点间的全部结点信息及结点间的关系关系。结点间的关系通常有两种：一种是。结点间的关系通常有两种：一种是左右孩左右孩子结点的关系子结点的关系，另一种是，另一种是父结点的关系父结点的关系。二叉链表存储方式：每个结点除了二叉链表存储方式：每个结点除了存储结点存储结点元素的信息元素的信息外，还存储该结点的外，还存储该结点的左、右孩子结点左、右孩子结点的信息的信息。（。（常用存储方式常用存储方式）三叉链表存储方式：在三叉链表存储方式：在二叉链表的基础上二叉链表的基础上，在结点中再在结点中再增加一个存放该结点的父结点信息的增加一个存放该结点的父结点信息的指针域指针域。链式存储方式：链式存储方式：typedef struct Btnode Elemtype data;/存储二叉树结点元素的信息存储二叉树结点元素的信息 Btnode *lchild;/存储该结点的左孩子结点的信息存储该结点的左孩子结点的信息 Btnode *rchild;/存储该结点的右孩子结点的信息存储该结点的右孩子结点的信息 BtTree;二叉链表存储的结点类型定义：二叉链表存储的结点类型定义：6.6 二叉树遍历二叉树遍历n6.6.1 6.6.1 先根遍历先根遍历 n6.6.2 6.6.2 中根遍历中根遍历 n6.6.3 6.6.3 后根遍历后根遍历 n6.6.4 6.6.4 按层遍历按层遍历 n6.6.5 6.6.5 二叉树遍历的应用二叉树遍历的应用 一一棵棵二二叉叉树树是是由由根根结结点点、左左子子树树和和右右子子树树组组成成，争争别别用用D D、L L和和R R表表示示，并并要要求求左左子子树树在在右右子子树树前前遍遍历历，则则可可得得到到DLRDLR（先先根根遍遍历历）、LDRLDR（中中根根遍遍历历）和和LRDLRD（后后根根遍遍历历）三三种种。除除了了这这三三种种外外，还还可可按按结结点点所在层数进行遍历，称所在层数进行遍历，称按层遍历按层遍历。6.6.1 先根遍历先根遍历先根遍历（先根遍历（先序遍历）