《数据结构与算法分析》全册配套课件4.ppt

1、数据结构与算法分析数据结构与算法分析全册全册配套课件配套课件4 42Data Structures and Algorithms Analysis数据结构与算法分析数据结构与算法分析3& 第一章第一章 绪论绪论 1.1 1.1 引言引言 1.2 1.2 数据结构的有关基本概念；数据结构的有关基本概念； 1.3 1.3 算法及算法分析（算法评价）算法及算法分析（算法评价） 4数据结构的发展概况和地位数据结构作为一门独立的课程在国外是从1968年才开始的。数据结构是计算机科学中一门综合性的专业基础课。数学代数系统数据类型算子关系编码理论数据表示法数理的运算数据结构数据存取机器组织文件系统数据组织信

2、息检索软件（计算机程序设计）硬件存储装置（计算机系统设计）5程序 = 算法 + 数据结构 程序是对所要解决问题的各个对象和处理规则的描述，或者说是数据结构和算法的描述（Niklaus Wirth 1984）6课程地位 计算机科学与技术专业本科生的专业基础课计算机科学与技术专业本科生的专业基础课程之一程之一 计算机专业本科生必修的学位课程计算机专业本科生必修的学位课程 计算机专业研究生入学考试必考科目计算机专业研究生入学考试必考科目 计算机软件技术资格和水平考试内容计算机软件技术资格和水平考试内容 全国计算机等级考试（三级、四级）内容全国计算机等级考试（三级、四级）内容7课程地位（续） 为操作系

3、统、数据库系统、编译原理、计算为操作系统、数据库系统、编译原理、计算机网络等后续课程提供了必要的知识基础机网络等后续课程提供了必要的知识基础 为提高程序设计能力、逻辑思维能力和分析为提高程序设计能力、逻辑思维能力和分析问题、解决问题的能力提供了必要的技能训问题、解决问题的能力提供了必要的技能训练练8本课程研究的问题 数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数值性数据 非数值性数据 数值问题 对以数学方式表示的问题求数值解。例如，代数方程计算、矩阵计算、线性方程组求解、数值积分、微分方程求解等； 非数值问题 求非数值解。例

4、如，排序查找、模式匹配等。 数据结构的研究问题：非数值数据之间的结构关系，及如何表示，如何存储，如何处理9 数值问题与非数值问题数值问题与非数值问题1）数值问题）数值问题例例1 已知：游泳池的长已知：游泳池的长len和宽和宽wide，求面积，求面积area设计设计 求解问题的方法求解问题的方法编程编程main ( ) int len, wide ,area ;scanf (“%d %d%n”, &l,&w);area=len*wide ;printf (“area=%d”,area); 建模型：建模型： 问题涉及的对象：游泳池的长问题涉及的对象：游泳池的长len 宽宽wide，面积，面积are

5、a； 对象之间的关系：对象之间的关系：area=len wide10 例3 多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图11学习数据结构的必要性数据结构 是指数据的组织 更有效的程序 计算机功能越强大尝试更复杂的问题（应用） 更复杂的问题需要更大的计算量 工作越复杂就越偏离人们的日常经验12数据的组织对于任意组织的一组数据项能够查找出指定的数据项，将这些数据项处理成任何期望得到的顺序，或者更改任何特定数据项的值。 同一个程序，选择不同的数据结构和算法可能会产生很大的差异，有的可能在几秒钟就运行完毕，也有可能需要几天时间才能完成。13效率Efficien

6、cy一种解决方案如果能在所要求的资源限制（resource constraints）内将问题解决好，则称该算法是有效率的（efficient） 空间Space 时间Time 一种算法的代价（cost）是指这种算法消耗的资源量14数据结构的选择选择数据结构的步骤：1. 分析问题，以确定解决方案会遇到的资源限制2. 确定必须支持的基本操作，并度量每种操作的资源限制3. 选择最适合这些需求的数据结构15考虑的问题 开始时是将所有数据都插入数据结构，还是与其它操作混合在一起插入? 数据是否要删除? 所有数据是按一些定义明确的顺序来处理，还是允许随机访问?16数据结构的原则每个数据结构都将代价与效益联系

7、在一起很少有一个数据结构在所有情况下都比其它算法好一个数据结构需要： 一定的空间存储它的每一个数据项， 一定的时间来执行单个基本操作， 一定的程序设计工作。17数据结构的原则 (cont)每一个问题都有可利用空间和时间的约束只有对问题的特性进行仔细分析之后，才能得到执行这项任务最好的数据结构。一个银行业务的例子： 新开帐户：花费几分钟 交易：几秒钟 注销帐户：整夜18课程的目的1. 加强一个概念：每一个数据结构都有其相关的代价和效益2. 学会常用的数据结构 这些数据结构形成了一个程序员的基本数据结构工具箱3. 了解如何评价一个数据结构或算法的代价（cost） 这些技术也使得程序员能够判断自己或

8、别人发明的新数据结构的价值。19教学目的学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步掌握算法的时间分析和空间分析技术本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范。为今后的程序设计作一些铺垫20& 第一章第一章 绪论绪论 1.1 1.1 引言引言 1.2 1.2 数据结构的有关基本概念数据结构的有关基本概念 1.3 1.3 算法及算法分析（算法评价）算法及算法分析（算法评价） 21术语类型（type）是一组值的集合数据项（data item or element）是一条信息或者

9、一个记录数据类型（data type）是指一种类型和定义在该类型上的一组操作数据项又称为数据类型的成员简单数据项不包含子结构复杂数据项可能包含多项信息22抽象数据类型抽象数据类型（ADT）：根据一组值的集合定义的数据类型和该数据类型上的一组操作集每个ADT操作由它的输入和输出定义。封装：隐藏实现细节23数据结构 数据结构是ADT的实际实现 与ADT联系在一起的每个操作由一个或多个子程序来实现 数据结构通常涉及数据在内存中的组织方式 文件结构是指在外存储器（如磁盘驱动器）上数据的组织24抽象化ADT：复杂问题的抽象化：隐喻 标志的层次化Ex: 晶体管 门电路 CPU.ADT在程序中通过特定的数据

10、结构实现，然而在设计使用ADT的那部分程序时，我们只关心数据类型上的操作，而不关心数据结构的实现25逻辑 vs. 物理形式数据项有逻辑形式和物理形式。逻辑形式：用ADT来给出数据项的定义 Ex:数学意义上的integers： +, -物理形式：数据结构中对数据项的实现。 Ex: 16/32 bit integers, overflow.26数据类型ADT:类型操作数据项: 逻辑形式数据项: 物理形式数据结构:存储空间子程序27问题 问题：一个需要完成的工作。 即一组输入就有一组相应的输出。 问题的定义将包含对任何可行方案所需资源的限制。 问题数学的函数 函数是输入（domain ）和输出（ra

11、nge）之间的一种映射关系。 函数的输入可以是一个值，或者是一个信息的集合。 这些值组成的输入称为函数的参数。 每一个特定的输入，每次函数计算得到的输出就必然相同。28算法与程序算法：解决问题的一种方法或者一个过程。如果将问题看做函数，那么算法就是把输入转换为输出 一个输入到输出的映射一个问题可以用多种算法来解决29计算机软件 计算机软件是与计算机系统操作有关的程序、规程、规则及任何与之有关的文档及数据。 它由两部分组成：一是机器可执行的程序及有关数据；二是机器不可执行的，与软件开发、运行、维护、使用和培训有关的文档。 30小结 有效性 代价与效益 数据结构的定义 程序算法数据结构31& 第一

12、章第一章 绪论绪论 1.1 1.1 引言引言 1.1.2 2 算法算法及算法分析（算法评价）及算法分析（算法评价） 32什么是算法？ 算法是对解决问题的方法的一种精确描述。 并非所有问题都有算法，有些问题经研究可行，则可能有相应算法；而有些问题经研究不可行，则没有相应算法。 因此，算法研究在某种意义上就是可行性研究。 33算法的性质 算法可以理解为动作序列的有限集合 仅有一个初始动作 每个动作的后继动作是确定的 算法的终止表示问题得到解答或问题没有解答 34算法算法是为了解决某类问题而规定的一个有限长的操作序列操作序列。一个算法必须满足以下五个重要特性：1 1有穷性有穷性 2 2确定性确定性

13、3 3可行性可行性4 4有输入有输入 5 5有输出有输出算法的性质351 1有穷性有穷性 对于任意一组合法输入值，在执行有穷步骤有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间有限时间内完成。 2 2确定性确定性 对于每种情况每种情况下所应执行的操作，在算法中都有确切确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且并且在任何条件下，算法都只有一在任何条件下，算法都只有一条执行路径。条执行路径。363 3可行性可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。4 4有输入有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些

14、输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。37 5 5有输出有输出 它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。38算法设计的原则设计算法时，通常应考虑达到以下目标：1正确性正确性2. . 可读性可读性3健壮性健壮性4高效率与低存储量需求高效率与低存储量需求391 1正确性正确性 首先，首先，算法应当满足满足以特定的“规格规格说明说明”方式给出的需求需求。 其次，其次，对算法是否“正确正确”的的理解可以有以下四个层次四个层次：a a程序中不含语法错误；b b程序对于几组输入数据能够得出满足要求的结果

15、；40 c c程序对于精心选择的、典型、苛刻且程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足带有刁难性的几组输入数据能够得出满足要求的结果；要求的结果；通常以第 c c 层意义的正确性作为衡量一个算法是否合格的标准。 d d程序对于一切合法的输入数据都能得出满足要求的结果；412. . 可读性可读性 算法主要是为了人的阅读与交流阅读与交流，其次才是为计算机执行，因此算法应该易易于于人的理解理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。423健壮性健壮性 当输入的数据非法非法时，算法应当恰当地作出反映或进行相应处理进行相应处理，而不是产生莫名奇妙的输出结果。并且

16、，处理出处理出错的方法错的方法不应是中断程序的执行，而应是返回返回一个表示错误或错误性质的值表示错误或错误性质的值，以便在更高的抽象层次上进行处理。434高效率与低存储量需求高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。44& 第一章第一章 绪论绪论 1.1 1.1 引言引言 1.1.2 2 算法及算法及算法分析算法分析（算法评价）（算法评价） 45算法分析与算法复杂度 算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论其复杂度，探讨具体算法对问题的适应性 算法的复杂度分时间复杂度和空间复杂度。 计算机理论科

17、学中，按照计算复杂性研究问题求解的难易性，可把问题分为 P类、NP类 和 NP-完全类。 46算法的效率对于一个问题通常有多种解法（算法），应该选择哪一种呢？计算机程序设计的核心有两个目标（有时它们互相冲突）1. 设计一种容易理解、编码和调试的算法2. 设计一种能有效利用计算机资源的算法47算法的效率 (cont)目标1涉及到软件工程原理目标2涉及到数据结构与算法分析本课程主要讲的是与目标2有关的问题怎样度量算法的代价、效率呢？48如何度量效率?1. 实验比较（运行程序）2. 渐近算法分析Asymptotic Algorithm Analysis关键资源:影响运行时间的因素:对很多算法而言，运

18、行时间依赖与输入的规模执行算法所需要的时间T写成输入规模n的函数，记为T(n)49怎样比较两种算法解决问题的效率呢？ 实验比较用源程序分别实现这两种算法，然后输入适当的数据运行，测算两个程序各自的开销这是一种事后统计的方法 渐近算法分析(asymptotic algorithm analysis)，简称算法分析(algorithm analysis) 可以估算出当问题规模变大时，一种算法及实现它的程序的效率和开销这是一种事前分析估算的方法50“规模”与“基本操作” 判断算法性能的一个基本考虑是处理一定“规模” (size)的输入时该算法所需执行的“基本操作” (basic operation)

19、数 “规模”一般是指输入量的数目 比如，在排序问题中，问题的规模可以用被排序元素的个数来衡量51“规模”与“基本操作”（续） 一个“基本操作”必须具有这样的性质：完成该操作所需时间与操作数的具体取值无关在大多数高级语言中，下列操作是基本操作： 赋值运算 简单算术运算 简单布尔运算 简单IO操作 函数返回n个整数累加不是基本操作 因为其代价依赖于n的值(即大小)52运行时间和增长率 由于影响运行时间的最主要因素一般是输入的规模，所以经常把执行算法所需要的时间T写成输入规模n的函数，记为T(n)我们总是假设T(n)为非负值 算法的增长率(growth rate)是指当输入规模增长时，算法代价的增长

20、速率53最佳、最差和平均情况不是相同规模的所有输入的运行时间都相同顺序搜索法（Sequential search）从一个n元一维数组中找出一个给定的值K :从第一个元素开始，依次检索每一个元素，直到找到K为止最佳情况:最差情况:平均情况:54请用通俗的例子谈谈对增长率和平均情况 两个概念的理解请邮件告诉我（）55Growth Rate Graph565.1.1 时间复杂性（续）时间复杂性（续） 更快的计算机，还是更快的算法?57时间复杂度对解题速度的影响O(n)解解 题题 速速 度度n = 10n = 30n = 60n0.01 ms0.03 ms0.06 msn20.1 ms0.9 ms3.

21、6 msn50.1 s24.3 s13.0 min2n1.0 ms17.9 min366.0 世纪世纪3n0.059 s6.5 年年1.31013 世世纪纪58u 阿达尔定律设 f 为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比，p 处理机的数目，Sp 为并行计算机系统最大的加速能力（单位：倍），则设 f =1%，p ，则Sp =100。串行计算与并行计算pffSp1159算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论其复杂度，探讨具体算法对问题的适应性 算法的时间复杂度 规模 基本操作 增长率 平均情况 效率请把下列的术语融入到上句中，请把下列的术语融入到上句

22、中，对算法分析的任务进行更加清晰的说明对算法分析的任务进行更加清晰的说明60渐近分析:大O定义: 对于非负函数T(n)，若存在两个正常数c和n0，使得当nn0时有T(n)cf(n)， 则称T(n)在集合O(f(n)中。用法: 这个算法最佳、平均、最差情况（下的增长率的上限）在O(n2)中.含意: 对于问题的所有最佳、平均、最差情况输入，只要输入规模足够大(即 nn0), 该算法总能在cf(n) 步以内完成.61上限:大O (cont)增长率的上限用符号O表示，称为大O表示法(big-Oh notation).Example: If T(n) = 3n2 then T(n) is in O(n2

23、).希望最“紧”（即最小）的上限:虽然 T(n) = 3n2 可以说它在O(n3)中, 我们更喜欢用O(n2).62上限的例子例1:考虑找出整数数组中某个元素的顺序检索法 (average cost).如果访问并检查数组中的一个元素需要时间cs (cs为常数)，那么在平均情况下T(n) = csn/2 。当n 1时，csn/2 1，c1n2 + c2n = c1n2 + c2n2 = (c1 + c2)n2.因此取c = c1 + c2 and n0 = 1，有T(n) n0 时有T(n) = cg(n) ，则称T(n) 在集合(g(n)中意义: 对于问题的所有最佳、平均、最差情况输入，只要输

24、入规模足够大(即 nn0),该算法的完成至少需要cf(n)步.下限.65Big-Omega Example例1：假定T(n) = c1n2 + c2n. (c1，c20)则有 c1n2 + c2n = c1n2 for all n 1.因此，取c = c1 ，n0 = 1 ，有T(n) = cn2.所以,根据定义, T(n) 在(n2)中 也可以说T(n)在 (n)中我们希望找到一个最“紧”的可能限制.（最大下限）66Theta Notation上限和下限描述了算法运行时间的范围当上、下限相等时，可以用表示法定义: 如果非负函数T(n)既在O(h(n)中，又在(h(n)中，则称算法T(n)是(

25、h(n)。这时也说T(n)与h(n)同阶67A Common Misunderstanding“算法最佳情况是输入规模为1时，因为这时运行最快”。错误！大O指的是当n趋近于时的增长率最佳情况指的是在规模为n的所有输入中哪个输入运行最快。68A Common Misunderstanding混淆了最差情况和上限上限指的是增长率最差情况指的是给定规模的所有可能输入中最差的输入，消耗（运行）的时间最大69Simplifying Rules1. If f(n) is in O(g(n) and g(n) is in O(h(n), then f(n) is in O(h(n).2. If f(n) i

26、s in O(kg(n) for any constant k 0, then f(n) is in O(g(n).3. If f1(n) is in O(g1(n) and f2(n) is in O(g2(n), then (f1 + f2)(n) is in O(max(g1(n), g2(n).4. If f1(n) is in O(g1(n) and f2(n) is in O(g2(n) then f1(n)f2(n) is in O(g1(n)g2(n).70程序运行时间的计算(1)Example 1: a = b;This assignment takes constant t

27、ime, so it is (1).Example 2:sum = 0;for (i=1; i=n; i+) sum += n;时间代价为时间代价为(1)时间代价为时间代价为nincnc1)(71程序运行时间的计算(2)Example 3:sum = 0;for (i=1; i=n; i+) for (j=1; j=i; j+) sum+;for (k=0; kn; k+) Ak = k;时间代价为常量时间代价为常量c1时间代价为时间代价为c2n时间代价为时间代价为)(2) 1(23111333ncnnciccniijni72程序运行时间的计算(3)Example 4:sum1 = 0;for

28、 (i=1; i=n; i+) for (j=1; j=n; j+) sum1+;sum2 = 0;for (i=1; i=n; i+) for (j=1; j=i; j+) sum2+;时间代价为时间代价为(n2)时间代价为时间代价为(n2)73程序运行时间的计算(4)Example 5:sum1 = 0;for (k=1; k=n; k*=2) for (j=1; j=n; j+) sum1+;sum2 = 0;for (k=1; k=n; k*=2) for (j=1; j=k; j+) sum2+;第一段程序的时间代价为第一段程序的时间代价为 (nlogn)第二段程序的时间代价为第二段

29、程序的时间代价为 (n)外层for循环当i=1, 2, 22, , 2k=n时执行, 总共执行1+k次，因为k=logn, 所以总共执行1+logn次。又内层循环执行次数恒为n，所以第一段程序的总时间代价可表示为n(1+logn), 即(nlogn)外层for循环当i=1, 2, 22, , 2k=n时执行, 而内层循环执行k次，所以第二段程序的总时间代价可表示为1+2+22+ + 2k= , 由公式2.9可知，其和为2k+1-1, 因为k=logn, 所以总时间代价为2n-1, 即(n)kii0274其他控制语句 while循环、do-while循环分析方法与for循环类似 if语句最差情况

30、时间代价是then和else部分中时间代价较大的那一个对于平均情况代价也是如此假设n的取值与执行哪一条指令的概率无关 switch语句最差情况时间代价是所有分支中开销最大的一个 子程序调用加上执行子程序的时间75问题的分析 问题代价的上限：已知最优算法的代价上限 问题代价的下限：所有可能算法的代价下限（包括尚未设计出来的算法）76多参数问题Compute the rank ordering for all C pixel values in a picture of P pixels.for (i=0; iC; i+) / Initialize count counti = 0;for (i=

31、0; iP; i+) / Look at all pixels countvalue(i)+; / Increment countsort(count); / Sort pixel countsIf we use P as the measure, then time is (P log P).More accurate is (P + C log C).77空间代价 与分析时间代价类似与分析时间代价类似 渐近分析中增长率的概念对于空间代价同样适渐近分析中增长率的概念对于空间代价同样适用用 时间代价是相对于处理某个数据结构的算法而时间代价是相对于处理某个数据结构的算法而言的言的 空间代价是相对

32、于该数据结构本身而言的空间代价是相对于该数据结构本身而言的78空间/时间权衡原则(space/time tradeoff principle) 以时间换空间以时间换空间 信息压缩存储信息压缩存储 以空间换时间以空间换时间 查找表查找表 基于磁盘的空间基于磁盘的空间/时间权衡原则时间权衡原则 在磁盘上的存储代价越小，程序运行得越快在磁盘上的存储代价越小，程序运行得越快79小结 算法分析的动机、基本符号和基本技术 增长率的概念 增长率的上限和下限的概念 能够区分一种算法的代价和一个问题的代价80第一部分小结 数据结构和算法 效率 代价和效益 数据结构的定义；ADT 算法分析 动机：增长率 基本符号

33、：O、81什么情况下，可以直接用表示算法的复杂度？即什么情况下，算法的下限和上限相等。 请邮件告诉我（）82习题讲解写出下列程序段平均情况下时间代价的表示式。假设所有变量类型都为int：(a)a = b + c;d = a + e;(b)sum = 0;for(i=0;i3;i+)for(j=0;jn;j+)sum+;(c)sum = 0;for(i=0;in*n;i+) sum+;时间代价为时间代价为(1)时间代价为时间代价为(n)时间代价为时间代价为(n2)83(d)假设数组A中含有n个元素，函数Random花的时间是常数值，sort需要执行nlogn步。for(i=0;in;i+)for

34、(j=0;jn;j+) Ai = Random(n);sort(A,n);(e)假设数组A中元素为从0到n1的任意一个排列。sum3 = 0;for(i=0;in;i+)for(j=0;Aj!=i;j+) sum3+;时间代价为时间代价为(n2logn)时间代价为时间代价为 = (n2)nii184(f)sum = 0;if(EVEN(n)for(i=0;in;i+) sum+;else sum = sum + n;时间代价为时间代价为(n)85课堂练习1. The primary purpose of most computer programs is a) to perform a mat

35、hematical calculation. b) to store and retrieve information. c) to sort a collection of records. d) all of the above. e) none of the above.2. An algorithm must be or do all of the following EXCEPT: a) correct b) composed of concrete steps c) ambiguous d) composed of a finite number of steps e) termi

36、nate863. Asymptotic analysis refers to:a) The cost of an algorithm in its best, worst, or average case.b) The growth in cost of an algorithm as the input size grows towards infinity.c) The size of a data structure.d) The cost of an algorithm for small input sizes4. Pick the growth rate that correspo

37、nds to the most efficient algorithm as n gets large:a) 5nb) 20 log nc) 2n2d) 2n87树树数据结构与算法88引言前述我们所研究的数据结构线性表是线性结构。本章将研究的树型结构是一种动态的，非线性的，可描述结构层次特性的数据结构。这种结构是按分枝关系把信息联系起来的数据组织形式。在日常生活中这种结构是不少见的，如：89家谱图(谱系图)Chang Chang父祖父祖母Chang母外祖父外祖母90行政机构图中央人民政府湖南省湖北省上海市长沙 全省各地市各市、县、区91UNIX文件目录92XML文件结构93树型的网络拓扑结构9

38、4编译程序中使用语法树95树型结构小节 客观世界中广泛存在树结构 树结构也在计算科学领域中被广泛的（创造和）应用以上各例的数据(信息)组织形式，均称为树型结构。当然它与植物树有所不同，(它的根在上，枝在下)96树的定义和基本术语97树的定义 一棵树(tree)T是由一个或一个以上结点组成的有限集 其中有一个特定的结点R称为T的根结点。 集合(TR)中的其余结点可被划分为n0个互不相交的子集T1，T2，, Tn，其中每个子集本身又是一棵树，并且其相应的根结点R1，R2，, Rn是R的子结点 子集Ti(1in)称为树T的子树(subtree)。 子树可如下排序：Ti排在Tj之前，当且仅当i1时，其

39、余结点可分为时，其余结点可分为m (m0)个互个互 不相交的有限集不相交的有限集T1, T2, , Tm，其中每一，其中每一 棵子集本身又是一棵符合本定义的树，棵子集本身又是一棵符合本定义的树， 称为根称为根root的子树。的子树。 数据关系数据关系 R：106 基本操作：基本操作：查查 找找 类类 插插 入入 类类删删 除除 类类107 Root(T) / 求树的根结点求树的根结点 查找类：查找类：Value(T, cur_e) / 求当前结点的元素值求当前结点的元素值 Parent(T, cur_e) / 求当前结点的双亲结点求当前结点的双亲结点LeftChild(T, cur_e) /

40、求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T, cur_e) / 求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T) / 判定树是否为空树判定树是否为空树 TreeDepth(T) / 求树的深度求树的深度TraverseTree( T, Visit() ) / 遍历遍历108InitTree(&T) / 初始化置空树初始化置空树 插入类：插入类：CreateTree(&T, definition) / 按定义构造树按定义构造树Assign(T, cur_e, value) / 给当前结点赋值给当前结点赋值InsertChild(&T, &p, i, c)

41、/ 将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树109 ClearTree(&T) / 将树清空将树清空 删除类：删除类：DestroyTree(&T) / 销毁树的结构销毁树的结构DeleteChild(&T, &p, i) / 删除结点删除结点p的第的第i棵子树棵子树110树结点的ADT/ General tree node ADTtemplate class GTNode public: GTNode(const Elem&); / Constructor GTNode(); / Destructor Elem value(); / Return value b

42、ool isLeaf(); / TRUE if is a leaf GTNode* parent(); / Return parent GTNode* leftmost_child(); / First child GTNode* right_sibling(); / Right sibling void setValue(Elem&); / Set value void insert_first(GTNode* n); void insert_next(GTNode* n); void remove_first(); / Remove first child void remove_next

43、(); / Remove sibling;111树的ADT/ General tree node ADTtemplate class GenTree private： void printhelp(GTNode *); /print helper functionpublic: GenTree(); /constructor GenTree(); /Destructor void clear(); /Send nodes to free store GTNode* root(); /Return the root /Combine two subtree Void newroot(Elem&,

44、GTNode*,GTNode*); Void print(); /Print a tree;112二叉树的定义和性质113二叉树Binary Trees二叉树(binary tree)是结点(node)的有限集合，这个集合或者为空(empty)，或者由一个根结点(root)以及两棵二叉树组成, 这两棵二叉树分别称作这个根的左子树(left subtree)和右子树(right subtree) ,这两棵二叉树分别与根结点相连且彼此不相交. 114115二叉树的五种基本形态N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为

45、空树116二叉树的特性(性质1)：在二叉树中，第i层上的结点数最多为2i1(i1);(归纳法)： 当i=1时，只有一个结点，2i1=20=1(归纳基础)归纳假设：假定对所有的j, 1ji 命题成立，即第j层上结点总数最多为2j1个结点。那么，可以证明 j=i 时命题成立。117归纳步骤：由归纳假设可知，i1层上的结点总数最多为2i2。由于二叉树每个结点的度最大为2，所以第i层上的结点最大数为第i1层上结点最大数的2倍，即2 2i2，从而得证，i层上最大结点数为2i1.118：深度为k的二叉树至多有2k1个结点. (k1)证明：证明：深度为k的二叉树结点最大数为每一层结点最大数之和。由特性一得：

46、122)(111kkiikii层上结点最大数第二叉树的特性(性质2)119：对任一棵二叉树，若叶结点数为n0, 度为2的结点数为n2，则有n0=n2+1 成立证明：证明：设度为1的结点数为n1，则二叉树的结点总数为：n=n0+n1+ n2 (1)二叉树的特性(性质3)120设二叉树的分支总数为B，除根结点外，每一个结点都有一个分支进入，则B=n1 又因为度为1的结点发出一个分支，度为2的结点发出2个分支所以： B=n1+2n2从而得 n=n1+2n2+1 (2)由(1), (2)式得 n0=n2+1 成立.121Full and Complete Binary Trees满二叉树(full b

47、inary tree)的每一个结点或者是一个分支结点，并恰有两个非空子结点；或者是叶结点.完全二叉树(complete binary tree)从根结点起每一层的结点从左到右连续填充, 除了最下面一层以外其余各层都是满的, 并且最下面一层的结点都集中在该层的最左边.122：具有n个结点的完全二叉树，其深度为： k=log2n+1证证：根据性质2和完全二叉树的定义，设完全二叉树的深度为k，则 2k1 1 n 2k1深度为k1的完全二叉树的最大结点数深度为k的完全二叉树的最大结点数即2k1 n 2k 于是有k1 log2nk k为整数 k =log2n +1 得证完全二叉树的特性(性质4)123特

48、性五：特性五：如果对一棵有n个结点的完全二叉树(其深度为log2n+1)的结点按层次自上而下，从左至右编号，则对任一编号为i的结点(1in)有 2) 若2in 则结点i的左孩子是编号为2i的结点; 否则结点i无左孩子（结点i为叶子结点）。1) 若i=1, 则该结点为根结点，无双亲，若i1, 则结点i的双亲是编号为i/2 的结点。记为parent(i)= i/2 完全二叉树的特性(性质5)3) 若2i+1n 则结点i的右孩子是结点2i+1; 否则结点i无右孩子。12448925106371结点3211时，其余结点可分为不相交的有限集时，其余结点可分为不相交的有限集 Tl、 Tr，其中每一，其中每

49、一 个子集本身又是一棵符合个子集本身又是一棵符合 本定义的二叉树，称为根本定义的二叉树，称为根root的子树。的子树。 数据关系数据关系 R：134二叉树结点的ADT/ Binary tree node abstract classtemplate class BinNode public: virtual Elem& val() = 0; / Return the nodes element virtual void setVal(const Elem&) = 0; / Set the nodes element virtual BinNode* left() const = 0; / Re

50、turn the nodes left child virtual void setLeft(BinNode*) = 0; / Set the nodes left child virtual BinNode* right() const = 0; / Return the nodes right child virtual void setRight(BinNode*) = 0; / Set the nodes right child virtual bool isLeaf() = 0; / Return true iff the node is a leaf;135Binary Tree