数据结构学习分享

数据结构学习分享一些看法学了数据结构的同学，不是被数据结构伤的百孔千疮，就是产生了心理阴影，太难太绕了。辛辛苦苦的学的差不多了吧，做程序的时候，好像根本用不上数据机构一样。此乃神物，花费那么大的力气学，到时候用不上岂不是太亏了。很多很多的文章很多很多的过来人，都告诉你，数据结构很重要。老师上来就跟你说，这个很重要很重要。其实没有几个老师能跟你讲清楚数据结构到底是什么，以至于你学完了都不知所云。都不知道学完后怎么用，如何用，有没有用。虽然他们都说有用，非常有用，那怎么个有用法，很少提及。甚至，在工作中怎么体现的也不曾提及。似乎数据结构就是什么栈、链表、二叉树、图之类的。其实这些东西不是数据结构。作为一个特别爱思考的人，没有一个清晰的方向，学起来也是痛苦的，也是盲目的，虽然知道有用，但是还是如此。或者换一种说法，清楚了自己学的东西，不仅学起来目标明确，心情也爽快，同时效率还会很高。数据结构+算法=程序其实，算法和数据结构并非一个东西，数据结构也不是链表之类的。这些都是错误的信号。数据结构是一门抽象的学科。这个确实如此。而且非常抽象。然而我们的学习，最好是从具体的开始东西开始，这样学习效果更好。很少有人一开始抽象思维就很好的，抽象思维是通过大量的培养才得到的。实际上在潜意识里，抽象思维好的人总会无意识的将一个抽象模型关联到他熟知的一个东西或者现象中。而这些联系在讲授或学习知识的时候，又忽略了。才导致抽象的东西，越来越抽象，或者说，我们没有能够将抽象的东西足够的具体化成一个实例。所以，你在学习的时候，尽量联系实际中的案例来理解。数据结构和算法，都是一种抽象的东西。其实就是人的思想。学好数据结构和算法，就是去掌握那些别人已经想出来的思想而已。并不是让你去记住这些东西如何实现，怎么写代码怎么考试。而我们学到的各种数据结构，是为了算法思路好完成逻辑而构建的一些固定的模型，这些模型只是人为的一个规定而已。或者说，我们只是将这些比较不错的想法思路取一个名字，然后大家交流的时候，说起这个名字就知道了这个数据结构等。例如我们学习链表结构之类的，就是人家建立的一个固定的模型，或者叫做一个约定的操作方式。那么既然这些别人实现的都是一个典型的操作方式，那么必然有他的优点，我们才需要学习的。然而你既然知道了天机，那么自然就可以去藐视天机，可以去创造，而不是一味的接受。既然是一种思想，你完全可以通过你自己的智慧去改善他的思想，这个就是思想更迭的过程。并不是后来人比前面的人聪明，而是因为他站在巨人的肩膀上起飞的。国内的教育都是应试教育，没有挖掘这种创造力，然而，要想把这门课学好，就需要充分发挥创造力。你完全可以在掌握一种数据结构模型后，改造它。可以创造出更好的数据结构模型，在今后的多少年，可能教材里的结构就出现了你的结构模型了。以上是如何学习思想的看法。算法则是一套思维的流程，以何种逻辑或者说是运算的先后顺序将一个目标实现。比如说，冒泡排序，最终的目标是将一组数据拍好顺序，至于如何实现，其实可以有多种，并不是唯一的。冒泡代表一种思想。你只需要弄懂这个思想的关键，如何一步步运作到实现目标的这个流程，就可以了。基于这个流程，你可以使用另外的实现方式来做到需要的目标，而不必拘泥于课本上的实现过程。否则，你永远都学不会算法。通常，算法都要用到数据结构的各种模型，这些模型的建立，就是为了方便完成算法的逻辑流程的。正是这些数据结构的存在，让效率大大提升，或者让操作过程更加简便。如果你能理解我说的这些，说明你有所领悟，而彻底明白，只是时间的问题了，前提是要继续思考。当你领悟到数据结构和算法不再是书上那些东西，你就成功了一大半了。当你的思维高于书上的东西，你学起来，那就简单多了。至少你不会再迷茫，而只是熟悉那些套路而已了。你改进一个算法才成为可能，从此就不是死读书的模式学习数据结构了。数据结构的研究内容03/02/202314【数据结构的三个方面研究内容】具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存储结构和对数据所施加的运算（操作）。

数据的逻辑结构（面向人类）

数据的存储结构（面向计算机）

数据的运算（操作）：检索、排序、插入、删除、修改等

线性结构

非线性结构顺序存储链式存储线性表栈队列树形结构图形结构散列存储索引存储串及数组第一讲绪论了解数据结构有关概念的含义，特别是数据的逻辑结构和存储结构之间的关系；（重点）熟悉类C语言的书写规范；了解计算算法时间复杂度的方法。（难点）03/02/202315数据结构的定义按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。基本概念和术语【数据】是对信息的一种符号表示。是可以输入计算机中，

能被计算机识别处理和输出的一切符号集合。【数据元素】是数据的基本单位，在计算机中通常作为一个

整体进行考虑和处理。也称为记录。【数据项】一个数据元素可由若干个数据项组成。是数据不

可分割的最小单位。【数据对象】是性质相同的数据元素的集合。是数据的一个

子集。03/02/202317【数据结构】相互之间存在一种或多种特定关系的数据

元素的集合计算机如何解决问题03/02/202318问题机外表示处理要求逻辑结构基本运算数学模型存储结构编程实现实现建模求精研究数据结构是为了帮计算机解决问题！四种基本逻辑结构03/02/202319【集合】——数据元素间除了“同属于一个集合”外，无其他关系。【线性结构】——

1对1的关系比如线性表、栈、队列。【树形结构】——

1对多的关系比如树。【图形结构】——多对多的关系比如图。算法与数据结构算法与数据结构关系密切选择的数据结构是否恰当直接影响算法的效率；而数据结构的优劣由算法的执行来体现。“算法+数据结构=程序”算法!=程序算法是供人阅读的，程序是让机器执行的算法用计算机语言实现时就是程序程序不具有算法的有穷性算法的概念算法是解决某个特定问题的求解步骤的描述。算法在计算机中表现为指令的有限序列，每条指令表示一个或多个操作。计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。程序不等于算法：计算机程序是算法的具体实现。03/02/202321（1）有穷性：一个算法必须在执行有穷步之后结束。（2）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。（3）可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。（4）输入：一个算法应该有零个或多个输入。（5）输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。算法的性质算法设计的要求正确性（四个境界）没有语法错误对于合法的输入数据能够产生满足要求的输出对于非法的输入数据能够得出满足规格说明的结果对于任何测试数据都有满足要求的输出结果可读性：便于阅读、理解和交流健壮性：不合法数据也能合理处理时间效率高和存储量低03/02/202323算法效率的度量方法事后统计方法通过设计好的测试程序和数据，利用计算机测量其运行时间。缺陷：需要先编写程序；和计算机软硬件相关；和测试数据相关。事前分析估算方法（我们的选择）依据统计方法对算法进行估算。m=f(n)，m是语句总的执行次数，n是输入的规模。和问题输入规模相关，独立于程序设计语言和计算机软硬件

03/02/202324算法时间复杂度03/02/202325在进行算法分析时，语句的总执行次数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((2n3+3n2+2n+1)/n3)

=2n→∞n→∞则算法的时间复杂度为O(n3)算法空间复杂度03/02/202327

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。

我们主要讨论时间复杂度问题。例题解析【例1】数据元素之间的关系在计算机中有几种表示方法？各有什么特点？答：四种表示方法（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。（3）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。03/02/202328例题解析【例2】有下列运行时间函数：（1）T1(n)=1000;（2）T2(n)=n2+1000n;（3）T3(n)=3n3+100n2+n+1;分别写出相应的大O表示的运算时间答：(1)O(1)(2)O(n2)(3)O(n3)03/02/202329第二讲线性表线性结构的定义和特点在数据元素的非空有限集中，有且仅有一个开始结点和一个终端结点，并且所有结点只有一个直接前趋和一个直接后继。简言之，线性结构反映结点间的逻辑关系是

一对一。线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最简单、最常用的是线性表。线性表的存储方法顺序存储：逻辑上相邻物理上一定相邻链式存储：逻辑上相邻物理上不一定相邻顺序表顺序表——线性表的顺序存储表示顺序存储——用一组地址连续的存储单元依次存储线性表的元素，可通过数组来实现。（逻辑上相邻物理上一定相邻）

LOC(ai

)=LOC(a1)+(i-1)len

（a1为首元素，len为单个元素占用空间长度）顺序存储的优点可以随机存取表中任一元素O(1)；存储空间使用紧凑顺序存储的缺点在插入元素时平均需要移动n/2个元素，删除某一元素时，平均需要移动n-1/2个元素。算法的平均时间复杂度为O(n)预先分配空间需按最大空间分配，利用不充分;表容量难以扩充03/02/202331链表链式存储结构特点用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息

链式存储结构的优点：结点空间可以动态申请和释放；数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素。链式存储结构的缺点：每个结点的指针域需额外占用存储空间。当数据域所占字节不多时，指针域所占存储空间的比重显得很大。链表是非随机存取结构。对任一结点的操作都要从头指针依链查找该结点，这增加了算法的复杂度O（n）不便于在表尾插入元素：需遍历整个表才能找到位置。03/02/202332例题解析【例1】说明在线性表的链式存储结构中，头指针与头结点之间的根本区别。答：在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。03/02/202333例题解析

【例2】设顺序表va中的数据元素递增有序。试设计一个算法，将x插入到顺序表的适当位置上，以保持该表的有序性。答：voidInsert_SqList(SqListva,intx)/*把x插入递增有序表va中*/{inti;if(va.length>MAXSIZE)return;for(i=va.length-1;va.elem[i]>x&&i>=0;i--)va.elem[i+1]=va.elem[i];va.elem[i+1]=x;va.length++;}/*Insert_SqList*/03/02/202334#defineMAXSIZE100typedef

struct{

ElemType*elem;

intlength;}SqList；例题解析【例3】设单链表结点指针域为next，试写出删除链表中指针p所指结点的直接后继的C语言语句。答： q=p->next; p->next=q->next; free(q);03/02/202335例题解析【例4】设单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next，请写出在p结点之前插入s结点的操作。答：

设单链表的头结点的头指针为head,且pre=head；

while(pre->next!=p)pre=pre->next;s->next=p;pre->next=s;03/02/202336例题解析【例5】试编写在带头结点的单链表中删除（一个）最小值结点的算法。voiddelete（Linklist&L）答：[题目分析]本题要求在单链表中删除最小值结点。单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。

voiddelete（LinkedList&L）{∥L是带头结点的单链表p=L->next；∥p为工作指针。指向待处理的结点。假定链表非空。

pre=L；∥pre指向最小值结点的前驱。

q=p；∥q指向最小值结点，初始假定第一元素结点是最小值结点。

while（p->next!=null）{if（p->next->data<q->data）{pre=p；q=p->next；}∥查最小值结点

p=p->next；∥指针后移。

}pre->next=q->next；∥从链表上删除最小值结点

free（q）；∥释放最小值结点空间}∥结束算法delete。03/02/202337例题解析【例6】一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域coef，指数域exp和指针域next；现对链表求一阶导数，链表的头指针为ha，头结点的exp域为–1。

voidderivative(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)________);}}03/02/202338(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表)栈的存储方法栈的顺序存储——顺序栈栈的链式存储——链栈03/02/202339关于栈要求掌握的内容03/02/202340

栈的基本概念：LIFO

栈的存储栈的应用（了解）顺序栈（熟练掌握）链栈（熟练掌握）初始化取栈顶入栈出栈判断栈空

栈初始化取栈顶入栈出栈判断栈空队列定义03/02/202341

队列的定义队列：线性表

(queue)特点：先进先出(FIFO结构)。队尾队头下图是队列的示意图：

a1

a2

…

an出队入队队头队尾当队列中没有元素时称为空队列。表尾称为队尾(rear)表头称为队头(front)插入元素称为入队删除元素称为出队限定在表的一端插入、另一端删除。顺序队列的假溢出问题03/02/202342

在顺序队列中，当尾指针已经指向了队列的最后一个位置即数组上界时，若再有元素入队，就会发生“溢出”。

“假溢出”——队列的存储空间未满，却发生了溢出。rearfrontJ1

J2

J3

J4

rearfrontJ3

J4

(1)、平移元素：把元素平移到队列的首部。效率低。

解决“假溢出”的问题有两种可行的方法：(2)、将新元素插入到第一个位置上，构成循环队列，入队和出队仍按“先进先出”的原则进行。

操作效率、空间利用率高。rearfrontJ3

J4

frontrearJ3

J4

循环队列03/02/202343队空条件:front=rear(初始化时：front=rear)队满条件：front=(rear+1)%N(N=maxsize)队列长度：L=（N＋rear－front）%NJ2J3

J1

J4

J5frontrear

选用空闲单元法：即front和rear之一指向实元素，另一指向空闲元素。

问2：在具有n个单元的循环队列中，队满时共有多少个元素？n-1个5问1：左图中队列长度L=？例题解析【例1】一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？答： 43512不可能实现，主要是其中的12顺序不能实现； 12345的输出可以实现，只需压入一个立即弹出一个即可。03/02/202344例题解析【例2】如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？答： 435612中到了12顺序不能实现； 135426可以实现。03/02/202345例题解析【例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种可能性。03/02/202346例题解析【例4】简述顺序存储队列的假溢出的避免方法及队列满和空的条件。答：设顺序存储队列用一维数组q[m]表示，其中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则为队满。03/02/202347第四讲串和数组【例1】填空题：1.空格串是指_____________，其长度等于_____________。【答案】（1）由空格字符（ASCII值32）所组成的字符串（2）空格个数2．组成串的数据元素只能是_____________。【答案】字符【解析】串是一种特殊的线性表，其特殊性在于串中的元素只能是字符型数据。3．两个字符串相等的充分必要条件是_____________。【答案】两串的长度相等且两串中对应位置上的字符也相等。4．一个字符串中_____________称为该串的子串。【答案】任意个连续的字符组成的子序列03/02/202348例题解析【例2】设计一个算法，将字符串s的全部字符复制到字符串t中，不能利用strcpy函数。答：【算法分析】要实现两个字符串的复制，实质为两个字符数组之间的复制，在复制时，一个字符一个字符的复制，直到遇到'\0'，'\0'一同复制过去，'\0'之后的字符不复制。【算法源代码】voidcopy(chars[],chart[]){inti;for(i=0;s[i]!='\0';i++)t[i]=s[i];t[i]=s[i];}03/02/202349例题解析【例3】设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？答：设数组元素A[i][j]存放在起始地址为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.03/02/202350例题解析【例4】设有一个nn的对称矩阵A，为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，称之为对称矩阵A的压缩存储方式。试问：（1）存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？（2）若在一维数组B中从0号位置开始存放，则对称矩阵中的任一元素aij在只存下三角部分的情形下应存于一维数组的什么下标位置？给出计算公式。答：（1）数组B共有1＋2+3++n=（n+1）*n/2个元素。（2）只存下三角部分时，若ij，则数组元素A[i][j]前面有i-1行（1i-1，第0行第0列不算），第1行有1个元素，第2行有2个元素，，第i-1行有i-1个元素。在第i行中，第j号元素排在第j个元素位置，因此，数组元素A[i][j]在数组B中的存放位置为：1+2++（i-1）+j=（i-1）*i/2+j若i<j，数组元素A[i][j]在数组B中没有存放，可以找它的对称元素A[j][i]。在数组B的第（j-1）*j/2+i位置中找到。如果第0行第0列也计入，数组B从0号位置开始存放，则数组元素A[i][j]在数组B中的存放位置可以改为：当ij时，=i*（i+1）/2+j；当i<j时，=j*（j+1）/2+i。03/02/202351第五讲树03/02/202352二叉树的定义定义：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构：一对二（1：2）

基本特征:每个结点最多只有两棵子树（不存在度大于2的结点）；左子树和右子树次序不能颠倒（有序树）。满二叉树完全二叉树二叉树的性质（能证明吗）03/02/202353【性质1】在二叉树的第i

层上至多有2i-1个结点(i≥1)。【性质2】深度为k的二叉树至多有2k

-1个结点（k≥1）。【性质3】对任何一棵二叉树T，如果其叶子数为n0，度为2的结点数为n2，则n0=n2+1。（叶子数＝结点的度为2的结点数＋1）【性质4】具有n

个结点的完全二叉树的深度为

log2n+1或者log2(n+1)。【性质5】n个结点的完全二叉树，结点按层次编号有：

1)i的双亲是，如果i=1时为根（无双亲）；

2)i的左孩子是2i，如果2i>n，则无左孩子；

3)i的右孩子是2i+1，如果2i+1>n则无右孩子。例题解析1．深度为H的完全二叉树至少有_____________个结点；至多有_____________个结点；H和结点总数N之间的关系是_____________。【答案】（1）2H-1 （2）2H-1 （3）H=log2N+12．一棵有n个结点的满二叉树有_____________个度为1的结点，有_____________个分支（非终端）结点和_____________个叶子，该满二叉树的深度为_____________。【答案】（1）0 （2）(n-1）/2 （3）(n+1）/2 （4）log2n

+13．对于一个具有n个结点的二叉树，当它为一棵_____________时，具有最小高度，当它为一棵_____________时，具有最大高度。【答案】（1）完全二叉树 （2）单支树，树中任一结点（除最后一个结点是叶子外），只有左子女或只有右子女。4．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_____________。【答案】99【解析】在二叉树中，N0=N2+1，所以，有50个叶子结点的二叉树，有49个度为2的结点。若要使该二叉树的结点数最少，度为1的结点应为0个，即总结点数N=N0+N1+N2=99。03/02/202354二叉树的存储（一）03/02/202355二叉树存储方法有顺序存储和链式存储二叉树顺序存储结构完全二叉树：用一组地址连续的存储单元依次自上而下、自左至右存储结点元素，即将编号为i

的结点元素存储在一维数组中下标为

i

的分量中（不用下标为0存储单元）。此顺序存储结构仅适用于完全二叉树不是完全二叉树怎么办？一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。缺点：①浪费空间；②插入、删除不便二叉树的存储（二）03/02/202356二叉树链式存储结构

存储方式

一般从根结点开始存储，用二叉链表来表示。（相应地，访问树中结点时也只能从根开始）

二叉树结点的特点二叉树是非线性结构，适合用链式存储结构lchilddatarchild结点结构datarchildlchilddata

parentlchildrchild二叉树结点数据类型定义：typedefstruct

BiTNode{

TElemTypedata; structBiTNode

*lchild,*rchild;}BiTNode,*BiTree;二叉树遍历03/02/202357若规定先左后右，则只有前三种情况：DLR——

前（根）序遍历，LDR——

中（根）序遍历，LRD——

后（根）序遍历根据遍历顺序确定一棵二叉树已知二叉树的前序序列和中序序列，可以唯一确定一棵二叉树。已知二叉树的后序序列和中序序列，可以唯一确定一棵二叉树。已知二叉树的前序序列和后序序列，不能唯一确定一棵二叉树。例题解析03/02/202358

设二叉树bt的一种存储结构如下：00237580101jhfdbacegi000940000012345678910lchilddatarchild

其中bt为树根结点指针,lchild、rchild分别为结点的左、右孩子指针域,在这里使用结点编号作为指针域值,0表示指针域为空;data为结点的数据域。请完成下列各题：(1)画出二叉树的树形表示；(2)写出按先序、中序和后序遍历二叉树bt所得到的结点序列；例题解析（续）03/02/20235900237580101jhfdbacegi000940000012345678910lchilddatarchild(1)画出二叉树的树形表示；因为第6号结点不是任何结点的孩子结点，该结点必定是根结点，再根据和结点左、右指针域的值很容易得到该二叉树的树形表示为

abgfdcehij例题解析（续）03/02/20236000237580101jhfdbacegi000940000012345678910lchilddatarchildabgfdcehij(2)写出按先序、中序和后序遍历二叉树bt所得到的结点序列；a.先序序列abcedfhgij例题解析（续）03/02/20236100237580101jhfdbacegi000940000012345678910lchilddatarchildabgfdcehij(2)写出按先序、中序和后序遍历二叉树bt所得到的结点序列；a.先序序列abcedfhgijb.中序序列ecbhfdjiga例题解析（续）03/02/20236200237580101jhfdbacegi000940000012345678910lchilddatarchildabgfdcehij(2)写出按先序、中序和后序遍历二叉树bt所得到的结点序列；a.先序序列abcedfhgijb.中序序列ecbhfdjigab.后序序列echfjigdba树与森林【例题】从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。答：树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树惟一表示，并可使用二叉树的一些算法去解决树和森林中的问题。树和二叉树的区别有3：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分支的情况下，也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。03/02/202363例题解析【例题】已知一棵二叉树的中序序列和后序序列分别为GLDHBEIACJFK和LGHDIEBJKFCA（1）给出这棵二叉树；（2）转换为对应的森林。答：03/02/202364ACBHJDFGKLEIEABLDGHIJFCK例题解析【例题】假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为ABECFGDHI,中序序列为BCDAFEHIG。请画出该二叉树，并将其转换为对应的森林。答：按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列分成左右两部分：左子树和右子树。若左子树不空，层次序列中第二个结点为左子树的根；若右子树为空，则层次序列中第三个结点为右子树的根。对右子树也作类似的分析。层次序列的特点是，从左到右每个结点或是当前情况下子树的根或是叶子。03/02/202365IADEBFCGHECABDIGHF二叉树的应用：Huffman树03/02/202366Huffman树的应用带权路径计算WPL带权路径长度WPL最小的二叉树称作赫夫曼树具有相同带权结点的哈夫曼树不惟一满二叉树不一定是哈夫曼树哈夫曼树的结点的度数为0或2，没有度为1的结点。包含

n个叶子结点的哈夫曼树中共有2n–1个结点。Huffman树的构造过程给定权值集w={2,3,4,7,8,9},试构造关于w的的一颗哈夫曼树，并求其带权路径长度WPL。03/02/2023672347894789235789235499235497815Huffman树的构造过程03/02/202368给定权值集w={2,3,4,7,8,9},试构造关于w的的一颗哈夫曼树，并求其带权路径长度WPL。78159235491878159235491833WPL=(2+3)×4+4×3+9×2+(7+8)×2=80【例题】T={(a,2),(b,3),(c,4),(d,7),(e,9)}为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度WPL、T中每个字符的哈曼夫编码和哈夫曼编码的平均长度。23479Huffman编码过程T={(a,2),(b,3),(c,4),(d,7),(e,9)}为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度WPL、T中每个字符的哈曼夫编码和哈夫曼编码的平均长度。23479235T={(a,2),(b,3),(c,4),(d,7),(e,9)}