第10课数据结构

1、第8章 数据结构根据考试大纲的要求，在数据结构与算法方面，要求考生掌握以下知识点1、常用数据结构 数组(静态数组、动态数组)、线性表、链表(单向链表、双向链表、循环链表)、队列、栈、树(二叉树、查找树)、图等的定义、存储和操作。2、常用算法排序算法、查找算法、数值计算算法、字符串处理算法、数据压缩算法、递归算法、图的相关得法。算法与数据结构的关系，算法效率、算法描述(流程图、伪代码、决策表)、算法的复杂性。通过本章的学习，要求掌握如下内容：理解各种线性数据结构的定义，掌握线性结构中的基本运算及实现理解数组和矩阵元素的存储方式理解树的特点，掌握树结构中的基本运算入实现了解图的特点、存储结构、遍历

2、及各种应用掌握顺序查找和二分查找方法掌握二叉排序树的构造方法和查找方法了解哈希表的构造方法和查找过程了解各种查找方法的查找性能掌握简单排序方法和快速排序方法，理解堆排序、归并排序和基数排序等排序方法第8章 数据结构1、数据结构就是指数据元素的集合（或数据对象）以及它们之间相互关系数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(Data Object)：

3、是性质相同的数据元素的集合。是数据的一个子集。数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。2、数据结构在计算机中有两种不同的表示方法： 顺序表示和非顺序表示由此得出两种不同的存储结构：顺序存储结构和链式存储结构顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。第8章 数据结构算法：是对特定问题求解步骤的一种描述 算法是指令的有限序列，其中每一条指令表示一个或多个操作。 算法具有以下五个特性：（1）有穷性 一个算法必须总是在执行有穷

4、步之后结束，且每一步都在有穷时间内完成。（2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。（3）可行性 （有效性） 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。第8章 数据结构4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。算法设计的要求评价一个好的算法有以下几个标准:(1) 正确性(Correctness ) 算法应满足具体问题的需求。(2)可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解。

5、 (3)健状性(Robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。第8章 数据结构(4)效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。算法效率的度量 对一个算法要作出全面的分析可分成两用人才个阶段进行，即事前估计和后期测试事前估计 求出该算法的一个时间界限函数后期测试 收集此算法的执行时间和实际占用空间的统计资料。定义：如果存在两个正常数c和n0，对于所有的nn0，有f(n) cg(n) 则记作 f(n)=O(g(n)一般情况下，算法中基本操作重复执行的次数

6、是问题规模n的某个函数，算法的时间量度记作 T(n)=O(f(n)称作算法的渐近时间复杂度。第8章 数据结构例、for(I=1，I=n;+I) for(j=1;j=n;+j) cIj=0; for(k=1;k=n;+k) cIj+=aIk*bkj; 由于是一个三重循环，每个循环从1到n，则总次数为: nnn=n3时间复杂度为T(n)=O(n3)频度：是指该语句重复执行的次数例 +x;s=0;将x自增看成是基本操作，则语句频度为，即时间复杂度为(1)如果将s=0也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶。例、for(I=1;I=n;+I) +x;s+=x; 语句频度为：2n

7、其时间复杂度为：O(n) 即时间复杂度为线性阶。第8章 数据结构以下六种计算算法时间的多项式是最常用的。其关系为： O(1)O(logn)O(n)O(nlogn) O(n2)O(n3)指数时间的关系为： O(2n)O(n!)0)记作： (a1，a2，an) 这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1；其余的内部结点ai(2in-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。 线性表是一种典

8、型的线性结构。8.1 线性结构把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。 假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第I+1个数据元素的存储位置LOC( a i+1)和第i个数据元素的存储位置LOC(a I )之间满足下列关系： LOC(a i+1)=LOC(a i)+l 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(I-1)*l8.1 线性结构现在分析算法的复杂度。 这里的问题规模是表的长度，设它的值为。该算法的时间主要化费在循环的结点后移语句上，该

9、语句的执行次数（即移动结点的次数）是。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。当时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；当=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，8.1 线性结构其时间复杂度为O（n）。 由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度 在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为n-I+1。故 Eis(n)= pi(n-I+1) 不失一般性，假设在表中任何位

10、置(1in+1)上插入结点的机会是均等的，则 p1=p2=p3=p n+1=1/(n+1) 因此，在等概率插入的情况下， Eis(n)= (n-I+1)/(n+1)=n/2在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n)8.1 线性结构线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结点.为避免大量结点的移动，我们介绍线性表的另一种存储方式，链式存储结构，简称为链表(Linked List)。链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续

11、的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：8.1 线性结构线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结点.为避免大量结点的移动，我们介绍线性表的另一种存储方式，链式存储结构，简称为链表(Linked List)。链表是指用一组任意的存储单元来

12、依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构： 其中：data域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（Single

13、Linked)。 显然，单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于 终端结点无后继，故终端结点的指针域为空，即null（图示中也可用表示)。 datalink8.1 线性结构8.1 线性结构2、栈和队列栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。 假设栈S=(a1，a2，a3，an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈

14、的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。8.1 线性结构由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。8.1 线性结构设S是栈类型的指针变量。若栈底位置在向量的低端，即sdata0是栈底元素，那么栈顶指针stop是正向增加

15、的，即进栈时需将stop加1，退栈时需将stop 减1。因此，stoptop =stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。8.1 线性结构栈的链式存储结构称为链栈，它是运算是受限的单链表，克插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。8.1 线性结构队列(Queue)也是一种运算受

16、限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an ，也就是说队列的修改是依先进先出的原则进行的。8.1 线性结构队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许

17、删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an ，也就是说队列的修改是依先进先出的原则进行的。 队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而

18、要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值地队列初始化时均应置为。入队时将新元素插入所指的位置，然后将加。出队时，删去所指的元素，然后将加并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。 0 1 2 3FrontrearabcFront rear (a)队列初始为空（b）A,B,C入队 b c front rear front rear（c) a出队 (d) b,c出队，队为空和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小

19、，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为： if(I+1=QueueSize) i=0; else i+; 利用模

20、运算可简化为： i=(i+1)%QueueSize 显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。 如图所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。 解决此问题的方法至少有三种： 其一是另设一个布尔变量以匹别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；其三是使用一个计数器记录

21、队列中元素的总数（实际上是队列长度）。下面我们用第三种方法实现循环队列上的六种基本操作，为此先给出循环队列的类型定义。1、数组的定义 数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组： a11 a12 a1n a21 a22 a2n am1 am2 amn Amn=8.2 数组和矩阵 可以看成是由个行向量组成的向量，也可以看成是个列向量组成的向量。数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一维内存

22、来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。 通常有两种顺序存储方式：行优先顺序将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为： a11,a12,a1n,a21,a22,a2n,am1,am2,amn 在PASCAL、C语言中，数组就是按行优先顺序存储的。列优先顺序将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元

23、素按列优先顺序存储的线性序列为：a11,a21,am1,a12,a22,am2,an1,an2,anm在FORTRAN语言中，数组就是按列优先顺序存储的。 以上规则可以推广到多维数组的情况：优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。 按上述两种方式顺序存储的序组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。例如，二维数组Amn按“行优先顺序

24、”存储在内存中，假设每个元素占用d个存储单元。 元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行、第j列，前面i-1行一共有(i-1) n个元素，第i行上aij前面又有j-1个元素，故它前面一共有(i-1) n+j-1个元素，因此，aij的地址计算函数为： LOC(aij)=LOC(a11)+(i-1)*n+j-1*d同样，三维数组Aijk按“行优先顺序”存储，其地址计算函数为：LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p+(k-1)*d 上述讨论均是假设数组各维的下界是不是1，更一般的二维数组是Ac1.d1,c2.

25、d2，这里c1,c2不一定是1。aij前一共有i-c1行，二维数组一共有d2-c2+1列，故这i-c1行共有(i-c1)*(d2-c2+1)个元素，第i行上aij前一共有j-c2个元素，因此，aij的地址计算函数为： LOC(aij)=LOC(ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d 例如，在C语言中，数组各维下标的下界是0，因此在C语言中，二维数组的地址计算公式为： LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d 2、矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维

26、数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间， 我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0i,jn-1则称A为对称矩阵。如图5

27、.1便是一个5阶对称矩阵。 对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示： 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a22 3 0 2 5 1 . 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1 在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为： (i+1)=n(n+1)/2 因此，我们可以按图中箭头所指的次

28、序将这些元素存放在一个向量sa0.n(n+1)/2-1中。为了便于访问对称矩阵A中的元素，我们必须在aij和sak 之间找一个对应关系。 若ij，则ai j在下三角形中。 ai j之前的i行（从第0行到第i-1行）一共有1+2+i=i(i+1)/2个元素，在第i行上， ai j之前恰有j个元素（即ai0,ai1,ai2,aij-1），因此有： k=i*(i+1)/2+j 0kn(n+1)/2 若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j*(j+1)/2+i 0 kn(n+1)/2 令 I=max(i,j)， J=min(i,j)，

29、则k和 i, j的对应关系可统一为： k=I*(I+1)/2+J 0 kn(n+1)/2 因此，aij的地址可用下列式计算： LOC(aij)=LOC(sak) =LOC(sa0)+k*d=LOC(sa0+I*(I+1)/2+J*d 有了上述的下标交换关系，对于任意给定一组下标(i，j)，均可在sak中找到矩阵元素aij，反之，对所有的k=0,1,2,n(n-1)/2-1，都能确定sak中的元素在矩阵中的位置(i,j)。由此，称san(n+1)/2为阶对称矩阵A的压缩存储，见下图：k=0 1 2 3 n(n-1)/2 n(n-1)/2-1例如a21和a12均存储在 sa4中，这是因为 k=I*

30、(I+1)/2+J=2*(2+1)/2+1=4a00a10a11a20an-1 0 an-1,n-12、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。 a00 a01 a 0 n-1 a00 c c c a11 a 1 n-1 a10 a11 c . . c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩阵 (b)下三角矩阵 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1

31、)/2个，因此，三角矩阵可压缩存储到向量sa0.n(n+1)/2中，其中c存放在向量的最后一个分量中， 上三角矩阵中，主对角线之上的第p行(0pjk= 下三角矩阵的存储和对称矩阵类似，sak和aij对应关系是： i(i+1)/2+j ij n(n+1)/2 ij 3、对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵， a00 a01 a10 a11 a12 a21 a22 a23 . . . 对角矩阵 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-

32、2 an-1 n-1k=非零元素仅出现在主对角(aii,0in-1上，紧邻主对角线上面的那条对角线上(aii+1,0in-2)和紧邻主对角线下面的那条对角线上(ai+1 i,0in-2)。显然，当 i-j 1时，元素aij=0。由此可知，一个k对角矩阵(k为奇数)A是满足下述条件的矩阵：若 i-j (k-1)/2 ，则元素 aij=0。 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。 在三对角矩阵里附满足条件i=0，j=0、1，或i=n-1j=n-2、n-1或1i=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：

33、(1)有且仅有一个特定的称为根(Root)的结点； (2)其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。8.3 树二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树 相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。二叉树的定义定义：二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。 这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二查树不是树的特殊情况，它们是

34、两个概念。二叉树二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。图6.8列出二差树的5种基本形态，图6.8(C) 和图6.8（d）是不同的两棵二叉树。 (a)空二叉树AABABACB (b)根和空的左右子树 (c)根和左子树(d)根和右子树 (e)根和左右子树二叉树的5种形式二叉树的性质二叉树具有下列重要性质：性质1： 在二叉树的第i层上至多有2i-1个结点(i=1)。 采用归纳法证明此性质。 当i=1时，只有一个根结点，2i-1=20 =1,命题成立。 现在假定多所有的j，1=j=1).深度为k的二叉树的最大的结点

35、时为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数，： EkI=1（第i层上的最大结点数）= EkI=12i-1=2k 1 性质3： 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0n21。设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：Nn0n1n2 (8-1)再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数， 则有：NB1。由于这些分支都是由度为1和2的结点射出的，所有有： Bn1+2*n2 NB1n12n21 （82)由式（81）和（82）得到： n0+n1+n2=

36、n1+2*n2+1 n0n21下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。 一棵深度为k且由2k-1个结点的二叉树称为满二叉树。下图就是一棵满二叉树，对结点进行了顺序编号。如果深度为k、由n个结点的二叉树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，2453671图 满二叉树12345612345712367(a)完全二叉树(b)非完全二叉树( c)非完全二叉树图完全二叉树则称这样的二叉树为完全二叉树，图（b）、c）是2棵非完全二叉树。满二叉树是完全二叉树的特例。完全二叉树的特点是：（1)所有的叶结点都出现在第k层或k1层。 （2）任一结点，如果其右子树的最大层次

37、为1，则其左子树的最大层次为1或l1。 性质4：具有n个结点的完全二叉树的深度为log2n1。符号【x】表示不大于x的最大整数。 假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-11n=2k-1 或 2k-1=n2k取对数得到：k1log2nk 因为k是整数。所以有：k【log2n】1。性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第【log2n】+1层，每层从左到右),则对任一结点i（1=i1，则其双亲是结点【i/2】。 （2）如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。 （3）如果2i1n，则结点i无右孩子；否则，其右孩子是

38、结点2i1。i/2ii+12i2i+12(i+1)2i+3ii+12(i+1)2i+3i2i2i+1图 完全二叉树中结点i和i+1(a)I和i+1结点在同一层 (b)I和i+1结点不在同一层如图所示为完全二叉树上结点及其左右好在结点之间的关系。 在此过程中，可以从（2）和（3）推出（1），所以先证明（2）和（3）。 对于i1，由完全二叉树的定义，其左孩子是结点2，若2n，即不存在结点2，此是，结点i无孩子。结点i的由孩子也只能是结点3，若结点3不存在，即3n，此时结点i无右孩子。对于i1，可分为两种情况： （1）设第j（1=jn，则无左孩子：其右孩子必定为第j1层的第二个结点，编号为2i1。若

39、2i+1n，则无右孩子。 （2）假设第j（1=j=log2n)层上的某个结点编号为i（2e(j-1)=i=2ej-1),且2i11时，如果i为左孩子，即2（i/2)=i,则i/2是i的双亲；如果i为右孩子，i2p+1,i的双亲应为p，p（i1）/2=i/2. 证毕。二叉树的存储结构1.顺序存储结构 它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法： #define max-tree-size 100Typedef telemtype sqbitreemax-tree-size;S

40、qbitree bt 从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树确需要2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！ ABCDEFGHIJKL 1 2 3 4 5 6 7 8 9 10 11 12完全二叉树abcdefghijklABCDEFG 表示该处没有元素存在仅仅为了好理解ABCDEFG一般二叉树（2）二叉链表法 存储二叉树经常用二叉链表法 ABCDEFGHlchildDatarchild二叉树的二叉链表存储表示Typedef struct BiTNo

41、de TelemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;有时也可用数组的下标来模拟指针,即开辟三个一维数组Data ,lchild,rchild 分别存储结点的元素及其左,右指针域; 遍历二叉树在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从

42、而便于遍历。bca(根结点)(右子树)(左子树)由二叉树的递归定义，二叉树的三个基本组成单元是：根结点、左子树和右子树。假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为： DLR先（根）序遍历， LDR中（根）序遍历， LRD后（根）序遍历。1、先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。2、中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（

43、3）中序遍历右子树。3、后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。例如图（1）所示的二叉树表达式(a+b*(c-d)-e/f)若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为：-+a*b-cd/ef按中序遍历,其中序序列为：a+b*c-d-e/f按后序遍历,其后序序列为：abcd-*+ef/-人们喜欢中缀形式的算术表达式,对于计算机,使用后缀易于求值 图 （1）*a/b-dcfe线索二叉树： 当以二叉链表作为存储结构时,只能找到结点的左右孩子的信息,而不能在结点的任一序列的前驱与后继信息,这种信息只

44、有在遍历的动态过程中才能得到,为了能保存所需的信息,可增加标志域;其中: 0 lchild 域指示结点的左孩子 ltag= 1 lchild 域指示结点的前驱 0 rchild 域指示结点的右孩子 rtag= 1 rchild 域指示结点的后驱 以这种结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱与后继的指针叫做线索.加上线索的二叉树称之为线索二叉树lchildltagdatartagrchild赫夫曼树赫夫曼树 Huffman (最优二叉树最优二叉树)基本概念基本概念:从树中一个结点到另一个结点之间的分支构成这两个结点之间的从树中一个结点到另一个结点之间的分支构成这两

45、个结点之间的路径路径。 路径上的分支数目称做路径上的分支数目称做路径长度路径长度。 XYZX 到到 Y 的路径的路径路径长度为路径长度为 2X 到到 Z 的路径的路径树的路径长度树的路径长度是从树根到是从树根到每一个每一个结点的路径长度之结点的路径长度之和和。 在具有相同结点数的所有二叉树中，在具有相同结点数的所有二叉树中， 的路径长度是最短的。的路径长度是最短的。完全二叉树完全二叉树推广，为结点加权推广，为结点加权 w 。735ABCDE结点的带权路径长度结点的带权路径长度为从根结点到该结点之间的路径长度与结点上为从根结点到该结点之间的路径长度与结点上权值的乘积。权值的乘积。树的带权路径长度

46、树的带权路径长度为树中所有为树中所有叶子结点叶子结点的带权路径长度之和，通常的带权路径长度之和，通常记做记做 WPL = wk L(vk ) nk=1wk 为叶子结点为叶子结点 vk 的权值的权值L(vk )为叶子结点为叶子结点 vk 的路径长度的路径长度例，例，3 棵二叉树，都有棵二叉树，都有 4 个叶子结点个叶子结点 a、b、c、d，分别带权，分别带权7、5、2、4，求它们各自的带权路径长度。，求它们各自的带权路径长度。abcd7524(1)abdc7542(2)cdba2457(3)(1) WPL = 72 + 52 + 22 + 42 = 36(2) WPL = 73 + 53 + 2

47、1 + 42 = 46(3) WPL = 71 + 52 + 23 + 43 = 35假设有假设有n个权值个权值 w1,w2, wn ，试构造一棵有，试构造一棵有n个叶子结点个叶子结点的二的二叉树，每个叶子结点带权为叉树，每个叶子结点带权为 wi ，则其中带权路径长度则其中带权路径长度WPL最小最小的二叉树称做的二叉树称做最优二叉树最优二叉树或或赫夫曼树赫夫曼树。 如何构造如何构造赫夫曼树？赫夫曼树？(1) 根据给定的根据给定的 n 个权值个权值 w1,w2, wn 构成构成 n 棵二叉树的集合棵二叉树的集合 F = T1,T2, Tn，其中每棵二叉树，其中每棵二叉树 Ti 中只有一个权值为中

48、只有一个权值为 wi 的的根结点根结点。(2) 在在 F 中选取两棵根结点中选取两棵根结点权值最小权值最小的树作为左、右子树构造一棵的树作为左、右子树构造一棵新的二叉树，且置新二叉树的根结点的权值为其左、右子树根结点新的二叉树，且置新二叉树的根结点的权值为其左、右子树根结点的权值之和。的权值之和。(3) 在在 F 中删除这两棵树，同时将新得到的二叉树加入集合中删除这两棵树，同时将新得到的二叉树加入集合 F 中。中。(4) 重复重复 (2) 和和 (3) ，直到，直到 F 中只含一棵树为止。中只含一棵树为止。例，例， 4 个叶子结点个叶子结点 a、b、c、d，分别带权，分别带权7、5、2、4。c

49、d24b5a7初始初始cd246b5cd24611a7b5cd2461118赫夫曼编码赫夫曼编码1. 编码编码例，例，传送传送 ABACCD，四种字符，可以分别编码为，四种字符，可以分别编码为 00,01,10,11。则原电文转换为则原电文转换为 00 01 00 10 10 11。对方接收后，采用二位一分进行译码。对方接收后，采用二位一分进行译码。电文电文编码编码二进制二进制二进制二进制译码译码电文电文当然，为电文编码时，总是希望总长越短越好，当然，为电文编码时，总是希望总长越短越好，如果对每个字符设计长度不等的编码，且让电文中出现次数较多如果对每个字符设计长度不等的编码，且让电文中出现次数

50、较多的字符采用较短的编码，则可以减短电文的总长。的字符采用较短的编码，则可以减短电文的总长。例，例，对对 ABACCD 重新编码，分别编码为重新编码，分别编码为 0 , 00 , 1 , 01。A B C D则原电文转换为则原电文转换为 0 00 0 1 1 01。 减短了。减短了。问题问题: 如何译码？如何译码？前四个二进制字符就可以多种译法。前四个二进制字符就可以多种译法。AAAABB2. 前缀编码前缀编码若设计的长短不等的编码，满足任一个编码都不是另一个编码的若设计的长短不等的编码，满足任一个编码都不是另一个编码的前缀，则这样的编码称为前缀，则这样的编码称为前缀编码前缀编码。例，例， A

51、 , B , C , D 前缀编码可以为前缀编码可以为 0 , 110 , 10 , 111利用利用二叉树二叉树设计二进制前缀编码。设计二进制前缀编码。叶子结点表示叶子结点表示 A , B , C , D 这这 4 个字符个字符ACBD000111左分支表示左分支表示 0，右分支表示，右分支表示 1从根结点到叶子结点的路径上经过的二从根结点到叶子结点的路径上经过的二进制符号串作为该叶子结点字符的编码进制符号串作为该叶子结点字符的编码A(0)B(110)C(10)D(111)证明其必为前缀编码证明其必为前缀编码路径长度为编码长度路径长度为编码长度如何得到最短的二进制前缀编码？如何得到最短的二进制

52、前缀编码？3. 赫夫曼编码赫夫曼编码设每种字符在电文中出现的概率设每种字符在电文中出现的概率 wi 为，则依此为，则依此 n 个字符出现的概个字符出现的概率做权，可以设计一棵赫夫曼树，使率做权，可以设计一棵赫夫曼树，使WPL = wi li 最小最小ni=1wi 为叶子结点的出现概率为叶子结点的出现概率 ( 权权)li 为根结点到叶子结点的路径长度为根结点到叶子结点的路径长度例，某通信可能出现例，某通信可能出现 A B C D E F G H 8 个字符，其概率分别为个字符，其概率分别为 0.05 , 0.29 , 0.07 , 0.08 , 0.14 , 0.23 , 0.03 , 0.11

53、 ，试设计赫夫曼编码，试设计赫夫曼编码不妨设不妨设 w = 5 , 29 , 7 , 8 , 14 , 23 , 3 , 11 排序后排序后 w = 3 , 5 , 7 , 8 , 11 , 14 , 23 , 29 7 , 8 , 8 , 11 , 14 , 23 , 29 8 , 11 , 14 , 15 , 23 , 29 14 , 15 , 19 , 23 , 29 19 , 23 , 29 , 29 29 , 29 , 42 42 , 58 100 100 01100110101010A (0110)B (10)C (1110)D (1111)E (110)F (00)G (0111

54、)H (010)AG8537815CD1119H1429E F4223 B5829ACEA 编码为编码为 0110 1110 110 0110如何译码？如何译码？1. 从根结点出发，从左至右扫描编码，从根结点出发，从左至右扫描编码，2. 若为若为 0 则走左分支，若为则走左分支，若为1 则走右分支，直至叶结点为止，则走右分支，直至叶结点为止，3. 取叶结点字符为译码结果，返回重复执行取叶结点字符为译码结果，返回重复执行 1,2,3 直至全部译完为止直至全部译完为止10001100110101010A (0110)B (10)C (1110)D (1111)E (110)F (00)G (011

55、1)H (010)AG8537815CD1119H1429E F4223 B5829ACEA1. 二叉分类树二叉分类树(二叉排序树二叉排序树)二叉分类树或者是一棵空树；或者是具有下列性质的二叉树：二叉分类树或者是一棵空树；或者是具有下列性质的二叉树： (1) 左子树上所有结点的值均左子树上所有结点的值均小于等于小于等于它的根结点的值；它的根结点的值； (2) 右子树上所有结点的值均右子树上所有结点的值均大于大于它的根结点的值；它的根结点的值； (3) 根结点的左、右子树也分别为二叉分类树。根结点的左、右子树也分别为二叉分类树。 13 8523 1837如何插入新结点如何插入新结点 9 ?99右

56、儿子右儿子为空为空 9 13 8523 1837利用插入操作可以构造一棵二叉分类树利用插入操作可以构造一棵二叉分类树首先给出结点序列首先给出结点序列:13、8、23、5、18、37 13537 18 8238 235518183737分类二叉树的应用分类二叉树的应用:快速、方便查找某个结点快速、方便查找某个结点树和森林树和森林RBACDEFHGKRBACDEFHGKRADBECFGHK性质性质:1. 树可以表示成二叉树的形式树可以表示成二叉树的形式启示启示: 树与二叉树的转换树与二叉树的转换2. 树转换成一棵只有树转换成一棵只有左子树左子树的二叉树的二叉树6.4.2 森林与二叉树的转换森林与二

57、叉树的转换 ACBDEFGHIJ(1). 任何一棵树都可以转换为一棵任何一棵树都可以转换为一棵没有左子树没有左子树的二叉树。的二叉树。(2). 森林是由若干棵树构成的集合，若把森林中森林是由若干棵树构成的集合，若把森林中前一棵树前一棵树的根的根结点看成是结点看成是后一棵树后一棵树的根结点的根结点兄弟兄弟，就可以导出森林与二叉树，就可以导出森林与二叉树的转换。的转换。1. 森林转换成二叉树森林转换成二叉树(1) 增加增加一个根结点，作为原森一个根结点，作为原森林中各树根结点的林中各树根结点的父结点父结点。(2) 将将新树新树转换成二叉树。转换成二叉树。(3) 删除删除二叉树的根结点。二叉树的根结

58、点。ACBDEFGHIJRBECDFGHIJRA8.4 图图图是一种较线性表和树更为复杂的数据结构图是一种较线性表和树更为复杂的数据结构。线性表线性表: 线性结构线性结构树树: 层次结构层次结构图图: 结点之间的关系可以是任意的，即图中任意两个结点之间的关系可以是任意的，即图中任意两个数据元素之间都可能相关。数据元素之间都可能相关。 ABCDE图图 G 是由两个集合顶点集是由两个集合顶点集 V(G) 和边集和边集 E(G) 组成的，记作组成的，记作G=( V(G)，E(G) )，简称，简称G=(V，E)。ABCDEABCDEABCDEV是顶点的有穷是顶点的有穷非空非空集合集合 E是两个顶点之间

59、的关系，即边的有穷集合是两个顶点之间的关系，即边的有穷集合 无向图和有向图无向图和有向图 无向图无向图: 边是顶点的无序对，即边没有方向性。边是顶点的无序对，即边没有方向性。v1v2v3v5v4V = v1 , v2 , v3 , v4 , v5 E = ( v1 , v2 ) , ( v1 , v4 ) , ( v2 , v3 ) , ( v2 , v5 ) , ( v3 , v4 ) , ( v3 , v5 ) ( v1 , v2 )表示顶点表示顶点 v1 和和 v2 之间的边，之间的边， ( v1 , v2 ) = ( v2 , v1 )。有向图有向图: 其边是顶点的有序对，即边有方向性

60、。其边是顶点的有序对，即边有方向性。v1v2v4v3V = v1 , v2 , v3 , v4 E = , , , 通常边称为通常边称为弧弧，表示顶点表示顶点 v1 到到 v2 的弧。的弧。称称 v1 为弧尾，称为弧尾，称 v2 为弧头。为弧头。 带权无向图带权无向图(无向网无向网) 和和 带权有向图带权有向图(有向网有向网)有时对图的边或弧赋予相关的数值，这种与图的边或弧相有时对图的边或弧赋予相关的数值，这种与图的边或弧相关的数值叫做关的数值叫做权权。 这种带权的图通常称为这种带权的图通常称为网网。 带权的有向图称为带权的有向图称为有向网有向网。带权的无向图称为带权的无向图称为无向网无向网。