数据结构讲义第9章.ppt

《数据结构讲义第9章.ppt》由会员分享，可在线阅读，更多相关《数据结构讲义第9章.ppt（79页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、1 物料管理物料管理第1页 wrxAlgorithms and Data Structures数数 据据 结结 构构吴吴 润润 秀秀南昌工程学院南昌工程学院2 物料管理物料管理第2页 wrxAlgorithms and Data Structures9.1静态查找表静态查找表9.2动态查找表动态查找表9.3哈希表哈希表目录目录第第 九九 章章 查找查找3 物料管理物料管理第3页 wrxAlgorithms and Data Structures 查找的基本概念查找的基本概念查找的基本概念查找的基本概念 查找表查找表(Search Table)：是由同一类型的数据元素（或记录）构成的集合。由于“

2、集合”中的数据元素之间存在着完全松散的关系,因此查找表是一种非常灵便的数据结构。4 物料管理物料管理第4页 wrxAlgorithms and Data Structures查找表的操作：查找表的操作：1、查询某个“特定的”数据元素是否在查找表中。2、检索某个“特定的”数据元素的各种属性。3、在查找表中插入一个数据元素；4、从查找表中刪去某个数据元素。静态查找表：静态查找表：对查找表只作前两种操作，这两种操作统称为“查找”的操作，则称此类查找表为静态查找表静态查找表。动态查找表：动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个元素（也即元素集合可以根据情

3、况动态改变），则称此类表为动态查找表动态查找表。5 物料管理物料管理第5页 wrxAlgorithms and Data Structures 在日常生活中，人们几乎每天都要进行“查找”工作。例如，在电话号码簿中查阅“某单位”或“某人”的电话号码；在字典中查阅“某个词”的读单和含义等等。其中其中“电话号码簿电话号码簿”和和“字典字典”都可视作是一张查找表都可视作是一张查找表。查找：查找：根据给定的某个值，在查找表中确定一个其关键字等于给定的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的

4、记录，则称查找不成功。关键字（关键码）、主关键字、次关键字。举例：P214页书，（查找学生的高考成绩）6 物料管理物料管理第6页 wrxAlgorithms and Data Structures如何进行查找呢？其实，在一个结构中查找某个数据元素的过程依赖于这个数据元素在结构中所处的地位。因此，对表进行查找的方法取决于表中数据元素依何种关系（这个关系是人为地加上的）组织在一起的。举例：查电话号码时，由于电话号码簿是按用户（集体或个人）的名称（或姓名）分类且依笔划顺序编排，则查找的方法就是先顺序查找待查用户的所属类别，然后在此类中顺序查找，直到找到该用户的电话号码为止。又如，查阅英文单词时，由于

5、字典是按单词的字母在字母表中的次序编排的，因此查找时不需要从字典中第一个单词比较起，而只要根据待查单词中每个字母在字母表中的位置查到该单词。7 物料管理物料管理第7页 wrxAlgorithms and Data Structures 同样，在计算机中进行计算机中进行查找的方法查找的方法也随数据结构不同而不同也随数据结构不同而不同。但前面我们又说到查找表中的数据元素之间存在着完全松散的关系，这给我们查找带来不便。为此，需在数据元素之间人为地需在数据元素之间人为地加上一些关系，以例按某种规则进行查找加上一些关系，以例按某种规则进行查找，即以另一种数据结构来表示查找表。一些约定：一些约定：典型的关

6、键字类型说明：typedef float KeyType;/实型 typedef int KeyType;/整型typedef char*KeyType;/字符串型 数据元素类型定义为：typedef struct KeyType key;/关键字域 .ElemType;8 物料管理物料管理第8页 wrxAlgorithms and Data Structures对两个关键字的比较约定为如下的宏定义：对数值型关键字#define EQ(a,b)(a)=(b)#define LT(a,b)(a)(b)#define LQ(a,b)(a)=(b)对字符串型关键字#define EQ(a,b)(!s

7、trcmp(a),(b)#define LT(a,b)(strcmp(a),(b)0)#define LQ(a,b)(strcmp(a),(b)=0)9 物料管理物料管理第9页 wrxAlgorithms and Data Structures静态查找表静态查找表静态查找表静态查找表 静态查找表的抽象数据类型定义：ADT StaticSearchTable数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P：Create(&ST,n);操作结果：构造一个含n个数据元素的静态查找表ST。Destroy(

8、&ST);初始条件：静态查找表ST存在。操作结果：销毁表ST。9.1静态查找法静态查找法10 物料管理物料管理第10页 wrxAlgorithms and Data StructuresSearch(ST,key);初始条件：静态查找表ST存在，key为和关键字类型相同的给定值。操作结果：若ST中在在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。Traverse(ST,Visit();初始条件：静态查找表ST存在，Visit是对元素操作的应用函数。操作结果：按某种次序对ST的每个元素调用函数visit()一次且仅一次。一旦visit()失败，则操作失败。ADT

9、 StaticSearchTable11 物料管理物料管理第11页 wrxAlgorithms and Data Structures顺序表的查找顺序表的查找顺序表的查找顺序表的查找 以顺序表或线性链表表示静态查找表，则Search函数可用顺顺序查找序查找来实现。静态查找表的顺序存储结构typedef struct ElemType*elem;/ElemType elem100;int length;SSTable;顺序查找：顺序查找：从表中最后一个记录开始表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，查找不成功。

10、int Search_Seq(SSTable ST,KeyType key)ST.elme0.key=key;for(i=ST.length;!EQ(ST.elemi.key,key);-i);return i;演示！演示！12 物料管理物料管理第12页 wrxAlgorithms and Data Structures查找操作的性能分析：查找操作的性能分析：查找算法中的基本操作是将记录的关键字和给定值进行比较，通常以“其关键字和给定值进行过比较的记录个数的平均值其关键字和给定值进行过比较的记录个数的平均值”作为衡量依据。平均查找长度：平均查找长度：为确定记录在查找表中的位置，需用和给定值进行

11、比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度的平均查找长度(Average Search Length)。其中：Pi为查找表中第i个记录的概率，且 ；Ci为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数。对于含有n个记录的表，查找成功时的平均查找长度为：13 物料管理物料管理第13页 wrxAlgorithms and Data Structures 假设每个记录的查找概率相等，即 Pi=1/n则在等概率情况下顺序查找的平均查找长度为：假设查找成功与不成功的概率相同：从顺序查找的过程可见，Ci取决于所查记录在表中的位置。如：查找表中最后一个记录时

12、，仅需比较一次；而查找表中第一个记录时，则需比较n次。一般情况下Ci=n-i+1;假设n=ST.length，则顺序查找的平均查找长度为：ASL=nP1+(n-1)P2+.+2Pn-1+Pn 14 物料管理物料管理第14页 wrxAlgorithms and Data Structures 前面总假设各个记录的查找概率并不相等。但实际常常情况不是这样，如果能预先知道每个记录的查找概率，则应先对记录的查找概率进行排序，使表中记录按查找概率由小至大重新排列，以便提高查找效率。但是，在一般情况下，记录的查找概率预先无法测定。为了提高查找效率，我们可以在每个记录中附设一个访问频度域，并使顺序表中的记录

13、始终不断往后移，以例在以后的逐次查找中减少比较次数。或者在每次查找之后都将刚查找到的记录直接移至表尾。15 物料管理物料管理第15页 wrxAlgorithms and Data Structures有序表的查找（可以采用折半查找来实现）有序表的查找（可以采用折半查找来实现）以有序表表示静态查找表时，Search函数可用折半查找来实现。折半查找（Binary Search）的查找过程是：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。16 物料管理物料管理第16页 wrxAlgorithms and Data Structures见演示！见演示！17 物料管理物料

14、管理第17页 wrxAlgorithms and Data Structures折半查找的查找实现折半查找的查找实现int Search_Bin(SSTable ST,KeyType key)low=1;high=ST.length;while(low50时，可得近似结果 可见，折半查找的效率比顺序查找高，但折半查找只能适用于有序表，且限于顺序存储结构（对线性链表无法进行折半查找）。21 物料管理物料管理第21页 wrxAlgorithms and Data Structures索引顺序表的查找索引顺序表的查找 若以索引顺序表表示静态查找表，则若以索引顺序表表示静态查找表，则Search函数可

15、用函数可用分块查分块查找找来实现。来实现。分块查找分块查找又称又称索引顺序查找索引顺序查找，这是顺序查找的一种改进方法。，这是顺序查找的一种改进方法。在此查找法中，除表本身以外，尚需建立一个在此查找法中，除表本身以外，尚需建立一个“索引表索引表”。22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 532248 86231 7 13索引表最大关键字 起始地址整个表中含有18个记录，可分为三个子表（R1,R2,R6）、(R7,R12)、(R13,R18)对每个子表（或称块）建立一个索引项，其中包括两项内容：最大关键字项 该子表的起始地址 对索引表按关

16、键字有序，则表或者有序或者分块有序。P225页书划上概念！22 物料管理物料管理第22页 wrxAlgorithms and Data Structures 由于由索引项组成的索引表按关键字有序，则确定块的查找可以用顺序查找，亦可用折半查找，而块中记录是任意排列的，则在块中只能是顺序查找。由此，分块查找的算法即为这两种查找算法的简单合成由此，分块查找的算法即为这两种查找算法的简单合成。分块查找的平均查找长度为：ASLbs=Lb+Lw其中：Lb为查找索引表确定所在块的平均查找长度，Lb为在块中查找元素的平均查找长度。一般情况下，为进行分块查找，可以将长度为n的表均匀地分成b块，每块含有s个记录，

17、即b=n/s；又假定表中每个记录的查找概率相等，则每块查找的概率为1/b，块中每个记录的查找概率为1/s。若用顺序查找确定所在块，则分块查找的平均查找长度为：23 物料管理物料管理第23页 wrxAlgorithms and Data Structures1.索引顺序表：存储数据的表+索引；2.存储方法：数据分块存放，且块内无序，但块间有序；每块一个索引项，包括块地址和块中最大数据值。3.查找方法：首先在索引表中查找，索引是有序顺序表，可以采用折半查找方法；然后在 块内查找进行（只能）是顺序查找。总结：总结：24 物料管理物料管理第24页 wrxAlgorithms and Data Stru

18、ctures9.2动态查找法动态查找法动态查找表的定义动态查找表的定义动态查找表的定义动态查找表的定义 动态查找表的特点是：动态查找表的特点是：表结构本身是在查找过程中动态生成的，即对于给定值key,若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。以下是动态查找表抽象数据类型的定义：ADT DymanicSearchTable 数据对象：是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系：数据元素同属一个集合。特点：用于频繁进行插入、删除、查找的所谓动态查找表。特点：用于频繁进行插入、删除、查找的所谓动态查找表。

19、25 物料管理物料管理第25页 wrxAlgorithms and Data Structures基本操作：InitDSTable(&DT);操作结果：构造一个空的动态查找表DT。DestroyDSTable(&DT);初始条件：动态查找表DT存在；操作结果：销毁动态查找表DT。SearchDSTable(DT,key);初始条件：动态查找表DT存在，key为和关键字类型相同的给定值；操作结果：若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。InsertDSTable(&DT,e);初始条件：动态查找表DT存在，e为待插入的数据元素；操作结果：若DT

20、中不存在其关键字等于e.key的数据元素，则插入e到DT。26 物料管理物料管理第26页 wrxAlgorithms and Data StructuresDeleteDSTable(&T,key);初始条件：动态查找表DT存在，key为和关键字类型相同的给定值；操作结果：若DT中存在其关键字等于key的数据元素，则删除之。TraverseDSTable(DT,Visit();初始条件：动态查找表DT存在，Visit是对结点操作的应用函数；操作结果：按某种次序对DT的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。ADT DynamicSearchTable2

21、7 物料管理物料管理第27页 wrxAlgorithms and Data Structures二叉排序树及其查找过程二叉排序树及其查找过程二叉排序树及其查找过程二叉排序树及其查找过程 什么是二叉排序树？什么是二叉排序树？二叉排序树二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树：、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；、它的左、右子树了分别为二叉排序树。12225030011020099LNPEMCY105230216通常，取二叉链表作为二叉排序树的存储结构通常，取

22、二叉链表作为二叉排序树的存储结构二叉排序树二叉排序树又称又称二叉查找树二叉查找树,也可以称为也可以称为二叉分类树二叉分类树28 物料管理物料管理第28页 wrxAlgorithms and Data Structures1、分割式查找法：、分割式查找法：查找步骤：若根结点的关键字值等于查找的关键字，成功。查找步骤：若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，查其左子树。大于根结点的关键否则，若小于根结点的关键字值，查其左子树。大于根结点的关键字值，查其右子树。在左右子树上的操作类似。字值，查其右子树。在左右子树上的操作类似。122250300110200991052

23、30216BiTree SearchBST(BiTree T,KeyType key)/在二叉分类树查找关键字之值为 key 的结点，找到返回该结 /点的地址，否则返回空。T 为二叉分类树的根结点的地址。if (!T)|EQ(key,T-data.key)return(T);else if(LT(key,T-data.key)return(SearchBST(T-lchild,key);else return(SearchBST(T-rchild,key);/SearchBST表示：typedef struct BiTNode ElemType data;struct BiTNode*lchi

24、ld,*rchild;BiTNode;*BiTree;见演示见演示!29 物料管理物料管理第29页 wrxAlgorithms and Data Structures2、插入算法：、插入算法：首先执行查找算法，找出被插结点的父亲结点。首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。注意：新插入的结点总是叶子结点。e、g：将数的序列：将数的序列：122、99、250、

25、110、300、280 作为二叉排序树的结作为二叉排序树的结 点的关键字值，生成二叉排序树。点的关键字值，生成二叉排序树。30 物料管理物料管理第30页 wrxAlgorithms and Data Structures2、插入算法：、插入算法：首先执行查找算法，找出被插结点的父亲结点。首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。注意：新插入的结点总是叶子结点。

26、e、g：将数的序列：将数的序列：122、99、250、110、300、280 作为二叉排序树的结作为二叉排序树的结 点的关键字值，生成二叉排序树。点的关键字值，生成二叉排序树。12231 物料管理物料管理第31页 wrxAlgorithms and Data Structures2、插入算法：、插入算法：首先执行查找算法，找出被插结点的父亲结点。首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。若二叉树为空。则首先单独生成根结点。注意

27、：新插入的结点总是叶子结点。注意：新插入的结点总是叶子结点。e、g：将数的序列：将数的序列：122、99、250、110、300、280 作为二叉排序树的结作为二叉排序树的结 点的关键字值，生成二叉排序树树。点的关键字值，生成二叉排序树树。1221229932 物料管理物料管理第32页 wrxAlgorithms and Data Structures2、插入算法：、插入算法：首先执行查找算法，找出被插结点的父亲结点。首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。插结点作为叶子结点插入。若

28、二叉树为空。则首先单独生成根结点。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。注意：新插入的结点总是叶子结点。e、g：将数的序列：将数的序列：122、99、250、110、300、280 作为二叉排序树的结作为二叉排序树的结 点的关键字值，生成二叉排序树。点的关键字值，生成二叉排序树。122122991222509933 物料管理物料管理第33页 wrxAlgorithms and Data Structures2、插入算法：、插入算法：首先执行查找算法，找出被插结点的父亲结点。首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被判断被插

29、结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。注意：新插入的结点总是叶子结点。e、g：将数的序列：将数的序列：122、99、250、110、300、280 作为二叉排序树的结作为二叉排序树的结 点的关键字值，生成二叉排序树。点的关键字值，生成二叉排序树。12212299122250991222501109934 物料管理物料管理第34页 wrxAlgorithms and Data Structures2、插入算法：、插入算法：首先执行查找算法，找出被插

30、结点的父亲结点。首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。注意：新插入的结点总是叶子结点。e、g：将数的序列：将数的序列：122、99、250、110、300、280 作为二叉排序树的结作为二叉排序树的结 点的关键字值，生成二叉排序树。点的关键字值，生成二叉排序树。1221229912225099122250110991222503001109935 物料管理

31、物料管理第35页 wrxAlgorithms and Data Structures2、插入算法：、插入算法：首先执行查找算法，找出被插结点的父亲结点。首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。注意：新插入的结点总是叶子结点。12225030011028099e、g：将数的序列：将数的序列：122、99、250、110、300、280 作为二叉排序树的结作为二

32、叉排序树的结 点的关键字值，生成二叉排序树。点的关键字值，生成二叉排序树。1221229912225099122250110991222503001109936 物料管理物料管理第36页 wrxAlgorithms and Data Structures2、插入算法：、插入算法：Status SearchBST(BiTree T，KeyType key，BiTree f，BiTree&p)/在二叉排序树 T 查找关键字之值为 key 的结点。初始时 f 为 NULL。/如树空，返回 p 为 NULL及 FALSE。如树非空且查找成功，返回 p=T 及 TRUE。/如树非空且查不成功，返回 p=

33、f 及 FALSE。f 为待插入结点的的父亲结点的地址。if (!T)p=f;return FALSE;else if(EQ(key,T-data.key)p=T;return TRUE;else if(LT(key,T-data.key)return(SearchBST(T-lchild,key,T,p);else return(SearchBST(T-rchild,key,T,p);/SearchBST 程序实现：程序实现：12225030011099Tpf:nullf:T 的父亲结点的父亲结点p:指向最后一个结点，指向最后一个结点，TRUE 找到；找到；FALSE 叶叶子的父亲结点。如：

34、插入子的父亲结点。如：插入 280 的过程。的过程。28037 物料管理物料管理第37页 wrxAlgorithms and Data Structures2、插入算法：、插入算法：执行实例：插入值为执行实例：插入值为 280 的结点的结点 12225030011099Tf：null12225030011099fTKey=28012225030011099fTKey=280f12225030011099T:nullKey=280p1222503001109928038 物料管理物料管理第38页 wrxAlgorithms and Data Structures2、插入算法：、插入算法：Stat

35、us Inset BST(BiTree&T，ElemType e)/在二叉排序树中不存在 e.key 时，插入并返回 TRUE，否则返回 FALSE。if (!SearchBST(T，e.key，NULL，p)s=(Bitree)malloc(sizeof(BitNode);s-data=e;s-lchild=s-rchild=NULL;if (!p)T=s;else if(LT(e.key,p-data.key)p-lchild=s;else p-rchild=s;return TRUE;return FALSE;/Insert BST 程序实现：程序实现：12225030011099Tpf

36、:T 的父亲结点的父亲结点p:指向最后一个结点，指向最后一个结点，TRUE 找到；找到；FALSE 叶叶子的父亲结点。如：插入子的父亲结点。如：插入 280 的过程。的过程。280f:null39 物料管理物料管理第39页 wrxAlgorithms and Data Structures 1560703020503、二叉排序树的查找分析、二叉排序树的查找分析 平均情况分析（在成功查找两种的情况下）平均情况分析（在成功查找两种的情况下）e.g:下述两种情况下的成功的平均查找长度下述两种情况下的成功的平均查找长度 ASL156070302050ASL=(1+2+2+3+3+3)/6=14/6AS

37、L=(1+2+3+4+5+6)/6=21/640 物料管理物料管理第40页 wrxAlgorithms and Data Structures 3、二叉排序树的查找分析、二叉排序树的查找分析 平均情况分析（在成功查找两种的情况下）平均情况分析（在成功查找两种的情况下）在一般情况下，设在一般情况下，设 P（n，i）且它的左子树的结点个数为）且它的左子树的结点个数为 i 时的平均查找长时的平均查找长度。右图的结点个数为度。右图的结点个数为 n=6 且且 i=3;则则 P（n,i）=P（6,3）=1+(P(3)+1)*3+(P(2)+1)*2 /6 =1+(5/3+1)*3+(3/2+1)*2 /6

38、注意：这里注意：这里 P(3)、P(2)是具有是具有 3 个结点、个结点、2 个结点的二叉排序树的平均查找个结点的二叉排序树的平均查找 长度。长度。在一般情况下，在一般情况下，P（i）为具有）为具有 i 个结点二叉排序树的平均查找个结点二叉排序树的平均查找 长度。长度。P(3)（1+2+2）/3=5/3 P(2)（1+2）/2=3/2 P（n,i）=1+(P(i)+1)*i+(P(n-i-1)+1)*(n-i-1)/n n-1 P（n）=P（n,i）/n i=0 =1.465log2n 156070302050左子树左子树0到到n-1个结点个结点右子树右子树n-1到到0个结点个结点41 物料管

39、理物料管理第41页 wrxAlgorithms and Data Structures 4、二叉排序树的删除操作、二叉排序树的删除操作 叶子结点：直接删除，更改它的父亲结点的相应指针为空。如：删除数据场为叶子结点：直接删除，更改它的父亲结点的相应指针为空。如：删除数据场为 15、70 的结点。的结点。15607030205060302050子树的根结点：通常的做法：选取子树的根结点：通常的做法：选取“替身替身”取代被删结点。有资格充当该替身的是谁哪？取代被删结点。有资格充当该替身的是谁哪？左子树中最大的结点左子树中最大的结点 或或 右子树中最小的结点右子树中最小的结点，参看下图。，参看下图。要

40、点：维持二叉排序树的特性不变。在中序遍历要点：维持二叉排序树的特性不变。在中序遍历 中紧靠着被删结点的结点中紧靠着被删结点的结点 才有资格作为才有资格作为“替身替身”。42 物料管理物料管理第42页 wrxAlgorithms and Data Structures4、二叉排序树的删除操作、二叉排序树的删除操作 12225030011020099105230216400450500子树的根结点：若被删结点的左儿子为空或者右儿子为空。子树的根结点：若被删结点的左儿子为空或者右儿子为空。如下图所示，删除结点的数据场的关键字值为为如下图所示，删除结点的数据场的关键字值为为 99、300 的结点。的结

41、点。被删结点被删结点122250300200230216400450500110105删除删除9943 物料管理物料管理第43页 wrxAlgorithms and Data Structures4、二叉排序树的删除操作、二叉排序树的删除操作 12225030011020099105330316400450500被删结点被删结点122250330230216400450500删除删除30011099105子树的根结点：若被删结点的左儿子为空或者右儿子为空。子树的根结点：若被删结点的左儿子为空或者右儿子为空。如下图所示，删除结点的数据场的关键字值为为如下图所示，删除结点的数据场的关键字值为为 9

42、9、300 的结点。的结点。31644 物料管理物料管理第44页 wrxAlgorithms and Data Structures 4、二叉排序树的删除操作、二叉排序树的删除操作 12225030011020099105330316400450500被删结点被删结点结论：结论：将被删结点的另一儿子作为它的父将被删结点的另一儿子作为它的父 亲结点的儿子，究竟是作为左儿子亲结点的儿子，究竟是作为左儿子 还是右儿子依原替身结点和其父亲还是右儿子依原替身结点和其父亲 结点的关系而定。结点的关系而定。释放被删结点的空间。释放被删结点的空间。被删结点被删结点子树的根结点：若被删结点的左儿子为空或者右儿子

43、为空。子树的根结点：若被删结点的左儿子为空或者右儿子为空。如下图所示，删除结点的数据场的关键字值为为如下图所示，删除结点的数据场的关键字值为为 99、300 的结点。的结点。45 物料管理物料管理第45页 wrxAlgorithms and Data Structures 4、二叉排序树的删除操作、二叉排序树的删除操作 子树的根结点：若被删结点的左、右子树皆不空，则：子树的根结点：若被删结点的左、右子树皆不空，则：通常的做法：选取通常的做法：选取“替身替身”取代被删结点。有资格充当该替身的是谁哪？取代被删结点。有资格充当该替身的是谁哪？左子树中最大的结点左子树中最大的结点(被删结点的左子树中的

44、最右的结点，其右儿子指针场为空被删结点的左子树中的最右的结点，其右儿子指针场为空)或或 右子树中最小的右子树中最小的 结点结点(被删结点的右子树中的最左的结点，其左儿子指针场为空被删结点的右子树中的最左的结点，其左儿子指针场为空)，参看下图。，参看下图。要点：维持二叉分类树的特性不变。在中序周游中紧靠着被删要点：维持二叉分类树的特性不变。在中序周游中紧靠着被删 结点的结点才有资格作为结点的结点才有资格作为“替身替身”。12225030011020099105330316400450500被删结点被删结点替身替身替身替身11025030010520099330316400450500做法：将替身

45、的数据场复制到被删结做法：将替身的数据场复制到被删结 点的数据场。点的数据场。将结点将结点 的左儿子作为的左儿子作为 的父结点的父结点 的右儿子。的右儿子。11011099注意：结点注意：结点 右儿子必为空右儿子必为空 结点结点 的父结点为的父结点为1101109946 物料管理物料管理第46页 wrxAlgorithms and Data Structures 4、二叉排序树的删除操作、二叉排序树的删除操作 12225030011020099105330316400450500被删结点被删结点替身替身替身替身20025030011099105216400450500子树的根结点：若被删结点的

46、左、右子树皆不空，则：子树的根结点：若被删结点的左、右子树皆不空，则：通常的做法：选取通常的做法：选取“替身替身”取代被删结点。有资格充当该替身的是谁哪？取代被删结点。有资格充当该替身的是谁哪？左子树中最大的结点左子树中最大的结点(被删结点的左子树中的最右的结点，其右儿子指针场为空被删结点的左子树中的最右的结点，其右儿子指针场为空)或或 右子树中最小的右子树中最小的 结点结点(被删结点的右子树中的最左的结点，其左儿子指针场为空被删结点的右子树中的最左的结点，其左儿子指针场为空)，参看下图。，参看下图。要点：维持二叉分类树的特性不变。在中序周游中紧靠着被删要点：维持二叉分类树的特性不变。在中序周

47、游中紧靠着被删 结点的结点才有资格作为结点的结点才有资格作为“替身替身”。做法：将替身的数据场复制到被删结做法：将替身的数据场复制到被删结 点的数据场。点的数据场。将结点将结点 的右儿子作为的右儿子作为 的父结点的父结点 的左儿子。的左儿子。注意：结点注意：结点 左儿子必为空左儿子必为空 结点结点 的父结点为的父结点为20020020020025033031647 物料管理物料管理第47页 wrxAlgorithms and Data Structures 4、二叉排序树的删除操作、二叉排序树的删除操作 12225030011020099105230216400450500被删结点被删结点替身

48、替身替身替身子树的根结点：若被删结点的左、右子树皆不空，则：子树的根结点：若被删结点的左、右子树皆不空，则：通常的做法：选取通常的做法：选取“替身替身”取代被删结点。有资格充当该替身的是谁哪？取代被删结点。有资格充当该替身的是谁哪？左子树中最大的结点左子树中最大的结点(被删结点的左子树中的最右的结点，其右儿子指针场为空被删结点的左子树中的最右的结点，其右儿子指针场为空)或或 右子树中最小的右子树中最小的 结点结点(被删结点的右子树中的最左的结点，其左儿子指针场为空被删结点的右子树中的最左的结点，其左儿子指针场为空)，参看下图。，参看下图。要点：维持二叉分类树的特性不变。在中序周游中紧靠着被删要

49、点：维持二叉分类树的特性不变。在中序周游中紧靠着被删 结点的结点才有资格作为结点的结点才有资格作为“替身替身”。结论：结论：先将替身的数据场复制到被删结点先将替身的数据场复制到被删结点 将原替身的另一儿子作为它的父亲将原替身的另一儿子作为它的父亲 结点的儿子，究竟是作为左儿子还结点的儿子，究竟是作为左儿子还 是右儿子依原替身结点和其父亲结是右儿子依原替身结点和其父亲结 点的关系而定。点的关系而定。释放原替身结点的空间。释放原替身结点的空间。48 物料管理物料管理第48页 wrxAlgorithms and Data Structures4、二叉排序树的删除操作、二叉排序树的删除操作 FP被删结

50、点被删结点PRPLFP被删结点被删结点CCLPRQQLSSLFSCCLPRQQLSLFCCLPRQQLSSLFPRPL、PR皆皆 空，空，直接删除直接删除。PL或或PR为空，为空，PL为空，删除为空，删除后的情况。后的情况。1.删除法删除法2.删除法删除法49 物料管理物料管理第49页 wrxAlgorithms and Data StructuresStatus DeleteBST(BiTree&T，KeyType key)/若二叉排序树 T 中存在关键字为 key 的结点时，则删除该结点，并返回 TRUE；/否则返回 FALSE。if (!T)return FALSE;/二叉排序树 T 中