《二叉排序树的创建、删除、插入等操作(共13页).doc》由会员分享，可在线阅读，更多相关《二叉排序树的创建、删除、插入等操作(共13页).doc（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上武 汉 工 程 大 学计算机科学与工程学院数据结构实验报告专业班级09计算机工程01实验地点419学生学号指导教师蔡琼学生姓名沈亮实验时间实验项目查找技术综合应用实验类别操作性（）验证性（ ）设计性（ ）综合性（Y ）其它（ ）实验目的及要求（1）熟练掌握查找的常用算法；（2）熟练设计和应用查找算法解决比较简单的实际问题。成 绩 评 定 表类 别评 分 标 准分值得分合 计上机表现积极出勤、遵守纪律认真完成实验任务30分报告质量程序代码规范、功能正确填写内容完整、体现收获70分说明： 评阅教师： 日 期： 年 月 日实验内容：二叉排序树。任意给定一组数据，设计一个算法
2、，建立一棵二叉排序树，对它进行查找、插入、删除等操作。实验说明：二叉排序树存储结构如下：typedef struct BiTNode / 结点结构 struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;二叉排序树插入算法伪代码如下：1. 若root是空树，则将结点s作为根结点插入；否则2. 若s-dataroot-data，则把结点s插入到root的左子树中；否则3. 把结点s插入到root的右子树中。二叉排序树中删除一个结点f的左孩子结点p算法伪代码如下：1. 若结点p是叶子，则直接删除结点p； 2. 若结点p只有左子树，则只需
3、重接p的左子树； 若结点p只有右子树，则只需重接p的右子树； 3. 若结点p的左右子树均不空，则 3.1 查找结点p的右子树上的最左下结点s以及结点s的双亲结点par；3.2 将结点s数据域替换到被删结点p的数据域；3.3 若结点p的右孩子无左子树，则将s的右子树接到par的右子树上；否则，将s的右子树接到结点par的左子树上；3.4 删除结点s；1.实验分析：程序的主要流程图： 否是开始建树： 依次输入n个关键字 插入二叉排序树中 中序输出创建过程删除任意结点插入一个结点查找关键字中序输出操作后二叉排序树是否继续结束主要模块： 1）主函数模块 Main()建立n个关键字的二叉排序树并输出；从
4、二叉树排序树T中删除任意结点,其关键字为key；在二叉树排序树T中，插入一个结点t,其关键字为key；在二叉排序树T中递归查找关键字等于 key2 的数据元素；2）创建二叉排序树模块BiTree CreatBST(int n)建立n个关键字的二叉排序树； 从键盘输入调建立n个关键字依次用InsertBST1（插入函数）； 返回根结点T； 输出过程； 3）删除模块DeleteNode(BiTree &T, int x)从二叉树排序树T中删除任意结点,其关键字为x； 可以实现删除根结点、叶子结点以及其它任意结点的功能； 4）插入模块void InsertBST1(BiTree &T,BiTNode
5、 *s)在二叉树排序树T中，插入一个结点s(递归算法)； 被CreatBST函数调用； 5）查找模块BiTree searchBST1(BiTree T,TElemType key)在根指针T所指二叉排序树中递归查找关键字等于 key 的数据元素； 若成功，返回指向该数据元素结点的指针； 否则返回空指针；2.源程序代码：#includeusing namespace std;typedef int KeyType;typedef struct tree/声明树的结构 struct tree *left; /存放左子树的指针struct tree *right; /存放又子树的指针KeyType
6、 key; /存放节点的内容 BSTNode, * BSTree; /声明二叉树的链表BSTree insertBST(BSTree tptr,KeyType key)/ 在二叉排序树中插入结点 /若二叉排序树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
7、)malloc(sizeof(BSTNode); /生成新结点p-key=key; p-left=p-right=NULL;if(tptr=NULL) /原树为空，新插入的结点为新的根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)/ 中序遍历打印二
8、叉排序树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;
9、while(p) if(p-key=key) break; parent=p; p=(keykey)?p-left:p-right; if(!p) return NULL; tmp=p; if(!p-right&!p-left) /*p的左右子树都为空*/ if(!parent) /要删根，须修改根指针 tptr=NULL; else if(p=parent-right) parent-right=NULL; else parent-left=NULL; free(p); else if(!p-right) /p的右子树为空，则重接p的左子树 p=p-left; if(!parent) /要删
10、根，须修改根指针 tptr=p; else if(tmp=parent-left) parent-left=p; else parent-right=p; free(tmp); else if(!p-left) /的左子树为空，则重接p的左子树 p=p-right; if(!parent) /要删根，须修改根指针 tptr=p; else if(tmp=parent-left) parent-left=p; else parent-right=p; free(tmp); else if(p-right&p-left) /p有左子树和右子树，用p的后继覆盖p然后删去后继 /另有方法：用p的前驱覆
11、盖p然后删去前驱|合并p的左右子树 parent=p; /由于用覆盖法删根，则不必特殊考虑删根 p=p-right; while(p-left) parent=p; p=p-left; tmp-key=p-key; if(p=parent-left) parent-left=NULL; else parent-right=NULL; free(p); return tptr;int main()KeyType key;int flag,test;char cmd;BSTree root;docoutnnendl;couttt*请选择你要执行的操作:*endl;coutnendl;couttt
12、C.创建一棵二叉排序树n;couttt E.结束本程序n;coutnntt*endl;flag=0;doif(flag!=0)coutcmd;flag+; while(cmd!=c&cmd!=C&cmd!=a&cmd!=A);if(cmd=c|cmd=C)cout请输入你所要创建的二叉树的结点的值，以-1结束：n;root=createBST();doflag=0;coutnn中序遍历二叉树：endl; inorder_btree(root);coutnendl;couttt*请选择你要对这棵二叉树所做的操作:*endl;couttt* *endl;couttt* S.查找你想要寻找的结点 *
13、endl;couttt* I.插入你想要插入的结点 *endl;couttt* D.删除你想要删除的结点 *endl;couttt* Q.结束对这棵二叉树的操作 *endl;couttt* *endl;couttt*endl;doif(flag!=0)cout选择操作错误！请重新选择！n;fflush(stdin);scanf(%c,&cmd);flag+;while(cmd!=s&cmd!=S&cmd!=i&cmd!=I&cmd!=d&cmd!=D&cmd!=q&cmd!=Q);switch(cmd)case s:case S:coutkey;test=searchBST(root,key)
14、;if(test=0)coutn对不起，你所查找的结点 key不存在!;elsecoutn成功找到结点nkey ;break;case i:case I:coutkey;root=insertBST(root,key); /注意必须将值传回根break;case d:case D:coutkey;root=deleteBST(root,key); /注意必须将值传回根if(root=NULL)coutn对不起，你所删除的结点 key 不存在!n;elsecoutn成功删除结点 key ;break;while(cmd!=q&cmd!=Q);while(cmd!=e&cmd!=E);return
15、 0;实 验 内 容3.测试用例：1,程序运行时菜单显示如下： 当输入的二叉树序列为：2,6,9,8,4时，创建二叉排序树，并输出结果如下： 1.查找9结点时，运行结果如下：2.删除结点6时运行结果如下：3.插入结点7时运行结果如下：实 验 内 容4.实验总结：通过这次的实验，我认识到：仅仅掌握课本上的知识是不够的，在实际操作时，常常遇到一些问题，自己看不懂，更无法解决。不过，经过自己不断的思考，尝试着去更改代码中出现的问题。虽然开始很困难，但在老师和同学的帮助下，我逐渐的熟悉了许多操作，为后继工作的顺利进行做了准备。个人的力量是薄弱的，我学会了咨询别人，不再胆怯，不再保守。 在过程中和同学相互讨论，询问老师，不断进步。也许，我们可以说，编一个程仅仅是开始，调试和运行相比之下更难。实践中收获的远比想象的多。 看到自己完成了所要求的任务，有一种无法用言语来形容的欣慰之感，这也是无法从学习书本知识中得到的。专心-专注-专业