《二叉排序树的创建、删除、插入等操作.doc》由会员分享，可在线阅读，更多相关《二叉排序树的创建、删除、插入等操作.doc（44页珍藏版）》请在金锄头文库上搜索。
1、人生旅程，坎坎坷坷，创业之路，艰难曲折；人生苦短，生活不易，工作繁重，请允许我借此机会我提议两个愿望：淮阴工学院算法设计技能训练实习报告题目： 二叉排序树的创建、插入、 删除 系 （院）: 计算机工程学院 专 业： 计算机科学与技术 班 级： 计算机3123 学 号： 1121321124 姓 名： 单永明 指导教师： 刘作军/寇海州 学年学期: 2014 2015 学年 第 1 学期算法设计技能训练任务书课题名称设计目的1、 通过算法设计技能训练，深入理解算法设计的意义和重要性，更好地掌握 算法设计的知识。2、 能够针对某一具体问题，设计算法进行解决。3、 锻炼实践动手能力，提高解决问题的能
2、力。实验环境硬件：1、PC机，奔腾以上CPU， 512MB以上内存，80G以上硬盘； 软件：Visual C+编程工具任务要求1.分析问题，给出数学模型，选择数据结构2.设计算法，给出算法描述3.给出源程序清单4.编辑、编译、调试源程序5.撰写课程设计报告工作进度计划序号起止日期工 作 内 容12014.12.20任务下达，查阅文献资料22014.12.252014.12.28总体设计、素材搜集、课题详细设计、调试32014.12.292013.12.31完善设计、撰写报告42014.12.31答辩指导教师（签章）： 年 月 日 目录1、引言42、课程设计的题目和内容52.1课程设计的题目52
3、.2课程设计的内容53、课程设计报告内容63.1课程概述63.2实验内容73.3源程序代码103.4测试用例15实验总结18致谢19参考文献201.引言本算法设计技能训练的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 2、课程设计的题目和内容 2.1课程设计的题目 二叉排序树的基本操作 2.2、课程设计内容 1.用二叉链表作存储结构，2.编写程序实现二叉排序树上的基本操作：3.输入数列生成二叉排序树4.对二叉排序作中序遍历；5.查找二叉排序树6.删除二叉排序树 3、课程设
4、计报告内容3.1课题概述1、问题描述：（需求分析和背景意义） 利用二叉排序树实现一个动态查找表。2、基本要求：（设计阶段，概要设计和详细设计） 实现动态查找表的三种功能：查找、插入、删除。3、测试数据：自行设定。4、实现提示： （1）初始，二叉排序树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。每次插入或删除一个结点后，应更二叉排序树的显示。 （2）二叉排序树的显示可采用凹入表现形式，也可以采用图形界面画出树行。 （3）教科书已给出查找和插入算法，本题重点在于对删除算法的设计和实现。假设要删除关键字为x的结点。如果x不在叶子结点上，则用它的左子树中最大值或右子
5、树中的最小值取代x。如此反复取代，直到删除动作传递到某个叶子结点。删除叶子结点时，若需要进行平衡交换，可采用插入的平衡变换的反变换（如，左子树变矮对应右子树长高）。 3.2实验内容：二叉排序树。任意给定一组数据，设计一个算法，建立一棵二叉排序树，对它进行查找、插入、删除等操作。1.实验说明：二叉排序树存储结构如下：typedef struct tree/声明树的结构 struct tree *left; /存放左子树的指针struct tree *right; /存放又子树的指针KeyType key; /存放节点的内容二叉排序树插入算法伪代码如下：1. 若root是空树，则将结点s作为根结点
6、插入；否则2. 若s-dataroot-data，则把结点s插入到root的左子树中；否则3. 把结点s插入到root的右子树中。二叉排二叉排序树中删除一个结点f的孩子p算法伪代码如下：1. 若结点p是叶子，则直接删除结点p； 2. 若结点p只有左子树，则只需重接p的左子树； 若结点p只有右子树，则只需重接p的右子树； 3. 若结点p的左右子树均不空，则 3.1 查找结点p的右子树上的最左下结点s以及结点s的双亲结点par；3.2 将结点s数据域替换到被删结点p的数据域；3.3 若结点p的右孩子无左子树，则将s的右子树接到par的右子树上；否则，将s的右子树接到结点par的左子树上；3.4 删
7、除结点s；2.实验分析：a. 主程序 从建树开始，依次输入你的关键字并以-1结束。将你的关键字插入二叉排序树中，并中序输出创建过程。并对你的树执行下列操作：插入，删除，查找。程序的主要流程图见图2-1： 否是开始建树： 依次输入n个关键字 插入二叉排序树中 中序输出创建过程删除任意结点插入一个结点查找关键字中序输出操作后二叉排序树是否继续结束 2-13.主要模块： 1）主函数模块 Main()建立n个关键字的二叉排序树并输出；从二叉树排序树T中删除任意结点,其关键字为key；在二叉树排序树T中，插入一个结点t,其关键字为key；在二叉排序树T中递归查找关键字等于 key2 的数据元素；2）创建
8、二叉排序树模块BiTree CreatBST(int n)建立n个关键字的二叉排序树； 从键盘输入调建立n个关键字依次用InsertBST1（插入函数）； 返回根结点T； 输出过程； 3）删除模块DeleteNode(BiTree &T, int x)从二叉树排序树T中删除任意结点,其关键字为x； 可以实现删除根结点、叶子结点以及其它任意结点的功能； 4）插入模块void InsertBST1(BiTree &T,BiTNode *s)在二叉树排序树T中，插入一个结点s(递归算法)； 被CreatBST函数调用； 5）查找模块BiTree searchBST1(BiTree T,TElemTy
9、pe key)在根指针T所指二叉排序树中递归查找关键字等于 key 的数据元素； 若成功，返回指向该数据元素结点的指针； 否则返回空指针；3.3.源程序代码：#includeusing namespace std;typedef int KeyType;typedef struct tree/声明树的结构 struct tree *left; /存放左子树的指针struct tree *right; /存放又子树的指针KeyType key; /存放节点的内容 BSTNode, * BSTree; /声明二叉树的链表BSTree insertBST(BSTree tptr,KeyType ke
10、y)/ 在二叉排序树中插入结点 /若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回BSTree f,p=tptr; /p的初值指向根结点while(p) /查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲if(p-key=key) /树中已有key，无须插入return tptr;f=p; /f保存当前查找的结点，即f是p的双亲p=(keykey)?p-left:p-right; p=(BSTree )malloc(sizeof(BSTNode); /生成新结点p-key=key; p-left=p-right=NULL;if(tptr=NULL) /原树为空，
11、新插入的结点为新的根tptr=p;elseif(keykey)f-left=p;elsef-right=p;return tptr;BSTree createBST()/建立二叉树 BSTree t=NULL; /根结点KeyType key;cinkey;while(key!=-1)t=insertBST(t,key);cinkey;return t;void inorder_btree(BSTree root)/ 中序遍历打印二叉排序树BSTree p=root;if(p!=NULL) inorder_btree(p-left );cout keyright );int searchBST(BSTree t,KeyType key)/查找if(key=t-key)return 1;if(t=NULL)return 0;if(keykey)return searchBST(t-left,key);elsereturn searchBST(t-right,key);BSTree deleteBST(BSTree tptr,KeyType key)/删除 BSTree p,tmp,parent=NULL; p=tptr; while(p) if(p-key=key) b
