《数据结构软》PPT课件

1,数据结构,（C语言版）,作者：黎剑兵,2,第一章绪论,学习内容常用术语算法评价时间复杂度与空间复杂度的分析重点了解逻辑结构物理结构和数据的运算三方面相关概念及相互关系难点时间复杂度的分析方法掌握用类C语言的表示方法会用类C编写程序,3,第一章绪论,计算机科技是一门研究用计算机进行信息表示和处理的科学。主要涉及两方面的问题：信息的表示和信息的处理信息的表示和组织直接关系到处理信息的程序的效率，随着计算机的应用领域的扩大。信息量的增加，信息范围的拓宽，使系统程序和应用程序的规模的日趋增大，结构也日趋增大。因此，为了编写出一个“好”的程序，必须分析处理的对象的特征及个对象之间的存在的关系。这就是本课程所要研究的问题。,4,第一章绪论,计算机程序是对信息进行加工处理。这些信息之间大多数情况下往往具有重要的结构关系。这就是数据结构的内容。那么，什么是数据结构呢？,5,1.地位,第一章绪论,6,1.地位,第一章绪论,数据结构DataStructure,7,数据模型,问题,实现,2.主要内容,第一章绪论,8,数据模型,问题,实现,2.主要内容,第一章绪论,(1)要对所加工的对象进行逻辑组织(2)如何把加工对象存储到计算机中去？(3)数据运算,9,3.学科定义,什么是数据结构,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的科。,10,基本概念和术语,数据元素(dataelement)数据基本单位，也称节或孩子，可由若干个数据项组成。数据项是数据最小单位数据(data)是对客观事物的表示，指所有能输入到计算机并被计算机程序处理的符号的总称。数据对象(dataobject)性质相同的数据元素的集合数据结构数据元素之间的相互关系,11,1)集合,基本概念和术语,数据间的四种典型结构：,2）线形,3）树形,4）图或网络：,12,基本概念和术语,四种典型结构：,1)集合,13,四种典型结构,基本概念和术语,2）线形：,14,四种典型结构：,基本概念和术语,3）树形：,15,四种典型结构：,基本概念和术语,4）图或网络：,16,基本概念和术语,（5）逻辑结构：从具体问题抽象出的数学模型。体现逻辑关系。,（6）物理结构(存储结构)：DE及关于在计算机中的表示。DE存储称为节点关系存储：a.顺序存储b.链式存储,17,基本概念和术语,（7）DS广义定义：DE的逻辑结构DE的物理结构DE的抽象运算（8）基本操作加工型：查找删除更新排序引用型：查找,18,基本概念和术语,19,算法和算法分析,一、算法定义,算法是对特定问题求解步骤的一种描述，是指令的有限序列。特性：有穷性确定性可行性输入输出,20,算法和算法分析,二、算法的描述与分析描述：类C语言要求正确性：a.语法b.n个输入c.一组典型的苛刻的输入d.所有输入可读性健壮性效率与存贮量,21,算法和算法分析,分析标准a、时间复杂度：算法中基本操作重复执行的次数(频度)。T(o)=O(f(n)时间复杂度分为平均时间复杂度和最坏时间复杂度复杂度的值取规模函数最高阶,22,分析标准a、时间复杂度：算法中基本操作重复执行的次数。T(o)=O(f(n)时间复杂度分为平均时间复杂度和最坏时间复杂度复杂度的值取规模函数最高阶,算法和算法分析,b、空间复杂度：算法所需存贮空间S(n)=O(f(n),23,算法和算法分析,例：分析下列语句段的时间复杂度m=0;1for(k=0;kn;k+)n+1for(j=0;jk;j+)n(n+1)/2m+=2;O(n2),24,习题与练习一,1.简要回答下列问题：a.数据与数据元素有何区别？b.逻辑结构与存储结构是什么？它们是什么关系？c.什么是算法？它有什么特点？,25,习题与练习一,2.试写一个算法，统计输入的100个整数中奇数和偶数的个数。3.设计下面问题算法，并分析最坏情况时间复杂性:在数组A1.n中查找值为K的元素，若找到输出其位置i(0in+1),否则输出0。,26,习题与练习一,4.设n为正整数，写出下列程序段的时间复杂度：（1）for(I=1;In;I+)m=m+I;for(j=0;jn;j+)count+=m+j;,27,习题与练习一,（2）for(I=0;In;I+)m=m+I;for(j=0;j10;)count+=m+j;j+;,28,习题与练习一,（3）k=1;s=0;while(s=i;j-)vj=vj-1;vj=x;*p=+n;return(1);,53,2.2线性表的顺序存储和实现,插入一个元素图示1,54,2.2线性表的顺序存储和实现,插入一个元素图示2,x,55,2.2线性表的顺序存储和实现,插入算法时间复杂度T(n)Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：,56,2.2线性表的顺序存储和实现,向线性表中表头插入一个元素,InsertFront(List,57,2.2线性表的顺序存储和实现,向线性表中满足条件的位置插入一个元素,voidInsert(List,58,2.2线性表的顺序存储和实现,向线性表中的末尾添加一个元素,voidInsertRear(List,59,变成长度为n-1的线性表,需将第i+1至第n共（n-i）个元素前移,2.2线性表的顺序存储和实现,删除一个元素定义：线性表的删除是指将第i（1in）个元素删除，使长度为n的线性表,60,2.2线性表的顺序存储和实现,删除一个元素算法,intsxbsc(inti,intv,int*p)intj,n;n=*p;if(in)return(0);for(j=i;jn;j+)vj-1=vj;*p=-n;return(1);,61,2.2线性表的顺序存储和实现,删除一个元素图示1,62,2.2线性表的顺序存储和实现,删除一个元素图示2,63,故在顺序表中插入或删除一个元平均移动表的一半元素，当n很大时，效率很低,2.2线性表的顺序存储和实现,删除算法评价,设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：,64,2.2线性表的顺序存储和实现,从线性表中删除等于给定值的元素1,intDelete(List,65,2.2线性表的顺序存储和实现,从线性表中删除等于给定值的元素2,if(i=L.size)printf(“Deletedelementisnotexist!”);return0;for(intj=i+1;jL.size;j+)L.listj-1=L.list;L.size-;return1;,66,例已知线性表(ao，a1，an-1)按顺序存储，且每个元素都是均不相等的整数。设计把所有奇数移到所有的偶数前边的算法(要求时间最少，辅助空间最少)。,2.2线性表的顺序存储和实现,解从左向右找到偶数A.datai，从右向左找到奇数A.dataj，将两者交换；循环这个过程直到i大于j为止,67,2.2线性表的顺序存储和实现,voidmove(sqlistA)inti=0,j=A.len-l,k;ElemTypetemp;while(inext表示p指向结点的指针域生成一个LNode型新结点：p=(LNode*)malloc(sizeof(LNode);系统回收p结点：free(p),2.3线性表的链式存储结构,75,2.3线性表的链式存储结构,头结点：在单链表第一个结点前附设的一个结点。头结点指针域为空表示线性表为空,76,2.3线性表的链式存储结构,在带头节点的单链表中查找第i个结点,StatusListSearch_L(LinkListL,inti,ElemType*e)P=L-next;j=1;While(!preturnOK；,77,2.3线性表的链式存储结构,在带头节点的单链表中第i个结点处插入新元素x,78,2.3线性表的链式存储结构,StatusListInsert_L(LinkListL,ElemTypex,constinti)p=L;j=0;while(p,79,2.3线性表的链式存储结构,删除元素：,80,2.3线性表的链式存储结构,StatusListDelete_L(LinkListL,intI,ElemType*e)P=L;j=0;While(p-next/ListDelete_L,删除元素：,81,2.3线性表的链式存储结构,两个有序单链表合并为一个有序单链表(非递减),MergeList_L(LinklistLa,LinkListLb,LinkListLc)pa=La-next;pb=Lb-next;Lc=pc=La;While(pa,82,它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢,2.3线性表的链式存储结构,单链表具有单向性的缺点,单链表特点,83,2.3线性表的链式存储结构,循环链表:表中最后一个结点的指针指向头表p或p-next=H结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率,84,2.3线性表的链式存储结构,循环链表操作与单链表基本一致,循环条件不同单链表:p或p-next=NULL循环链:p或p-next=H,85,2.3线性表的链式存储结构,2.3.3双向链表（doublelinkedlist),指向前驱结点,数据,指向后继结点,结点定义typedefstructnodedatatypedata;structnode*prior,*next;DLNode,*DLinkLIst,86,空双向循环链表：,非空双向循环链表：,L,2.3线性表的链式存储结构,双向链表图例,87,p-prior-next=p=p-next-proir;,2.3线性表的链式存储结构,双向链表图例,88,2.3线性表的链式存储结构,在给定结点p前插入一个新结点,89,在给定结点p前插入一个新结点,S=(DLinklist)malloc(sizeof(DLNode);s-data=x;s-prior=p-prior;s-next=p;p-prior-next=s;p-prior=s;,2.3线性表的链式存储结构,90,p-prior-next=p-next;,p-next-prior=p-prior;,2.3线性表的链式存储结构,删除给定结点p,91,p-prior-next=p-next;,p-next-prior=p-prior;,删除给定结点p动画演示,2.3线性表的链式存储结构,92,p-prior-next=p-next;p-next-prior=p-prior;free(p);,删除给定结点p算法,就这么简单！,2.3线性表的链式存储结构,93,3存储结构的选用,顺序与链式存储结构的选用应考虑因素：（1）存储空间（2）运算时间（3）程序设计语言,94,习题与练习二,1.描述以下三个概念的区别：头结点、头指针和开始结点2.从尾指针出发能访问到链表上所有结点的链表有。3.假设有两个按元素值递增的线性表A、B，编写算法将两表合并为一个按元素值递减的线性表C。（分别以顺序、链式实现）,95,习题与练习二,4.设线性表存放在向量AMAXSIZE的前elenum个分量中，且递增有序。试写一算法，将x插入线性表适当位置上，以保持线性表的有序性，并且分析算法的时间复杂性。5.以链式存储结构实现上题。,96,习题与练习二,6.在双向链表上实现线性表的下列基本运算：(1)初始化(2)定位(3)插入(4)删除,97,【学习内容】栈的抽象数据类型、顺序表示、链表表示及相应操作(特别注意栈空和栈满的条件）队列的定义、特性队列的抽象数据类型、顺序表示、链表表示及相应操作（特别是循环队列中队头与队尾指针的变化情况）栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS。,第三章栈与队列,98,第三章栈与队列,3.1栈（stack）,3.1.1定义通常称插入、删除的这一端（如表尾）为栈顶(Top)，另一端（表头）为栈底(Bottom)。当表中没有元素时称为空栈特点：先进后出（FILO）或后进先出（LIFO）,99,例：假设栈S=(a1，a2，a3，an)则a1称为栈底元素，an为栈顶元素。进栈top+1;新元素插入elementstop位置出栈top-1;栈中元素按a1，a2，a3，an的次序进栈，退栈按后进先出的原则进行的,因此按ana3a2a1的次序出栈,3.1栈（stack）,100,3.1栈（stack）,栈的主要操作：,（1）建立一个空栈IniStack(新元素插入elementstop位置出栈：top-1,栈s=(a1,a2,an),3.1栈（stack）,栈的图示,102,3.1栈（stack）,栈和线性表类似，也有两种（顺序、链式）实现方法,103,存储结构定义#defineMAXSIZE6typedefstructdatatypeelementsMAXSIZE;inttop;SqStack;,3.1栈（stack）,一、栈的顺序存储,104,3.1栈（stack）,栈的顺序存储,栈顶指针top指示栈顶元素在顺序栈中的top=-1,栈空，此时出栈，则下溢（underflow）top=MAXSIZE-1,栈满，此时入栈，则上溢（overflow）,105,3.1栈（stack）,顺序栈进、出栈图示,栈顶指针top,指向实际栈顶后的空位置，初值为-1,进栈,A,出栈,栈满,B,C,D,E,F,设数组维数为Mtop=-1,栈空，此时出栈，则下溢（underflow)top=M-1,栈满，此时入栈，则上溢（overflow),栈空,106,StatusPush(SqStack*S,datatypee)If(S-top=MAXSIZE-1)/*上溢*/returnERROR;S-top+;S-elementsS-top=e;returnOK;,3.1栈（stack）,进栈算法,107,3.1栈（stack）,出栈算法,StatusPops(SqStack*S,datatype*e)If(S-top=-1)/*下溢*/returnERROR;S-top-;*e=S-elementsS-top+1;returnOK;,108,二、链栈（单链表）,3.1栈（stack）,typedefstructnodeintdata;structnode*link;LinkList;,结点定义,109,3.1栈（stack）,链栈的特点,链表的存储结构与链接存储的栈完全相同，只是链头指针就是栈顶指针。初始时为NULL链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作,110,3.1栈（stack）,链栈的进栈算法,进栈等同于不带头结点单链表的头插法StatusPush(LinkList*S,datatypee)p=(LinkList)malloc(sizeof(Linklist);p-data=e;p-next=S-top;S-top=p;returnOK;,111,3.1栈（stack）,链栈的出栈算法,出栈等同于删除第一个结点StatusPop(LinkList*S,datatype*e)If(S-top)returnERROR;/*下溢*/p=S-top;S-top=p-next;*e=p-data;free(p);returnOK;,112,3.1栈（stack）,3.1.3栈的应用,(1)“回溯”问题求解(2)过程的嵌套和递归调用,113,1嵌套调用,3.1栈（stack）,3.1.3栈的应用,114,s,3.1栈（stack）,嵌套调用过程图示,115,递归：函数直接或间接的调用自身的过程一个对象部分地包含它自己，或是用它自己给自己定义一个过程直接地或间接地调用自己利用前面运算来求得答案的过程实现：建立递归工作栈优点：递归函数结构清晰，程序易读，正确性易证明缺点：速度慢，空间大效率低,3.1栈（stack）,2递归调用,116,3.1栈（stack）,voidp(参数表)if（递归结束条件）可直接求解步骤；-基本项elsep（较小的参数）；-归纳项,递归算法的一般形式,117,3.1栈（stack）,例：求n!=,1，n=0n*(n-1)！n0,intFactorial(intn)if(n=0)return1;returnn*Factorial(n-1);,118,例：递归的执行情况分析,3.1栈（stack）,119,voidprint(Intw)inti;if(w!=0)print(w-1);for(i=1;idata=x;p-next=NULL;Q-rear-next=p;Q-rear=p;,131,3.2队列（QUEUE）,链队列出队算法,if(Empty(Q)returnERROR;elses=Q-front-next;/*指向被删结点*/if(s-next=NULL)Q-front-Next=Null;Q-rear=Q-front;ElseQ-front-next=s-next;*e=s-data;free(s);returnOK;,132,3.2队列（QUEUE）,J1,J2,J3,设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1,空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;,三、循环队列-队列的顺序表示和实现,133,3.2队列（QUEUE）,存在问题,设数组维数为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出真溢出当front-1,rear=M-1时，再有元素入队发生溢出假溢出解决方案:队首固定，每次出队剩余元素向下移动浪费时间循环队列,134,循环队列基本思想：存储队列的数组被当作首尾相接的表处理；让sq0接在sqM-1之后，若rear+1=M,则令rear=0。,3.2队列（QUEUE）,实现：利用“模”运算入队：rear=(rear+1)%M;sqrear=x;出队：front=(front+1)%M;x=sqfront;队满、队空判定条件,135,rear,front,maxSize-1,入队:rear=(rear+1)%MaxSize;elementsrear=item出队：front=(front+1)%MaxSize;,队空：rear=front;队满：(rear+1)%maxSize=front;,0,1,2,front,0,1,2,rear,队列初始化：front=rear=0;,存储队列的数组被当作首尾相接的表处理。队头、队尾指针加1时从MaxSize-1直接进到0，可用语言的取模(余数)运算实现。,3.2队列（QUEUE）,136,3.2队列（QUEUE）,初始状态,解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front=rear队满：(rear+1)%M=front,循环队列出入队图示,队空：front=rear队满：front=rear,137,3.2队列（QUEUE）,少用一个元素空间解决方案,队空rear=front;队满(rear+1)%maxSize=front;入队rear=(rear+1)%MaxSize;elementsrear=item；出队front=(front+1)%MaxSize;,138,voiden_cycque(intsq,intfront,intrear,intx)if(rear+1)%MAXSIZE)=front)printf(overflow);elserear=(rear+1)%MAXSIZE;sqrear=x;,3.2队列（QUEUE）,循环队列入队算法,139,循环队列出入队图示,3.2队列（QUEUE）,intdel_cycque(intsq,intfront,intrear,int*q)if(front=rear)return(0);elsefront=(front+1)%MAXSIZE;*q=sqfront;return(1);,140,1.铁路进行列车调度时,常把站台设计成栈式结构的站台，如右图所示。试问：,(1)设有编号为1,2,3,4,5,6的六辆列车,顺序开入栈式结构的站台,则可能的出栈序列有多少种?(2)若进站的六辆列车顺序如上所述,那么是否能够得到435612,325641,154623和135426的出站序列,如果不能,说明为什么不能;如果能,说明如何得到(即写出进栈或出栈的序列)。,第三章习题与上机实验,141,第三章习题与上机实验,2.假设以数组Qm存放循环队列中的元素,同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件,并写出相应的插入(enqueue)和删除(delqueue)元素的操作。,142,第四章数组,数组的顺序表示和实现矩阵的压缩存储:特殊矩阵稀疏矩阵,【学习内容】,143,4.1数组的定义及运算,数组的性质,数组元素数目固定元素类型相同下标有界且有序,144,一维数组,数组图示,4.1数组的定义及运算,eg.a1,a2,（a11,a12,a1n）,(a21,a22,a2n),145,二维数组,4.1数组的定义及运算,数组图示,三维数组,146,4.1数组的定义及运算,定义：由值和下标构成的有序对，结构中的每一个元素都与一对下标有关。运算：给定一组下标，存取相应DE给定一组下标，修改相应DE,147,42数组的顺序表示,元素数目、关系固定,顺序存储,多维数组以一维方式存储，即数组元素还是数组！,问题：内存是一维的，如何以一维内存存储多维数组,148,42数组的顺序表示,LOC(i)=LOC(i-1)+l=+i*l,一维数组的存储,149,42数组的顺序表示,二维数组的存储,150,52数组的顺序表示,行优先LOC(i,j)=a+(i0)*m+(j-0)*l,列优先LOC(i,j)=a+(j-0)*n+(i0)*l,例：,151,n维数组,各维元素个数为m1,m2,m3,mn下标为i1,i2,i3,in的数组元素的存储地址：,42数组的顺序表示,152,43矩阵的压缩存储,压缩存储,多个值相同的元素只分配一个空间，零元素不分配空间,153,一、特殊矩阵定义：相同元素/零元素分布有一定规律的矩阵。,1.对角矩阵,43矩阵的压缩存储,154,若将以上两矩阵以一维数组BM压缩存储,aijbk,三对角阵,单对角阵,43矩阵的压缩存储,155,2.上（下）三角矩阵,0,0,非零元素共n(n+1)/2个，以数组Bn*(n+1)/2存储非零DE,43矩阵的压缩存储,156,下三角,2.上（下）三角矩阵,上三角,43矩阵的压缩存储,157,3.对称矩阵,aij=ajik=I(I+1)/2+J;I=max(i,j),J=min(i,j),43矩阵的压缩存储,好东西啊！,158,二.稀疏矩阵,Am*n中非零元素个数远小于零元素个数,43矩阵的压缩存储,1三元组表组成：所有非零元素（行，列，值）+（行数，列数，非零元素个数）,159,三元组表类型说明：#defineSMAX16typedefintdatatype；typedefstructinti,j;/*行列号*/datatypev;/*元素值*/node;typedefstructintm,n,t;/*行、列数，非零元素个数*/nodedataSMAX;/*三元组表*/SpMatrix;,43矩阵的压缩存储,160,43矩阵的压缩存储,三元组表示例,行数列数元素个数,行列值,161,43矩阵的压缩存储,例：矩阵转置：Am*n-Bn*m且aij=bji,162,(1)一般矩阵：for(row=0;rown=M.m;T-t=M.t;if(T-t)q=1;for(col=1;coldataq.i=M.datap.j;T-dataq.j=M.datap.i;T-dataq.v=M.datap.v;q+;returnOK;,43矩阵的压缩存储,时间复杂度：O(n*t),166,第五章树,学习内容树的定义和基本术语二叉树的定义、性质和存储结构树和森林的存储结构、树与二叉树的转换哈夫曼树及其应用,167,第五章树和二叉树,树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。,树结构在客观世界是大量存在的：家谱、行政组织机构树在计算机领域中也有着广泛的应用：编译程序中，用树来表示源程序的语法结构在数据库系统中，可用树来组织信息在分析算法的行为时，可用树来描述其执行过程,168,5.1树的定义和基本术语,一、定义,树是一类重要的非线性数据结构，是以分支关系定义的层次结构,定义：树(tree)是n(n=0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根(root)，它只有直接后继，但没有直接前驱；当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)如果n=0，称为空树；,169,5.1树的定义和基本术语,要专心噢！,特点：树中至少有一个结点-根树中各子树是互不相交的集合,170,5.1树的定义和基本术语,171,5.1树的定义和基本术语,树的基本运算,初始化InitTree(如果2in，则其左孩子是2i(3)如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1(4)若i为奇数,且i不为1，则其左兄弟为i-1，否则无左兄弟若i为偶数,且小于n，则其右兄弟为i+1，否则无右兄弟(5)i所在层次为log2(i)+1,191,满二叉树也是完全二叉树,结点i的左子结点是2i右子结点是2i+1,完全二叉树,5.2.2二叉树性质,192,5.2.3二叉树的存储结构,一、顺序存储结构,实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素数组表示特点：结点间关系蕴含在其存储位置中适于存满二叉树和完全二叉树,无需任何附加存储单元来存放指针，具有顺序存储的固有缺点定义：defineN50/树结点的MaxtypedefelemtypeSQTREEN;,非完全二叉树要补成完全二叉树,193,5.2.3二叉树的存储结构,二叉树的数组表示,完全二叉树的数组表示一般二叉树的数组表示,194,5.2.3二叉树的存储结构,由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。,单支树,195,5.2.3二叉树的存储结构,二、链式存储结构,196,5.2.3二叉树的存储结构,typedefstructnodedatatypedata;structnode*lchild,*rchild;JD,bitree;,二叉链表-2个指针域,197,在n个结点的二叉链表中，有n+1个空指针域,5.2.3二叉树的存储结构,二叉链表图示,198,5.2.3二叉树的存储结构,三叉链表-3个指针域,typedefstructnodedatatypedata;structnode*lchild,*rchild,*parent;JD;,199,5.2.3二叉树的存储结构,200,5.3遍历二叉树,遍历按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列,201,5.3遍历二叉树,6.3.1二叉树的遍历方法：1.先序遍历：先访问根结点,然后分别先序遍历左子树、右子树DLR2.中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树LDR3.后序遍历：先后序遍历左、右子树，然后访问根结点LRD4.按层次遍历：从上到下、从左到右访问各结点DLR,202,5.3.1二叉树的遍历,设访问根结点记作D遍历根的左子树记作L遍历根的右子树记作R则可能的遍历次序有,203,5.3.1二叉树的遍历,1.先序遍历,先序遍历二叉树算法的框架是若二叉树为空，则空操作；否则访问根结点(V)；先序遍历左子树(L)；先序遍历右子树(R)。遍历结果-+a*b-cd/ef,204,5.3.1二叉树的遍历,PreOrder(BinTreeNode*current)if(current!=NULL)Visit(currentdata);PreOrder(currentleftChild);PreOrder(currentrightChild);,先序遍历递归算法如下：,205,5.3.1二叉树的遍历,DLR,先序遍历序列：ABDC,先序遍历:,206,5.3.1二叉树的遍历,VoidPreOderTraverse(BiTreeT)if(T!=NULL)printf(T-data);PreOrderTraverse(T-lchild);PreOrderTraverser(T-rchild);/*先序遍历*/,返回,返回,返回,返回,A,C,B,D,返回,207,5.3.1二叉树的遍历,2.中序遍历,中序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根结点(V)；中序遍历右子树(R)。遍历结果a+b*c-d-e/f,208,5.3.1二叉树的遍历,InOrder(BinTreeNode*current)if(current!=NULL)InOrder(currentleftChild);Visit(currentdata);InOrder(currentrightChild);,中序遍历地归算法如下：,209,5.3.1二叉树的遍历,LDR,中序遍历序列：BDAC,中序遍历:,210,5.3.1二叉树的遍历,后序遍历二叉树算法的框架是若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根结点(V)。遍历结果abcd-*+ef/-,3.后序遍历,211,LastOrder(BinTreeNode*current)if(current!=NULL)LastOrder(currentleftChild);LastOrder(currentrightChild);Visit(currentdata);,后序遍历地归算法如下：,5.3.1二叉树的遍历,212,5.3.1二叉树的遍历,LRD,后序遍历序列：DBCA,后序遍历:,213,5.3.1二叉树的遍历,层次遍历二叉树算法的框架是若二叉树为空，则空操作；否则，如队列不空，循环：根结点入队，并作为当前结点；将当前结点的左右孩子入队；做出队操作，队首元素作为当前结点最后，出队序列就是层序遍历序列遍历结果-+/a*efb-cd,4.按层次遍历,214,5.3.1二叉树的遍历,5.非递归算法遍历二叉树（以中序为例）递归算法逻辑清晰、易懂，但在实现时，由于函数调用栈层层叠加，效率不高，故有时考虑非递归算法。,215,5.非递归算法遍历二叉树（以中序为例）,5.3.1二叉树的遍历,在中序遍历中，最先访问的结点是最左下方结点先找到左下结点，即沿左链一直下来，直到左链为空，这时，所有路过的结点进栈。然后结点出栈并访问，对于每个出栈结点，即表示该结点和其左子树已被访问结束，应该访问该结点的右子树。（1）当前指针指向根结点。（2）当前指针指向其左孩子并进栈，重复（2），直到左孩子为NULL（3）退栈，打印出栈结点，将当前指针指向右孩子，（4）若栈非空或当前指针非NULL，执行（2）；否则结束。,216,5.3.1二叉树的遍历,InOrder(BinTreeNode*T)InitStack(s);p=T;While(p|!StackEmpty(s)if(p!=NULL)Push(s,p);p=p-lchild;ElsePop(s,p);visit(p-data);P=p-rchild;,中序遍历非递归算法,217,5.3.1二叉树的遍历,二叉树的遍历方法小结,先序遍历：,中序遍历：,后序遍历：,层次遍历：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,218,5.3.1二叉树的遍历,二叉树的小结,1、二叉树：或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树；2、二叉树即可以用顺序结构存储，也可用链式结构存储；3、遍历：按某种搜索路径访问二叉树的每个结点，每个结点仅被访问一次。二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树，三种遍历算法：先序遍历、中序遍历、后序遍历；,219,5.3.2二叉树的遍历应用,方法：对二叉树进行遍历，判断被访问的结点是否叶子结点，若是叶子结点，则将计数器加1。,intcountleaf(BiTree)intn1,n2;if(T=NULL)return(0);elseif(T-lchild=NULL),一、统计二叉树中叶子结点的个数,220,5.3.2二叉树的遍历应用,intdepth(biter*t)intdep1,dep2;if(t=NULL)return(0);elsedep1=depth(t-lchild);dep2=depth(t-rchild);if(dep1dep2)return(dep1+1);elsereturn(dep2+1);,二、求二叉树的深度二叉树深度=MAX(左子树深度，右子树深度）+1,221,孩子兄弟表示法（二叉树表示法）,5.4树的存储结构,实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点特点操作容易破坏了树的层次,typedefstructnodedatatypedata;structnode*fch,*nsib;JD;,222,5.4.1树的存储结构,孩子兄弟存储结构是为每个结点设计三个域：一个数据元素域，一个该结点的第一个孩子结点指针域，一个该结点的下一个兄弟结点指针域。由于树的孩子兄弟存储结构有两个指针域，并且这两个指针是有序的，所以孩子兄弟存储结构是把树转换为二叉树的存储结构。把树转换为二叉树所对应的结构恰好就是这种孩子兄弟存储结构孩子兄弟存储结构的最大优点是可方便地实现树和二叉树的相互转换。孩子兄弟存储结构的缺点也和孩子表示法的缺点一样：从当前结点查找双亲结点比较麻烦，需要从树的根结点开始逐个结点比较查找。,223,5.4.2树与二叉树的转换,树与二叉树上结点的对应关系二叉树中各结点：左孩子-该结点的第一个孩子右孩子-该结点的第一个右兄弟注：由一棵树转换得到的二叉树必无右子树（思考：为什么？）,224,5.4.2树与二叉树的转换,225,5.4.2树与二叉树的转换,树转换成二叉树,226,5.4.2树与二叉树的转换,树转换成二叉树,227,5.4.2树与二叉树的转换,森林转化成二叉树的规则,若F为空，即n=0，则对应的二叉树B为空二叉树。若F不空，则对应二叉树B的根root(B)是F中第一棵树T1的根root(T1)；其左子树为B(T11,T12,T1m)，其中，T11,T12,T1m是root(T1)的子树；其右子树为B(T2,T3,Tn)，其中，T2,T3,Tn是除T1外其它树构成的森林。,228,5.4.2树与二叉树的转换,森林转换为二叉树,方法：将各棵树分别转成二叉树；把每棵树的根结点用线连起来；以第一棵树的根结点作为二叉树的根结点，按顺时针方向旋转。,229,5.4.2树与二叉树的转换,森林转换为二叉树,230,5.4.2树与二叉树的转换,森林与二叉树的对应关系,231,5.4.2树与二叉树的转换,如果B为空，则对应的森林F也为空。如果B非空，则F中第一棵树T1的根为root；T1的根的子树森林T11,T12,T1m是由root的左子树LB转换而来，F中除了T1之外其余的树组成的森林T2,T3,Tn是由root的右子树RB转换而成的森林。,二叉树转换为森林的规则,232,二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树还原：将孤立的二叉树还原成树,5.4.2树与二叉树的转换,233,5.4.3树与森林的遍历,常用方法（前）先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点按层次遍历：先访问第一层上的结点，然后依次遍历第二层，第n层的结点,234,5.4.3树与森林的遍历,一、树的遍历,前序遍历若树非空，则1、访问根结点2、依次前序遍历树的各子树,遍历序列：A，B，E，F，C，G，D，H，I，J,235,5.4.3树与森林的遍历,后序遍历若树非空，则1、依次前序遍历树的各子树2、访问根结点,遍历序列：E，F，B，G，C，H，I，J，D，A,236,5.4.3树与森林的遍历,层序遍历,遍历序列：A，B，C，D，E，F，G，H，I，J,237,5.4.3树与森林的遍历,先序遍历：,后序遍历：,层次遍历：,A,B,E,F,I,G,C,D,H,J,K,L,N,O,M,E,I,F,G,B,C,J,K,N,O,L,M,H,D,A,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,树的遍历小结,按广度,按深度,238,5.4.3树与森林的遍历,二、森林的遍历,森林的遍历即多棵树的遍历，单棵树的遍历与树的遍历相同，逐棵树进行遍历。,239,先序遍历森林若森林非空先访问第一棵树的根结点，再先序遍历第一棵树根的子森林，再先序遍历除去第一棵树后剩余的子森林。转换成二叉树后与二叉树的先序遍历相同,5.4.3树与森林的遍历,240,5.4.3树与森林的遍历,中序遍历森林若森林非空中序遍历第一棵树根的子森林访问第一棵树的根中序遍历去掉第一棵树后剩余的子森林转换成二叉树后与二叉树的中序遍历相同,241,5.4.3树与森林的遍历,先序遍历,A,B,C,D,E,F,G,H,I,J,ABCDEFGHIJ,中序遍历,BCDAFEHJIG,森林的遍历,242,先序遍历,ABCDEFGHIJ,中序遍历,BCDAFEHJIG,5.4.3树与森林的遍历,森林转换成的二叉树的遍历,243,5.5哈夫曼树及应用,定义路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径路径长度：路径上的分支数树的路径长度：从树根到每一个结点的路径长度之和树的带权路径长度：树中所有带权结点的路径长度之和,哈夫曼树(Huffman)带权路径长度最短的树,244,5.5.1哈夫曼树,Huffman树设有n个权值w1,w2,wn，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫Huffman树。,构造Huffman树的方法Huffman算法,构造Huffman树步骤根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，令起权值为wj在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和在森林中删除这两棵树，同时将新得到的二叉树加入森林中重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树,245,5.5.1哈夫曼树,例有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树,WPL=7*2+5*2+2*2+4*2=36,WPL=7*3+5*3+2*1+4*2=46,WPL=7*1+5*2+2*3+4*3=35,要使二叉树WPL小,就须在构造树时,将权值大的结点靠近根.,246,5.5.1哈夫曼树,构造Huffman树的方法Huffman算法,247,5.5.1哈夫曼树,例w=5,29,7,8,14,23,3,11,248,5.5.2哈夫曼编码,哈夫曼编码在进行数据通讯时，涉及数据编码问题。所谓数据编码就是数据与二进制字符串的转换。例如：邮局发电报,例要传输的原文为ABACCDA等长编码A：00B：01C：10D：11发送方：将ABACCDA转换成00010010101100接收方：将00010010101100还原为ABACCDA,不等长编码A：0B：00C：1D：01发送方：将ABACCDA转换成000011010接收方：000011010转换成,A的编码是B的前缀,249,设A：0B：110C：10D：111发送方：将ABACCDA转换成0110010101110总长度是13所得的译码是唯一的,前缀编码：任何字符编码不是其它字符编码的前缀,5.5.2哈夫曼编码,250,5.5.2哈夫曼编码,思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列,Huffman编码：数据通信用的二进制编码,251,例要传输的字符集D=C,A,S,T,;字符出现频率w=2,4,2,3,3,T:00;:01A:10C:110S:111,5.5.2哈夫曼编码,252,5.5.2哈夫曼编码,从Huffman树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束,例电文是CAS;CAT;SAT;AT其编码“11010111011101000011111000011000”电文