数据结构 复习与习题解析(1).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,数据结构,与,算法,复习与习题解析,(,第,1-5,讲）,第一讲 绪论,了解数据结构有关概念的含义，特别是数据的逻辑结构和存储结构之间的关系；（,重点,）,熟悉类,C,语言的书写规范；,了解计算算法时间复杂度的方法。（,难点,）,29/10/2025,2,数据结构的定义,按某种逻辑关系,组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并,按一定的存储表示方式,把它们存储在计算机的存储器中，并,在其上定义了一个运算的集合,。,基本概念和术语,【,数据,】,是对信息的一种符号表示。是,可以输入,计算机中，,能被计算机,识别处理和输出的,一切,符号集合。,【,数据元素,】,是数据的,基本单位,，在计算机中通常作为一个,整体进行考虑和处理。也称为,记录,。,【,数据项,】,一个数据元素可由若干个数据项组成。是数据不,可分割的,最小单位,。,【,数据对象,】,是,性质相同,的数据元素的集合。是数据的一个,子集,。,29/10/2025,4,【,数据结构,】,相互之间存在一种或多种,特定关系,的数据,元素的集合,计算机如何解决问题,29/10/2025,5,问题,机外表示,处理要求,逻辑结构,基本运算,数学模型,存储结构,编程实现,实现,建模,求精,研究数据结构是为了帮计算机解决问题！,数据结构的研究内容,29/10/2025,6,【,数据结构的三个方面研究内容,】,具体来说，数据结构包含三个方面的内容，即,数据的逻辑结构,，,数据的存储结构,和,对数据所施加的运算,（操作）。,数据的逻辑结构,（面向人类）,数据的存储结构,（面向计算机）,数据的运算（操作）：检索、排序、插入、删除、修改等,线性结构,非线性结构,顺序存储,链式存储,线性表,栈,队列,树形结构,图形结构,散列存储,索引存储,串及数组,四种基本逻辑结构,29/10/2025,7,【,集合,】,数据元素间除了,“,同属于一个集合,”,外，无其他关系。,【,线性结构,】,1,对,1,的关系比如线性表、栈、队列。,【,树形结构,】,1,对多的关系比如树。,【,图形结构,】,多对多的关系比如图。,算法与数据结构,算法与数据结构关系密切,选择的数据结构是否恰当直接影响算法的效率；而数据结构的优劣由算法的执行来体现。,“,算法,+,数据结构,=,程序,”,算法,!=,程序,算法是,供人阅读,的，程序是,让机器执行,的,算法用,计算机语言实现,时就是程序,程序不具有算法的,有穷性,算法的概念,算法是解决某个特定问题的求解,步骤,的描述。,算法在计算机中表现为指令的,有限,序列，每条指令表示一个或多个操作。,计算机对数据的操作可以分为,数值性,和,非数值性,两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。,程序,不等于,算法：计算机程序是算法的具体实现。,29/10/2025,9,（,1,）,有穷性,：一个算法必须在执行有穷步之后结束。,（,2,）,确定性,：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。,（,3,）,可行性,：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。,（,4,）,输入,：一个算法应该有零个或多个输入。,（,5,）,输出,：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。,算法的性质,算法设计的要求,正确性,（四个境界）,没有语法错误,对于合法的输入数据能够产生满足要求的输出,对于非法的输入数据能够得出满足规格说明的结果,对于任何测试数据都有满足要求的输出结果,可读性,：便于阅读、理解和交流,健壮性,：不合法数据也能合理处理,时间效率高和存储量低,29/10/2025,11,算法效率的度量方法,事后统计方法,通过设计好的测试程序和数据，利用计算机测量其运行时间。,缺陷：需要先编写程序；和计算机软硬件相关；和测试数据相关。,事前分析估算方法（我们的选择）,依据,统计方法,对算法进行,估算,。,m=f(n),，,m,是语句总的执行次数，,n,是输入的规模。,和问题输入规模相关,，独立于程序设计语言和计算机软硬件,29/10/2025,12,算法时间复杂度,29/10/2025,13,在进行算法分析时，语句的总执行次数,T(n),是关于问题规模,n,的函数，进而分析,T(n),随,n,的,变化情况,并确定,T(n),的,数量级,。,算法的时间复杂度，也就是算法的时间量度，用“,大,O,记法,”记作：,T(n)=O(f(n),。由此得到的,T(n),的数量级叫“,大,O,阶,”。它表示随问题规模,n,的增大，算法执行时间增长率和,f(n),的,增长率相同,，称作算法的,渐进时间复杂度,，简称时间复杂度。其中,f(n),是问题规模,n,的,某个函数,。,一般情况下，,T(n),增长,越慢,，算法,越优,。,大,O,阶的数学定义,当,n,时，有,f(n)/g(n)=,常数,0,，则称函数,f(n),与,g(n),同阶,或者说，,f(n),与,g(n),同一个数量级，记作,f(n)=O(g(n),称上式为算法的时间复杂度,或称该算法的时间复杂,度为,O(g(n),。,其中,n,为问题的规模,(,大小,),的量度。,若,lim(f(n)/g(n)=lim(2n,3,+3n,2,+2n+1)/n,3,),=2,n,n,则算法的时间复杂度为,O(n,3,),算法空间复杂度,29/10/2025,15,算法的空间复杂度通过计算算法,所需的存储空间,实现，算法空间复杂度的计算公式记作：,S(n)=O(f(n),，其中，,n,为问题的规模，,f(n),为语句关于,n,所占存储空间的函数。,我们主要讨论时间复杂度问题。,例题解析,【,例,1】,数据元素之间的关系在计算机中有几种表示方法？各有什么特点？,答：,四种表示方法,（,1,）,顺序存储方式。,数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。,（,2,）,链式存储方式。,每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。,（,3,）,索引存储方式。,除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。,（,4,）,散列存储方式。,通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。,29/10/2025,16,例题解析,【,例,2】,有下列运行时间函数：,（,1,）,T,1,(n)=1000;,（,2,）,T,2,(n)=n,2,+1000n;,（,3,）,T,3,(n)=3n,3,+100n,2,+n+1;,分别写出相应的大,O,表示的运算时间,答：,(1)O(1)(2)O(n,2,)(3)O(n,3,),29/10/2025,17,例题解析,【,例,3】,已知如下程序段,for(i=n;i0;i-),语句,1,x=x+1;,语句,2,for(j=n;j=i;j-),语句,3,y=y+1;,语句,4,语句,1,执行的频度为,_,；,语句,2,执行的频度为,_,；,语句,3,执行的频度为,_,；,语句,4,执行的频度为,_,。,答：,（,1,）,n+1,（,2,）,n,（,3,）,n(n+3)/2,（,4,）,n(n+1)/2,第二讲 线性表,线性结构的定义和特点,在数据元素的非空有限集中，有且仅有一个开始结点和一个终端结点，并且所有结点只有一个直接前趋和一个直接后继。简言之，线性结构反映结点间的逻辑关系是,一对一,。线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最简单、最常用的是线性表。,线性表的存储方法,顺序存储：逻辑上相邻物理上,一定,相邻,链式存储：逻辑上相邻物理上,不一定,相邻,顺序表,顺序表,线性表的顺序存储表示,顺序存储,用一,组地址连续的,存储单元,依次,存储线性表的元素，可通过,数组,来实现。（逻辑上相邻物理上一定相邻）,LOC,(,a,i,),=LOC,(,a,1,)+(,i,-1),len,（,a,1,为首元素，,len,为单个元素占用空间长度,）,顺序存储的优点,可以随机存取表中任一元素,O(1),；存储空间使用紧凑,顺序存储的缺点,在插入元素时平均需要移动,n/2,个元素，删除某一元素时，平均需要移动,n-1/2,个元素。,算法的平均时间复杂度为,O(n),预先分配空间需按最大空间分配，利用不充分,;,表容量难以扩充,29/10/2025,20,链表,链式存储结构特点,用一组任意的存储单元存储线性表的数据元素,利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素,每个数据元素,ai,，,除存储本身信息外，还需存储其直接后继的信息,链式存储结构的优点：,结点空间可以,动态申请和释放,；,数据元素的逻辑次序靠结点的指针来指示，,插入和删除时不需要移动数据元素,。,链式存储结构的缺点：,每个结点的,指针域需额外占用存储空间,。当数据域所占字节不多时，指针域所占存储空间的比重显得很大。,链表,是,非随机存取,结构,。对任一结点的操作都要从头指针依链查找该结点，这增加了算法的复杂度,O,（,n,）,不,便于,在表尾,插入,元素：需遍历整个表才能找到位置。,29/10/2025,21,例题解析,【,例,1】,说明在线性表的链式存储结构中，头指针与头结点之间的根本区别。,答：,在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。,头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。,29/10/2025,22,例题解析,【,例,2】,设顺序表,va,中的数据元素递增有序。试设计一个算法，将,x,插入到顺序表的适当位置上，以保持该表的有序性。,答：,void Insert_SqList(SqList va,int x)/*,把,x,插入递增有序表,va,中*,/,int i;,if(va.length MAXSIZE)return;,for(i=va.length-1;va.elemix i-),va.elemi+1=va.elemi;,va.elemi+1=x;,va.length+;,/*Insert_SqList*/,29/10/2025,23,#define MAXSIZE 100,typedef struct ,ElemType *elem;,int length;,SqList,；,例题解析,【,例,3】,设单链表结点指针域为,next,，试写出删除链表中指针,p,所指结点的直接后继的,C,语言语句。,答：,q=p-next;,p-next=q-next;,free(q);,29/10/2025,24,例题解析,【,例,4】,设单链表中某指针,p,所指结点（即,p,结点）的数据域为,data,，链指针域为,next,，请写出在,p,结点之前插入,s,结点的操作。,答：,设单链表的头结点的头指针为,head,且,pre=head,；,while(pre-next!=p),pre=pre-next;,s-next=p;,pre-next=s;,29/10/2025,25,例题解析,【,例,5】,试编写在带头结点的单链表中删除（一个）最小值结点的算法。,void delete,（,Linklist&L,）,答：,题目分析,本题要求在单链表中删除最小值结点。单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。,void delete,（,LinkedList&L,）,L,是带头结点的单链表,p=L-next,；,p,为工作指针。指向待处理的结点。假定链表非空。,pre=L,；,pre,指向最小值结点的前驱。,q=p,；,q,指向最小值结点，初始假定第一元素结点是最小值结点。,while,（,p-next!=null,）,if,（,p-next-datadata,）,pre=p,；,q=p-next,；,查最小值结点,p=p-next,；,指针后移。,pre-next=q-next,；,从链表上删除最小值结点,free,（,q,）；,释放最小值结点空间,结束算法,delete,。,29/10/2025,26,例题解析,【,例,6】,一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域,coef,，指数域,exp,和指针域,next,；现对链表求一阶导数，链表的头指针为,ha,，头结点的,exp,域为,1,。,void derivative(ha),q=ha;pa=ha-next;,while(1)_),if(2)_)(3)_);free(pa);pa=(4)_);,else pa-coef(5)_);pa-exp(6)_);q=(7)_);,pa=(8)_);,29/10/2025,27,(1),pa!=ha,或,pa-exp!=-1,(2),pa-exp=0,若指数为,0,，即本项为常数项,(3),q-next=pa-next,删常数项,(4),q-next,取下一元素,(5),=pa-coef*pa-exp,(6),-,指数项减,1,(7),pa,前驱后移,或,q-next,(8),pa-next,取下一元素,第三讲 栈和队列,栈,限定仅在表尾进行插入和删除的线性表，把这个表尾称为,栈顶,。,特点,后进先出,(LIFO,表,),栈的存储方法,栈的顺序存储,顺序栈,栈的链式存储,链栈,29/10/2025,28,关于栈要求掌握的内容,29/10/2025,29,栈的基本概念：,LIFO,栈的存储,栈的应用（了解）,顺序栈,（熟练掌握）,链栈,（熟练掌握）,初始化,取栈顶,入栈出栈,判断栈空,栈,初始化,取栈顶,入栈出栈,判断栈空,队列定义,29/10/2025,30,队列的定义,队列：,线性表,(queue),特点：先进先出,(FIFO,结构,),。,队尾,队头,下图是队列的示意图：,a,1,a,2,a,n,出队,入队,队头,队尾,当队列中没有元素时称为,空队列,。,表尾称为队尾,(rear),表头称为队头,(front),插入元素称为入队,删除元素称为出队,限定在表的一端插入、另一端删除,。,顺序队列的假溢出问题,29/10/2025,31,在顺序队列中，当尾指针已经指向了队列的最后一个,位置即数组上界时，若再有元素入队，就会发生“,溢出,”。,“,假溢出,”,队列的存储空间未满，却发生了溢出。,rear,front,J,1,J,2,J,3,J,4,rear,front,J,3,J,4,(1),、平移元素：把元素平移到队列的首部。,效率低,。,解决“假溢出”的问题有两种可行的方法：,(2),、将新元素插入到第一个位置上，构成,循环队列,，,入队和出队仍按“先进先出”的原则进行。,操作效率、空间利用率高,。,rear,front,J,3,J,4,front,rear,J,3,J,4,循环队列,29/10/2025,32,队空条件,:,front=rear,(,初始化时：,front=rear),队满条件,：,front=(rear+1)%N,(N=maxsize),队列长度：,L=,（,N,rear,front,）,%N,J2 J3,J1,J4,J5,front,rear,选用,空闲单元法：,即,front,和,rear,之一指向实元素，另一指向空闲元素。,问,2,：,在具有,n,个单元的循环队列中，队满时共有多少个元素？,n-1,个,5,问,1,：,左图中队列长度,L=,？,例题解析,【,例,1】,一个栈的输入序列是,12345,，若在入栈的过程中允许出栈，则栈的输出序列,43512,可能实现吗？,12345,的输出呢？,答：,43512,不可能实现，主要是其中的,12,顺序不能实现；,12345,的输出可以实现，只需压入一个立即弹出一个即可。,29/10/2025,33,例题解析,【,例,2】,如果一个栈的输入序列为,123456,，能否得到,435612,和,135426,的出栈序列？,答：,435612,中到了,12,顺序不能实现；,135426,可以实现。,29/10/2025,34,例题解析,【,例,3】,一个栈的输入序列为,123,，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？,答：,可以通过穷举所有可能性来求解：,1,入,1,出，,2,入,2,出，,3,入,3,出，即,123,；,1,入,1,出，,2,、,3,入,3,、,2,出，即,132,；,1,、,2,入，,2,出，,3,入,3,出，即,231,；,1,、,2,入，,2,、,1,出，,3,入,3,出，即,213,；,1,、,2,、,3,入，,3,、,2,、,1,出，即,321,；,合计有,5,种可能性。,29/10/2025,35,例题解析,【,例,4】,简述顺序存储队列的假溢出的避免方法及队列满和空的条件。,答：设顺序存储队列用一维数组,qm,表示，其中,m,为队列中元素个数，队列中元素在向量中的下标从,0,到,m-1,。设队头指针为,front,，队尾指针是,rear,，约定,front,指向队头元素的前一位置，,rear,指向队尾元素。当,front,等于,-1,时队空，,rear,等于,m-1,时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针,rear,等于,m-1,时，若,front,不等于,-1,，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用,0,至,rear-front-1,）；二是将队列看成首尾相连，即循环队列（,0.m-1,）。在循环队列下，仍定义,front=rear,时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即,rear+1=front,（准确记是（,rear+1,）,%m=front,，,m,是队列容量）时为队满。另一种解法是“设标记”方法，如设标记,tag,，,tag,等于,0,情况下，若删除时导致,front=rear,为队空；,tag=1,情况下，若因插入导致,front=rear,则为队满。,29/10/2025,36,第四讲 串和数组,【,例,1】,填空题：,1.,空格串是指,_,，其长度等于,_,。,【,答案,】,（,1,）由空格字符（,ASCII,值,32,）所组成的字符串 （,2,）空格个数,2,组成串的数据元素只能是,_,。,【,答案,】,字符,【,解析,】,串是一种特殊的线性表，其特殊性在于串中的元素只能是字符型数据。,3,两个字符串相等的充分必要条件是,_,。,【,答案,】,两串的长度相等且两串中对应位置上的字符也相等。,4,一个字符串中,_,称为该串的子串。,【,答案,】,任意个连续的字符组成的子序列,29/10/2025,37,例题解析,【,例,2】,设计一个算法，将字符串,s,的全部字符复制到字符串,t,中，不能利用,strcpy,函数。,答：,【,算法分析,】,要实现两个字符串的复制，实质为两个字符数组之间的复制，在复制时，一个字符一个字符的复制，直到遇到,0,，,0,一同复制过去，,0,之后的字符不复制。,【,算法源代码,】,void copy(char s,char t),int i;,for(i=0;si!=0;i+)ti=si;,ti=si;,29/10/2025,38,例题解析,【,例,3】,设有一个二维数组,A,m,n,，假设,A,00,存放位置在,644,，,A,22,存放位置在,676,，每个元素占一个空间，问,A,33,存放在什么位置？,答：设数组元素,Aij,存放在起始地址为,Loc,（,i,j,）的存储单元中。,Loc,（,2,2,）,=Loc,（,0,0,）,+2*n+2,=644+2*n+2=676.,n=,（,676-2-644,）,/2=15,Loc,（,3,3,）,=Loc,（,0,0,）,+3*15+3,=644+45+3=692.,29/10/2025,39,例题解析,【,例,4】,设有一个,n,n,的对称矩阵,A,，为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组,B,中，称之为对称矩阵,A,的压缩存储方式。试问：,（,1,）存放对称矩阵,A,上三角部分或下三角部分的一维数组,B,有多少元素？,（,2,）若在一维数组,B,中从,0,号位置开始存放，则对称矩阵中的任一元素,a,ij,在只存下三角部分的情形下应存于一维数组的什么下标位置？给出计算公式。,答：,（,1,）数组,B,共有,1,2+3+,+n=,（,n+1,）*,n/2,个元素。,（,2,）只存下三角部分时，若,i,j,，则数组元素,Aij,前面有,i-1,行（,1,i-1,，第,0,行第,0,列不算），第,1,行有,1,个元素，第,2,行有,2,个元素，,，第,i-1,行有,i-1,个元素。在第,i,行中，第,j,号元素排在第,j,个元素位置，因此，数组元素,Aij,在数组,B,中的存放位置为：,1+2+,+,（,i-1,）,+j=,（,i-1,）*,i/2+j,若,i j,，数组元素,Aij,在数组,B,中没有存放，可以找它的对称元素,Aji,。在数组,B,的第（,j-1,）*,j/2+i,位置中找到。如果第,0,行第,0,列也计入，数组,B,从,0,号位置开始存放，则数组元素,Aij,在数组,B,中的存放位置可以改为：当,i,j,时，,=i*,（,i+1,）,/2+j,；当,i n,，则无左孩子；,3),i,的右孩子是,2i+1,，如果,2i+1n,则无右孩子。,例题解析,1,深度为,H,的完全二叉树至少有,_,个结点；至多有,_,个结点；,H,和结点总数,N,之间的关系是,_,。,【,答案,】,（,1,）,2H-1,（,2,）,2H-1,（,3,）,H=,log,2,N,+1,2,一棵有,n,个结点的满二叉树有,_,个度为,1,的结点，有,_,个分支（非终端）结点和,_,个叶子，该满二叉树的深度为,_,。,【,答案,】,（,1,）,0,（,2,）,(n-1,）,/2,（,3,）,(n+1,）,/2,（,4,）,log,2,n,+1,3,对于一个具有,n,个结点的二叉树，当它为一棵,_,时，具有最小高度，当它为一棵,_,时，具有最大高度。,【,答案,】,（,1,）完全二叉树（,2,）单支树，树中任一结点（除最后一个结点是叶子外），只有左子女或只有右子女。,4,已知二叉树有,50,个叶子结点，则该二叉树的总结点数至少是,_,。,【,答案,】99,【,解析,】,在二叉树中，,N0=N2+1,，所以，有,50,个叶子结点的二叉树，有,49,个度为,2,的结点。若要使该二叉树的结点数最少，度为,1,的结点应为,0,个，即总结点数,N=N0+N1+N2=99,。,29/10/2025,43,二叉树的存储（一）,29/10/2025,44,二叉树存储方法有,顺序存储,和,链式存储,二叉树,顺序存储,结构,完全二叉树,：用一组地址连续的存储单元依次,自上而下、自左至右,存储结点元素，即将编号为,i,的结点元素存储在一维数组中下标为,i,的分量中（不用下标为,0,存储单元）。,此,顺序存储结构仅适用于完全二叉树,不是完全二叉树怎么办？,一律转为完全二叉树！方法很简单，将各层空缺处统统补上,“,虚结点,”,，其内容为空。,缺点：,浪费空间；插入、删除不便,二叉树的存储（二）,29/10/2025,45,二叉树链式存储结构,存储方式,一般从根结点开始存储，用二叉链表来表示。（相应地，访问树中结点时也只能从根开始）,二叉树结点的特点,二叉树是非线性结构，适合用链式存储结构,lchild data rchild,结点结构,data,rchild,lchild,data,parent,lchild,rchild,二叉树结点数据类型定义：,typedef s,truct,BiTN,ode,TElemType,data,;,struct,BiTN,ode,*l,child,*r,child;,BiTNode,*BiTree;,二叉树遍历,29/10/2025,46,若规定先左后右，则只有前三种情况：,DLR,前（根）序遍历，,LDR,中（根）序遍历，,LRD,后（根）序遍历,根据遍历顺序确定一棵二叉树,已知二叉树的,前序,序列和,中序,序列，,可以,唯一确定一棵二叉树。,已知二叉树的,后序,序列和,中序,序列，,可以,唯一确定一棵二叉树。,已知二叉树的,前序,序列和,后序,序列，,不能,唯一确定一棵二叉树。,例题解析,29/10/2025,47,设二叉树,bt,的一种存储结构如下：,0,0,2,3,7,5,8,0,10,1,j,h,f,d,b,a,c,e,g,i,0,0,0,9,4,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,lchild,data,rchild,其中,bt,为树根结点指针,lchild,、,rchild,分别为结点的左、右孩子指针域,在这里使用结点编号作为指针域值,0,表示指针域为空,;data,为结点的数据域。请完成下列各题：,(1),画出二叉树的树形表示；,(2),写出按先序、中序和后序遍历二叉树,bt,所得到的结点序列；,例题解析（续）,29/10/2025,48,0,0,2,3,7,5,8,0,10,1,j,h,f,d,b,a,c,e,g,i,0,0,0,9,4,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,lchild,data,rchild,(1),画出二叉树的树形表示；因为第,6,号结点不是任何结点的孩子结点，该结点必定是根结点，再根据和结点左、右指针域的值很容易得到该二叉树的树形表示为,a,b,g,f,d,c,e,h,i,j,例题解析（续）,29/10/2025,49,0,0,2,3,7,5,8,0,10,1,j,h,f,d,b,a,c,e,g,i,0,0,0,9,4,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,lchild,data,rchild,a,b,g,f,d,c,e,h,i,j,(2),写出按先序、中序和后序遍历二叉树,bt,所得到的结点序列；,a.,先序序列,a,b,c,e,d,f,h,g,i,j,例题解析（续）,29/10/2025,50,0,0,2,3,7,5,8,0,10,1,j,h,f,d,b,a,c,e,g,i,0,0,0,9,4,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,lchild,data,rchild,a,b,g,f,d,c,e,h,i,j,(2),写出按先序、中序和后序遍历二叉树,bt,所得到的结点序列；,a.,先序序列,a,b,c,e,d,f,h,g,i,j,b.,中序序列,e,c,b,h,f,d,j,i,g,a,例题解析（续）,29/10/2025,51,0,0,2,3,7,5,8,0,10,1,j,h,f,d,b,a,c,e,g,i,0,0,0,9,4,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,lchild,data,rchild,a,b,g,f,d,c,e,h,i,j,(2),写出按先序、中序和后序遍历二叉树,bt,所得到的结点序列；,a.,先序序列,a,b,c,e,d,f,h,g,i,j,b.,中序序列,e,c,b,h,f,d,j,i,g,a,b.,后序序列,e,c,h,f,j,i,g,d,b,a,树与森林,【,例题,】,从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。,答：,树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树惟一表示，并可使用二叉树的一些算法去解决树和森林中的问题。,树和二叉树的区别有,3,：一是二叉树的度至多为,2,，树无此限制；二是二叉树有左右子树之分，即使在只有一个分支的情况下，也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。,29/10/2025,52,例题解析,【,例题,】,已知一棵二叉树的中序序列和后序序列分别为,GLDHBEIACJFK,和,LGHDIEBJKFCA,（,1,）给出这棵二叉树；（,2,）转换为对应的森林。,答：,29/10/2025,53,A,C,B,H,J,D,F,G,K,L,E,I,E,A,B,L,D,G,H,I,J,F,C,K,例题解析,【,例题,】,假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为,ABECFGDHI,中序序列为,BCDAFEHIG,。请画出该二叉树，并将其转换为对应的森林。,答：按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列分成左右两部分：左子树和右子树。若左子树不空，层次序列中第二个结点为左子树的根；若右子树为空，则层次序列中第三个结点为右子树的根。对右子树也作类似的分析。层次序列的特点是，从左到右每个结点或是当前情况下子树的根或是叶子。,29/10/2025,54,I,A,D,E,B,F,C,G,H,E,C,A,B,D,I,G,H,F,二叉树的应用：,Huffman,树,29/10/2025,55,Huffman,树的应用,带权路径计算,WPL,带权路径长度,WPL,最小的二叉树称作,赫夫曼树,具有相同带权结点的哈夫曼树不惟一,满二叉树不一定是哈夫曼树,哈夫曼树的结点的度数为,0,或,2,，没有度为,1,的结点。,包含,n,个叶子结点的哈夫曼树中共有,2,n,1,个结点。,Huffman,树的构造过程,给定权值集,w=2,3,4,7,8,9,试构造关于,w,的的一颗哈夫曼树，并求其带权路径长度,WPL,。,29/10/2025,56,2,3,4,7,8,9,4,7,8,9,2,3,5,7,8,9,2,3,5,4,9,9,2,3,5,4,9,7,8,15,Huffman,树的构造过程,29/10/2025,57,给定权值集,w=2,3,4,7,8,9,试构造关于,w,的的一颗哈夫曼树，并求其带权路径长度,WPL,。,7,8,15,9,2,3,5,4,9,18,7,8,15,9,2,3,5,4,9,18,33,WPL=,(2+3),4,+,4,3,+,9,2,+,(7+8),2,=80,【,例题,】T=(a,2),(b,3),(c,4),(d,7),(e,9),为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度,WPL,、,T,中每个字符的哈曼夫编码和哈夫曼编码的平均长度。,2,3,4,7,9,Huffman,编码过程,T=(a,2),(b,3),(c,4),(d,7),(e,9),为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度,WPL,、,T,中每个字符的哈曼夫编码和哈夫曼编码的平均长度。,2,3,4,7,9,2,3,5,T=(a,2),(b,3),(c,4),(d,7),(e,9),为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度,WPL,、,T,中每个字符的哈曼夫编码和哈夫曼编码的平均长度。,2,3,4,7,9,2,3,5,T=(a,2),(b,3),(c,4),(d,7),(e,9),为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度,WPL,、,T,中每个字符的哈曼夫编码和哈夫曼编码的平均长度。,2,3,4,7,9,2,3,5,2,3,5,4,9,T=(a,2),(b,3),(c,4),(d,7),(e,9),为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度,WPL,、,T,中每个字符的哈曼夫编码和哈夫曼编码的平均长度。,2,3,4,7,9,2,3,5,2,3,5,4,9,T=(a,2),(b,3),(c,4),(d,7),(e,9),为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度,WPL,、,T,中每个字符的哈曼夫编码和哈夫曼编码的平均长度。,2,3,4,7,9,2,3,5,2,3,5,4,9,7,9,16,T=(a,2),(b,3),(c,4),(d,7),(e,9),为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度,WPL,、,T,中每个字符的哈曼夫编码和哈夫曼编码的平均长度。,2,3,4,7,9,2,3,5,2,3,5,4,9,7,9,16,T=(a,2),(b,3),(c,4),(d,7),(e,9),为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度,WPL,、,T,中每个字符的哈曼夫编码和哈夫曼编码的平均长度。,2,3,4,7,9,2,3,5,2,3,5,4,9,7,9,16,2,3,5,4,9,7,9,16,25,T=(a,2),(b,3),(c,4),(d,7),(e,9),为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度,WPL,、,T,中每个字符的哈曼夫编码和哈夫曼编码的平均长度。,2,3,4,7,9,2,3,5,2,3,5,4,9,7,9,16,2,3,5,4,9,7,9,16,25,T=(a,2),(b,3),(c,4),(d,7),(e,9),为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度,WPL,、,T,中每个字符的哈曼夫编码和哈夫曼编码的平均长度。,2,3,5,4,9,7,9,16,25,a,b,c,d,e,WPL=,55,0,0,0,0,1,1,1,1,a:,010,b:,011,c:,00,d:,10,e:,11,哈夫曼编码的平均长度,=,3,2,+,3,3,+,2,4,+,2,7,+,2,9,=55,1,、定义和性质,2,、存储结构,3,、遍历,4,、线索化：线索树,顺序结构,链式结构,前序线索树,中序线索树,后序线索树,树,二叉树,森林,前,序,遍,历,后,续,遍,历,遍历,存储结构,遍历,双亲表示,孩子表示,孩子兄弟,先根遍历,后根遍历,中序遍历,后序遍历,前序遍历,霍夫曼树,霍夫曼编码,关于树的小结,