下载文档原格式
数据结构查找实验报告数据结构查找实验报告1·实验目的本实验旨在研究不同的查找算法在不同数据结构下的性能表现，通过实验结果对比分析，选取最优算法来完成查找操作。
2·实验方法2·1 数据结构选择在本实验中，我们选择了常用的数据结构进行查找性能比较，包括线性表、二叉树、哈希表等。
2·2 查找算法选择我们选择了以下常用的查找算法进行实验：●顺序查找●二分查找●插值查找●二叉查找树●平衡二叉查找树（AVL树）●哈希查找3·实验过程3·1 实验环境设置首先，我们需要搭建合适的实验环境，包括编程语言选择、编译器、开发环境等。
在本次实验中，我们选择了C++编程语言，并使用了Visual Studio 2019作为开发环境。
3·2 实验步骤为了比较各个查找算法的性能，我们按照以下步骤进行实验： 1·创建用于查找的数据结构，并初始化数据集合。
2·调用每个查找算法进行查找，并记录查找耗时。
3·分析实验结果，比较各个查找算法的性能。
4·实验结果与分析根据实验步骤中记录的各个查找算法的耗时，我们得到了以下结果：●对于小规模数据集，顺序查找表现较好。
●对于有序数据集，二分查找和插值查找表现最佳。
●对于动态数据集，哈希表的查找效率最高。
5·结论根据实验结果与分析，我们得出以下结论：●不同的数据结构适用于不同的查找需求。
●在静态有序数据集中，二分查找和插值查找是较好的选择。
●在动态数据集中，哈希表具有较高的查找效率。
附件：附件1：实验数据集附件2：查找算法代码法律名词及注释：1·数据结构：数据之间的组织方式和关系，使得我们可以高效地进行数据的存储和操作。
2·查找算法：在给定某个目标值的情况下，在给定数据集内寻找目标值的算法。
3·顺序查找：逐个比较目标值和数据集内的元素，直到找到目标值或者遍历完整个数据集。
数据结构实验报告实验第四章：实验: 简单查找算法一．需求和规格说明：查找算法这里主要使用了顺序查找，折半查找，二叉排序树查找和哈希表查找四种方法。
由于自己能力有限，本想实现其他算法，但没有实现。
其中顺序查找相对比较简单，折半查找参考了书上的算法，二叉排序树查找由于有之前做二叉树的经验，因此实现的较为顺利，哈希表感觉做的并不成功，感觉还是应该可以进一步完善，应该说还有很大的改进余地。
二．设计思想：开始的时候提示输入一组数据。
并存入一维数组中，接下来调用一系列查找算法对其进行处理。
顺序查找只是从头到尾进行遍历。
二分查找则是先对数据进行排序，然后利用三个标志，分别指向最大，中间和最小数据，接下来根据待查找数据和中间数据的比较不断移动标志，直至找到。
二叉排序树则是先构造，构造部分花费最多的精力，比根节点数据大的结点放入根节点的右子树，比根节点数据小的放入根节点的左子树，其实完全可以利用递归实现，这里使用的循环来实现的，感觉这里可以尝试用递归。
当二叉树建好后，中序遍历序列即为由小到大的有序序列，查找次数不会超过二叉树的深度。
这里还使用了广义表输出二叉树，以使得更直观。
哈希表则是利用给定的函数式建立索引，方便查找。
三．设计表示：四．实现注释：其实查找排序这部分和前面的一些知识联系的比较紧密，例如顺序表的建立和实现，顺序表节点的排序，二叉树的生成和遍历，这里主要是中序遍历。
应该说有些知识点较为熟悉，但在实现的时候并不是那么顺利。
在查找到数据的时候要想办法输出查找过程的相关信息，并统计。
这里顺序查找和折半查找均使用了数组存储的顺序表，而二叉树则是采用了链表存储的树形结构。
为了直观起见，在用户输入了数据后，分别输出已经生成的数组和树。
折半查找由于只能查找有序表，因此在查找前先调用函数对数据进行了排序。
在查找后对查找数据进行了统计。
二叉排序树应该说由于有了之前二叉树的基础，并没有费太大力气，主要是在构造二叉树的时候，要对新加入的节点数据和跟数据进行比较，如果比根节点数据大则放在右子树里，如果比根节点数据小则放入左子树。
数据结构查找算法实验报告关键信息项：1、实验目的2、实验环境3、实验原理4、实验内容5、实验步骤6、实验结果7、结果分析8、遇到的问题及解决方法9、总结与体会1、实验目的11 熟悉常见的数据结构查找算法，如顺序查找、二分查找、哈希查找等。
111 掌握不同查找算法的基本原理和实现方法。
112 通过实验比较不同查找算法的性能，分析其时间复杂度和空间复杂度。
113 培养运用数据结构和算法解决实际问题的能力。
2、实验环境21 操作系统：具体操作系统名称211 编程语言：具体编程语言名称212 开发工具：具体开发工具名称3、实验原理31 顺序查找顺序查找是从数据结构的一端开始，依次逐个比较给定的关键字与数据元素的关键字，直到找到相等的元素或者遍历完整个数据结构为止。
其时间复杂度为 O(n)。
32 二分查找二分查找要求数据结构是有序的。
通过不断将待查找区间缩小为原来的一半，直到找到目标元素或者确定目标元素不存在。
其时间复杂度为 O(log n)。
33 哈希查找哈希查找通过哈希函数将关键字映射到一个特定的位置，然后在该位置进行比较。
如果发生冲突，则通过解决冲突的方法来查找目标元素。
其平均时间复杂度接近O(1)，但在最坏情况下可能会退化为O(n)。
4、实验内容41 实现顺序查找算法，并对给定的无序数组进行查找操作。
411 实现二分查找算法，并对给定的有序数组进行查找操作。
412 实现哈希查找算法，并对给定的数据集进行查找操作。
413 对不同规模的数据集，分别使用上述三种查找算法进行查找，并记录查找时间和比较次数。
5、实验步骤51 顺序查找算法实现511 定义顺序查找函数，接受数组和要查找的关键字作为参数。
512 从数组的第一个元素开始，逐个比较关键字与数组元素的关键字。
513 如果找到相等的元素，返回该元素的索引；如果遍历完数组都未找到，返回－1。
52 二分查找算法实现521 定义二分查找函数，接受有序数组、要查找的关键字以及数组的起始和结束索引作为参数。
一、实验目的1. 理解并掌握几种常见查找算法的基本原理和实现方法。
2. 比较不同查找算法的时间复杂度和空间复杂度。
3. 通过实验验证查找算法的效率和适用场景。
二、实验内容本次实验主要涉及以下查找算法：1. 顺序查找法2. 二分查找法3. 散列查找法三、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发环境：PyCharm四、实验步骤1. 实现顺序查找法2. 实现二分查找法3. 实现散列查找法4. 编写测试程序，分别对三种查找算法进行测试5. 比较三种查找算法的性能五、实验结果与分析1. 顺序查找法（1）实现代码```pythondef sequential_search(arr, target):for i in range(len(arr)):if arr[i] == target:return ireturn -1```（2）测试程序```pythonarr = [5, 3, 8, 6, 2, 7, 4, 9, 1]target = 6print("顺序查找结果：", sequential_search(arr, target))```（3）分析顺序查找法的时间复杂度为O(n)，空间复杂度为O(1)。
当数据量较大时，查找效率较低。
2. 二分查找法（1）实现代码```pythondef binary_search(arr, target):left, right = 0, len(arr) - 1while left <= right:mid = (left + right) // 2if arr[mid] == target:return midelif arr[mid] < target:left = mid + 1else:right = mid - 1return -1```（2）测试程序```pythonarr = [1, 2, 3, 4, 5, 6, 7, 8, 9]target = 6print("二分查找结果：", binary_search(arr, target))```（3）分析二分查找法的时间复杂度为O(log2n)，空间复杂度为O(1)。
查找算法实验报告查找算法实验报告一、引言查找算法是计算机科学中的一个重要概念，它在数据处理和信息检索中起着关键作用。
本实验旨在探究几种常见的查找算法，并对它们的性能进行比较和分析。
二、顺序查找算法顺序查找算法是最简单直观的一种查找方法，它逐个比较待查找元素与数据集中的元素，直到找到匹配项或遍历完整个数据集。
该算法的时间复杂度为O(n)，其中n为数据集的大小。
尽管顺序查找算法的效率较低，但在小规模数据集或无序数据集中仍然具有一定的应用价值。
三、二分查找算法二分查找算法是一种高效的查找算法，它要求数据集必须是有序的。
该算法通过将待查找元素与数据集的中间元素进行比较，从而将查找范围缩小一半。
如果中间元素与待查找元素相等，则查找成功；如果中间元素大于待查找元素，则在左半部分继续查找；如果中间元素小于待查找元素，则在右半部分继续查找。
通过不断缩小查找范围，二分查找算法的时间复杂度为O(log n)，其中n为数据集的大小。
二分查找算法在大规模有序数据集中具有较高的查找效率。
四、哈希查找算法哈希查找算法是一种基于哈希表的查找方法，它通过将待查找元素映射到哈希表中的一个位置，从而快速定位到目标元素。
哈希查找算法的时间复杂度为O(1)，即常数级别。
然而，哈希查找算法对哈希函数的选择和哈希冲突的处理有一定的要求。
如果哈希函数设计不合理或哈希冲突过多，可能会导致查找效率下降。
五、比较与分析在本实验中，我们对上述三种查找算法进行了性能比较和分析。
实验结果表明，在小规模数据集或无序数据集中，顺序查找算法的效率较高；而在大规模有序数据集中，二分查找算法的效率最高。
哈希查找算法虽然具有常数级别的时间复杂度，但在哈希函数和哈希冲突处理上需要额外的开销。
因此，在实际应用中，我们需要根据具体需求选择合适的查找算法。
六、实验总结通过本次实验，我们深入了解了查找算法的原理和应用。
顺序查找算法、二分查找算法和哈希查找算法各具特点，在不同场景下有不同的优劣势。
数据结构实验七查找在计算机科学中，数据结构是组织和存储数据的方式，而查找则是在给定的数据结构中寻找特定元素的操作。
本次实验七的重点就是深入研究查找这一重要的数据处理操作。
查找操作在我们日常生活和计算机程序中无处不在。
想象一下在电话簿中查找一个朋友的号码，或者在图书馆的书架中寻找一本书，这都是查找的实际应用场景。
在计算机程序中，当我们需要从大量数据中快速找到所需的信息时，高效的查找算法就显得至关重要。
常见的查找算法有顺序查找、二分查找、哈希查找等。
顺序查找是最简单直接的方法，它从数据结构的起始位置开始，依次比较每个元素，直到找到目标元素或者遍历完整个数据结构。
这种方法适用于数据量较小或者数据未排序的情况。
让我们通过一个简单的示例来理解顺序查找。
假设有一个整数数组5, 3, 8, 2, 9，我们要查找数字 8。
从数组的第一个元素 5 开始，依次与8 进行比较。
当比较到第三个元素时，找到了目标数字 8，查找结束。
虽然顺序查找的思路简单，但在数据量较大时，它的效率相对较低。
与顺序查找不同，二分查找则要求数据是有序的。
它通过不断将待查找的区间一分为二，逐步缩小查找范围，从而提高查找效率。
还是以整数数组为例，比如 2, 4, 6, 8, 10 要查找数字 6。
首先，比较中间元素 6 和目标数字 6，正好相等，查找成功。
如果要查找的数字小于中间元素，则在左半区间继续查找；如果大于中间元素，则在右半区间查找。
二分查找的效率在有序数据中表现出色。
然而，如果数据经常变动，需要频繁进行插入和删除操作，维护数据的有序性可能会带来较大的开销。
哈希查找则是另一种常见的查找方法。
它通过一个哈希函数将关键字映射到一个特定的位置，从而实现快速查找。
哈希函数的设计至关重要，如果设计不当，可能会导致大量的冲突，影响查找效率。
在实际应用中，选择合适的查找算法取决于多种因素，如数据的规模、数据的分布特征、查找的频繁程度以及对时间和空间复杂度的要求等。
数据结构的查找算法在计算机科学中，数据结构是用于组织和存储数据的一种方式。
查找算法是数据结构中的重要部分，它用于在数据集合中搜索特定元素或信息。
本文将介绍几种常见的数据结构查找算法，包括线性查找、二分查找、哈希查找以及树结构的查找算法。
1. 线性查找线性查找是一种简单直观的查找方法，适用于无序的数据集合。
其基本思想是从数据集合的第一个元素开始逐个比较，直到找到目标元素或者遍历完整个数据集合。
由于线性查找需要遍历所有元素，所以时间复杂度为O(n)，其中n为数据集合的大小。
2. 二分查找二分查找是一种高效的查找算法，但它要求数据集合中的元素必须有序。
具体实现方式是将数据集合分为两半，然后与目标元素进行比较，不断缩小查找范围，直到找到目标元素或者确定目标元素不存在。
由于每次都将查找范围减小一半，所以时间复杂度为O(log n)，其中n为数据集合的大小。
3. 哈希查找哈希查找利用哈希函数将目标元素映射到哈希表中的特定位置，从而快速定位目标元素。
哈希表是一种以键-值对形式存储数据的数据结构，可以快速插入和删除元素，因此在查找时具有良好的性能。
哈希查找的时间复杂度为O(1)，但在处理哈希冲突时可能会影响性能。
4. 树结构的查找算法树是一种常见的数据结构，其查找算法主要包括二叉搜索树、平衡二叉搜索树以及B树和B+树。
二叉搜索树是一种有序的二叉树，左子树的所有节点值都小于根节点，右子树的所有节点值都大于根节点。
通过比较目标元素与节点的值，可以快速定位目标元素。
平衡二叉搜索树是为了解决二叉搜索树在某些情况下可能出现的退化情况，通过旋转操作保持树的平衡性。
B树和B+树是一种多路搜索树，它们可以减少磁盘I/O操作，适用于大规模数据的查找。
综上所述，数据结构的查找算法是计算机科学中的重要内容。
不同的查找算法适用于不同的场景，选择合适的算法可以提高查找效率。
在实际应用中，需要根据数据集合的特点及查找需求来选择合适的算法。
数据结构查找实验报告数据结构查找实验报告1. 简介查找是计算机科学中一种常见的操作，它用于在一组数据中快速定位特定的元素。
数据结构是计算机存储、组织数据的方式，可以有效地支持查找操作。
本实验报告将介绍查找算法的原理和实现，以及实验结果的分析和总结。
2. 查找算法2.1 顺序查找顺序查找是一种简单直观的查找算法，它从数据集的第一个元素开始逐个比较，直至找到目标元素或遍历完所有元素。
顺序查找的时间复杂度为O(n)，其中n是数据集的大小。
2.2 二分查找二分查找是一种高效的查找算法，它要求数据集必须是有序的。
它通过将数据集分成两部分，并与目标元素进行比较，以确定目标元素所在的区间，然后在该区间内继续二分查找，直至找到目标元素或确定目标元素不存在。
二分查找的时间复杂度为O(log n)，其中n是数据集的大小。
2.3 插值查找插值查找是对二分查找的一种改进，它根据目标元素的估计位置来确定比较的起始位置。
它适用于数据集分布均匀的情况，可以进一步减少查找的次数。
插值查找的时间复杂度为O(log(log n))。
3. 实验结果本次实验我们使用了三种查找算法（顺序查找、二分查找和插值查找）在不同大小的数据集上进行了性能测试。
实验结果如下表所示：---- 数据集大小 ---- 顺序查找时间（ms） ---- 二分查找时间（ms） ---- 插值查找时间（ms） ---------------------------------------------------------------------------------------------- 1000 ---- 10 ---- 2 ---- 1 -------- 10000 ---- 100 ---- 4 ---- 2 -------- 100000 ---- 1000 ---- 6 ---- 3 -------- 1000000 ---- 10000 ---- 8 ---- 4 ----从实验结果可以看出，随着数据集的增大，顺序查找的时间成正比增加，而二分查找和插值查找的时间相对较稳定。
数据结构实验课教案一、实验目的与要求1. 实验目的(1) 掌握数据结构的基本概念和算法。
(2) 培养实际操作能力，巩固课堂所学知识。
(3) 提高编程技能，为实际项目开发打下基础。
2. 实验要求(1) 严格按照实验指导书进行实验。
(2) 实验前认真预习，充分理解实验内容。
(3) 实验过程中积极思考，遇到问题及时解决。
(4) 按时完成实验，积极参与讨论与交流。
二、实验环境与工具1. 实验环境(1) 操作系统：Windows 7/8/10或Linux。
(2) 编程语言：C/C++、Java或Python。
(3) 开发工具：Visual Studio、Eclipse、IntelliJ IDEA或PyCharm。
2. 实验工具(1) 文本编辑器或集成开发环境（IDE）。
(2) 版本控制系统（如Git）。
(3) 在线编程平台（如LeetCode、牛客网）。
三、实验内容与安排1. 实验一：线性表的基本操作(1) 实现线性表的顺序存储结构。
(2) 实现线性表的插入、删除、查找等基本操作。
(3) 分析线性表的时间复杂度。
2. 实验二：栈与队列的基本操作(1) 实现栈的顺序存储结构。
(2) 实现队列的顺序存储结构。
(3) 实现栈与队列的进栈、出栈、入队、出队等基本操作。
(4) 分析栈与队列的时间复杂度。
3. 实验三：线性表的链式存储结构(1) 实现单链表的结构。
(2) 实现单链表的插入、删除、查找等基本操作。
(3) 分析单链表的时间复杂度。
4. 实验四：树与二叉树的基本操作(1) 实现二叉树的结构。
(2) 实现二叉树的遍历（前序、中序、后序）。
(3) 实现二叉搜索树的基本操作。
(4) 分析树与二叉树的时间复杂度。
5. 实验五：图的基本操作(1) 实现图的邻接矩阵存储结构。
(2) 实现图的邻接表存储结构。
(3) 实现图的深度优先搜索（DFS）和广度优先搜索（BFS）。
(4) 分析图的时间复杂度。
四、实验评价与成绩评定1. 实验评价(1) 代码质量：代码规范、注释清晰、易于维护。
实验七查找一、实验目的1. 掌握查找的不同方法，并能用高级语言实现查找算法；2. 熟练掌握二叉排序树的构造和查找方法。
3. 熟练掌握静态查找表及哈希表查找方法。
二、实验内容设计一个读入一串整数，然后构造二叉排序树，进行查找。
三、实验步骤1. 从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中。
2. 在二叉排序树中查找某一结点。
3.用其它查找算法进行排序（课后自己做）。
四、实现提示1. 定义结构typedef struct node{ int key;int other;struct node *lchild, *rchild;} bstnode;void inorder ( t ){ if (t!=Null){ inorder(t→lchild);printf(“%4d”, t→key);inorder(t→rchild);} }bstnode *insertbst(t, s)bstnode *s, *t;{ bstnode *f, *p;p=t;while(p!=Null){ f=p;if (s→key= =p→key) return t;if (s→key<p→key) p=p→lchild;elsep=p→rchild;}if(t= =Null) return s;if (s→key<f→key) f→lchild=s;elsef→rchild=s;return t;}bstnode *creatord( ){ bstnode *t, * s;int key;t=Null;scanf(“%d”,&key);while (key!=0){ s=malloc(sizeof (bitree));s→key=key;s→lchild=Null;s→rchild=Null;scanf(“%d”, &data);s→other=data;t=insertbst(t, s);scanf(“%d”,&key);}return t;}五、思考与提高1. 用其它的查找方法完成该算法。
2.比较各种算法的时间及空间复杂度。
六、完整参考程序1.折半查找#include <conio.h>#include <stdio.h>#define MAX 30 //定义有序查找表的最大长度typedef struct{char elem[MAX]; //有序查找表int length; //length指示当前有序查找表的长度}SSTable;void initial(SSTable &); //初始化有序查找表int search(SSTable,int); //在有序查找表中查找元素void print(SSTable); //显示有序查找表中所有元素void main(){SSTable ST; //ST为一有序查找表int ch,loc,flag=1;char j;initial(ST); //初始化有序查找表while(flag){ printf("请选择：\n");printf("1.显示所有元素\n");printf("2.查找一个元素\n");printf("3.退出\n");scanf(" %c",&j);switch(j){case '1':print(ST); break; //显示所有元素case '2':{printf("请输入要查找的元素：");scanf("%d",&ch); //输入要查找的元素的关键字loc=search(ST,ch); //查找if(loc!=0) printf("该元素所在位置是：%d\n",loc); //显示该元素位置else printf("%d 不存在!\n",ch);//当前元素不存在break;}default:flag=0;}}printf("程序运行结束!按任意键退出!\n");}void initial(SSTable &v){//初始化有序查找表int i;printf("请输入静态表的元素个数："); //输入有序查找表初始化时的长度scanf("%d",&v.length);printf("请从小到大输入%d个元素（整形数）：\n",v.length);getchar();for(i=1;i<=v.length;i++) scanf("%d",&v.elem[i]); //从小到大输入有序查找表的各元素}int search(SSTable v,int ch){//在有序查找表中查找ch的位置，成功返回其位置，失败返回0int low,high,mid;low=1;high=v.length; //置区间初值while(low<=high){mid=(low+high)/2;if(v.elem[mid]==ch) return mid; //找到待查元素else if(v.elem[mid]>ch) high=mid-1; //继续在前半区间进行查找else low=mid+1; //继续在后半区间进行查找}return 0; //找不到时，i为0}void print(SSTable v) //显示当前有序查找表所有元素{int i;for(i=1;i<=v.length;i++) printf("%d ",v.elem[i]);printf("\n");}2.二叉排序树的建立与查找#include <conio.h>#include <math.h>#include <stdio.h>#include <stdlib.h>enum BOOL{False,True};typedef struct BiTNode //定义二叉树节点结构{char data; //为了方便，数据域只有关键字一项struct BiTNode *lchild,*rchild; //左右孩子指针域}BiTNode,*BiTree;BOOL SearchBST(BiTree,char,BiTree,BiTree&); //在二叉排序树中查找元素BOOL InsertBST(BiTree &,char); //在二叉排序树中插入元素BOOL DeleteBST(BiTree &,char); //在二叉排序树中删除元素void Delete(BiTree &); //删除二叉排序树的根结点void InorderBST(BiTree); //中序遍历二叉排序树，即从小到大显示各元素void main(){BiTree T,p;char ch,keyword,j='y';BOOL temp;T=NULL;while(j!='n'){printf("1.display\n");printf("2.search\n");printf("3.insert\n");printf("4.delete\n");printf("5.exit\n");scanf(" %c",&ch); //输入操作选项switch(ch){case '1':if(!T) printf("The BST has no elem.\n");else {InorderBST(T);printf("\n");}break;case '2':printf("Input the keyword of elem to be searched(a char):");scanf(" %c",&keyword); //输入要查找元素的关键字temp=SearchBST(T,keyword,NULL,p);if(!temp) printf("%c isn't existed!\n",keyword); //没有找到else printf("%c has been found!\n",keyword); //成功找到break;case '3':printf("Input the keyword of elem to be inserted(a char):");scanf(" %c",&keyword); //输入要插入元素的关键字temp=InsertBST(T,keyword);if(!temp) printf("%c has been existed!\n",keyword); //该元素已经存在else printf("Sucess to inert %c!\n",keyword); //成功插入break;case '4':printf("Input the keyword of elem to be deleted(a char):");scanf(" %c",&keyword); //输入要删除元素的关键字temp=DeleteBST(T,keyword);if(!temp) printf("%c isn't existed!\n",keyword); //该元素不存在else printf("Sucess to delete %c\n",keyword); //成功删除break;default: j='n';}}printf("The program is over!\nPress any key to shut off the window!\n");getchar();getchar();}void InorderBST(BiTree T){//以中序方式遍历二叉排序树T，即从小到大显示二叉排序树的所有元素if(T->lchild) InorderBST(T->lchild);printf("%2c",T->data);if(T->rchild) InorderBST(T->rchild);}BOOL SearchBST(BiTree T,char key,BiTree f,BiTree &p){//在根指针T所指二叉排序树中递归的查找其关键字等于key的元素，若查找成功//则指针p指向该数据元素，并返回True,否则指针指向查找路径上访问的最后一//个结点并返回False,指针f指向T的双亲，其初始调用值为NULLBOOL tmp1,tmp2;tmp1=tmp2=False;if(!T) {p=f;return False;} //查找不成功else if(key==T->data) {p=T;return True;} //查找成功else if(key<T->data) tmp1=SearchBST(T->lchild,key,T,p); //在左子树中继续查找else tmp2=SearchBST(T->rchild,key,T,p); //在右子树中继续查找if(tmp1||tmp2) return True; //若在子树中查找成功，向上级返回True else return False; //否则返回False}BOOL InsertBST(BiTree &T,char e){//当二叉排序树T中不存在元素e时，插入e并返回True,否则返回False BiTree p,s;if(!SearchBST(T,e,NULL,p)) //查找不成功{s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p) T=s; //被插结点*s为新的根结点else if(e<p->data) p->lchild=s; //被插结点*s为左孩子else p->rchild=s; //被插结点*s为右孩子return True; //成功插入}else return False; //树中已存在关键字为e的数据元素}BOOL DeleteBST(BiTree &T,char key){//若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点//并返回True,否则返回FalseBOOL tmp1,tmp2;tmp1=tmp2=False;if(!T) return False; //不存在关键字等于key的数据元素else{if(key==T->data) {Delete(T); return True;}//找到关键字等于key的数据元素并删除它else if(key<T->data) tmp1=DeleteBST(T->lchild,key); //继续在左子树中删除else tmp2=DeleteBST(T->rchild,key); //继续在右子树中删除if(tmp1||tmp2) return True; //在子树中删除成功，返回Trueelse return False; //不存在该元素}}void Delete(BiTree &p){//在二叉排序树中删除结点p,并重接它的左或右子树BiTree s,q;if(!p->rchild) //右子树空，只需重接它的左子树{q=p;p=p->lchild;free(q);}else if(!p->lchild) //左子树空，只需重接它的右子树{q=p;p=p->rchild;free(q);}else //左右子树均不空{q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;} //转左，然后向右走到尽头p->data=s->data; //s指向被删结点的“前驱”if(q!=p) q->rchild=s->rchild; //重接*q的右子树else q->lchild=s->lchild; //重接*q的左子树free(s);}}。
