二叉排序树的创建、删除、插入等操作 2

1、武汉工程大学计算机科学与工程学院成绩评定表类 别评分标准分值得分合计上机表现积极出勤、遵守纪律 认真完成实验任务30分报告质量程序代码规范、功能正确 填写内容完整、体现收获70分说明：评阅教师：日期：年月日成绩评定表类评分标准分值得分I合计数据结构实验报告专业班级09计算机工程01实验地点419学生学号0905080116指导教师蔡琼学生姓名沈亮实验时间实验项目查找技术综合应用实验类别操作性（）验证性（）设计性（）综合性（Y）其它（）实 验 步 目 求的及 要（1）熟练掌握查找的常用算法；（2）熟练设计和应用查找算法解决比较简单的实际问题。实验内容：二叉排序树。任意给定一组数据，设计一个算法，

2、建立一棵二叉排序树，对它进行查找、 插入、删除等操作。实验说明：二叉排序树存储结构如下：typedef struct BiTNode / 结点结构struct BiTNode *lchild, *rchild;/左右孩子指针 BiTNode, *BiTree;二叉排序树插入算法伪代码如下:若root是空树，则将结点s作为根结点插入；否则若s-dataroot-data，则把结点s插入到root的左子树中；否则把结点s插入到root的右子树中。二叉排序树中删除一个结点f的左孩子结点p算法伪代码如下:若结点p是叶子，则直接删除结点p；若结点p只有左子树，则只需重接p的左子树；若结点p只有右子树，则

3、只需重接p的右子树；若结点p的左右子树均不空，则3.1查找结点p的右子树上的最左下结点s以及结点s的双亲结点par；3.2将结点s数据域替换到被删结点p的数据域；3.3若结点p的右孩子无左子树，则将s的右子树接到par的右子树上;否则，将s的右子树接到结点par的左子树上；3.4删除结点s；实验分析：程序的主要流程图:主要模块：主函数模块Main()(建立n个关键字的二叉排序树并输出；从二叉树排序树T中删除任意结点，其关键字为key；在二叉树排序树T中，插入一个结点t,其关键字为key；在二叉排序树T中递归查找关键字等于key2的数据元素；创建二叉排序树模块BiTree CreatBST(in

4、t n)(建立n个关键字的二叉排序树；从键盘输入调建立n个关键字依次用InsertBST1 (插入函数);返回根结点T；输出过程；删除模块DeleteNode(BiTree &T, int x)(从二叉树排序树T中删除任意结点，其关键字为x；可以实现删除根结点、叶子结点以及其它任意结点的功能；插入模块void InsertBST1(BiTree &T,BiTNode *s)(在二叉树排序树T中，插入一个结点s (递归算法)；被CreatBST函数调用；查找模块BiTree searchBST1(BiTree T,TElemType key)(在根指针T所指二叉排序树中递归查找关键字等于key的

5、数据元素;若成功，返回指向该数据元素结点的指针；否则返回空指针；源程序代码：#include using namespace std; typedef int KeyType;typedef struct tree/声明树的结构struct tree *left;/存放左子树的指针struct tree *right; /存放又子树的指针KeyType key;存放节点的内容 BSTNode, * BSTree;/声明二叉树的链表BSTree insertBST(BSTree tptr,KeyType key)/ 在二叉排序树中插入结点/若二叉排序树tptr中没有关键字为key的结点，则插入，

6、否则直接返回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) /原树为空，新插入的结点为新的根tptr=p; elseif(keykey)f-left=p;els

7、ef-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

8、 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)break;parent=p;p=(keykey)?p-left:p-right;if(!p) return NULL;tmp=p;if(!p-right&!p-left) /*p 的左右子树都为空*/if(!par

9、ent)/要删根，须修改根指针tptr=NULL;else if(p=parent-right)parent-right=NULL;elseparent-left=NULL;free(p);else if(!p-right) /p的右子树为空，则重接p的左子树p=p-left;if(!parent)/要删根，须修改根指针tptr=p;else if(tmp=parent-left)parent-left=p;elseparent-right=p;free(tmp);else if(!p-left)的左子树为空，则重接p的左子树p=p-right;if(!parent)/要删根，须修改根指针tp

10、tr=p;else if(tmp=parent-left)parent-left=p;elseparent-right=p;free(tmp);else if(p-right&p-left)/p有左子树和右子树，用p的后继覆盖p然后删去后继另有方法：用p的前驱覆盖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;elseparent-right=NULL;free(p);return

11、 tptr;int main()KeyType key;int flag,test;char cmd;BSTree root;docoutnnendl;couttt* 请选择你要执行的操作：*endl;coutnendl;couttt C.创建一棵二叉排序树n”;couttt E.结束本程序 n”;coutnntt*endl;flag=0;do if(flag!=0)coutcmd;flag+;while(cmd!=c&cmd!=C&cmd!=a&cmd!=A);if(cmd=c|cmd=C)cout ”请输入你所要创建的二叉树的结点的值，以-1结束：n”;root=createBST();d

12、o flag=0;coutnn 中序遍历二叉树：endl;inorder_btree(root);coutnendl;couttt*请选择你要对这棵二叉树所做的操作：*，endl; .查找你想要寻找的结点 .插入你想要插入的结点D.删除你想要删除的结点Q.结束对这棵二叉树的操作couttt* *endl;couttt*endl;couttt*endl;couttt*endl;couttt*endl;couttt*endl;t 一 _ j t$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ s + + + + + + + + + + + + + ,4* $ $ $ $ $ $ $ $

13、$ $ $ $ $ $ $ ”一 一 11couttt*endl;doif(flag!=0)cout选择操作错误！请重新选择！ n;fflush(stdin);scanf(%c”,&cmd);flag+;while(cmd!=s&cmd!=S&cmd!=i&cmd!=T&cmd!=d&cmd!=D&cmd!=q& &cmd!=Q);switch(cmd)case s:case S:coutkey;test=searchBST(root,key);if(test=0)coutn对不起，你所查找的结点key不存在!”；elsecoutn 成功找到结,0nkey”;break;case i:case

14、 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 0;实验内容测试用例:程序运行时菜单显示如下: D:Program FilesMi:crosoft Visual StudicMyPrqjectsyue

15、sefuDebugyuesef. 8=1*请选择你要执彳亍的操作:上创建一愣二叉排序树 E.结束本程序Cdrrr当输入的二叉树序列为：2,6,9,8,4时，创建二叉排序树，并输出结果如下:或青选择你要对这棵二叉树所做的操作SID:XJOOOIlOtJOCO I回|密.rrrD:Program FilesMicrosoft Visual StudioMyPrqjectsyuesefuDebugyuese.中序遍历二叉树!2468作 点点占睇 结结结的 的的的树 找入除叉1.查找9结点时，运行结果如下:D:Program FilesMicrosoft Visu-al StudicMyPrqject

16、-syuesefuDebugTUese.NMKJOOCMXJCXXMXJCXKMXKXKXXNJCKJCXNXKJCXNMXJCXNMKJCXXMXJCXKMXJCX请输入你要查找结点的关键字=9成功我到结点 9中序遍历二叉树：24689请选择你要对这棵二叉树所做的操作:MtM-KM-K作 点点占漆 结结结的 的的的树 找入除叉 寻5二 要要幕 想想想&: 找入篷rrr删除结点6时运行结果如下:wD:Prgram FilesMicrosoft Vrsu-al StudicMyPrqjecrt:syuesefuDebugyuese.请输入你要删除结点的关键字，6成功删除结点6中序遍历二叉树;2489请选择你要对这棵二叉树所做的操作:s.ID.*Q.要要膏想想想这=对找入董I麴融作rrr插入结点7时运行结果如下:D Program FilesMicrosoft Visu-al StudicMyPrqjectsyues请输入你要插入结点的关键字二7中序谒历二叉树;2478*请选择你要对这棵二叉树所做的操作:55rrr结结结的 的的的树 找A除叉 寻费一 要要幕 想想想这 对 找入纂实验内容实验总结：通过这次的实验，我认识到：仅仅掌握