北邮数据结构实验—二叉排序树

北京邮电大学信息与通信工程学院第1页数据结构实验报告实验名称：______二叉排序树___________学生姓名：____________________班级：_______________班内序号：_______________________学号：________________日期：________________北京邮电大学信息与通信工程学院第2页1．实验要求根据二叉排序树的抽象数据类型的定义，使用二叉链表实现一个二叉排序树。二叉排序树的基本功能：1.二叉排序树的建立2.二叉排序树的查找3.二叉排序树的插入4.二叉排序树的删除5.二叉排序树的销毁6.其他：自定义操作编写测试main()函数测试二叉排序树的正确性2.程序分析2.1存储结构二叉链表2.2程序流程(或程序结构、或类关系图等表明程序构成的内容，一般为流程图等)2.2.1.流程图DataLchildRchild开始从文件读取原始数据建立排序二叉树北京邮电大学信息与通信工程学院第3页该元素和根节点数据比较大小大小根节点移向右孩子根节点移向左孩子当前根节点是否存在是否该元素节点插入到当前根节点位置是否还剩余元素判断下一个元素是用户输入操作判断操作北京邮电大学信息与通信工程学院第4页查找插入删除销毁退出该元素和当前根节点数据比较大小根节点移向右孩子根节点移向左孩子当前根节点值是否相等大小执行查找操作直到为空节点在该位置插入其节点执行查找操作删除最终节点是否输出该节点情况删除该节点是否销毁完删除下一节点是否销毁完否结束是是北京邮电大学信息与通信工程学院第5页2.2.2.伪代码1.从文件读取待建树元素2.建树，若待插入元素比根节点小，向左子树前进并重复比较左子树根节点，若待插入元素比根节点大，向右子树前进并重复比较右子树根节点，直至找到空节点则插入该元素，不断插入直至不剩下元素。3.用户选择操作。4.若用户选择查找，则现由用户输入待查找数值。从根节点开始比较，若较小则移至左子树，若较大则移至右子树，直至关键码相等，则输出节点情况。5.若用户选择插入，则现由用户输入待插入数值。从根节点开始比较，若较小则移至左子树，若较大则移至右子树，直至到空节点，则插入该元素。6.若用户选择删除，则现由用户输入待删除数值。从根节点开始比较，若较小则移至左子树，若较大则移至右子树，直至关键码相等；1）.若该节点为叶子节点，则直接删除；2）.若该节点无左子树，则其双亲节点直接与其右子树根节点连接，再删除该节点；3）.若该节点有左子树，则其左子树的最右节点数值直接覆盖该节点数值，再删除最后节点。7.若用户选择销毁，则不断执行删除操作直至不剩余节点。8.若用户选择退出，则程序结束。2.3关键算法分析关键代码即删除操作，代码如下：voidDelete(BiNode*&R){BiNode*q=newBiNode;BiNode*s=newBiNode;if(R-lch==NULL){q=R;R=R-rch;deleteq;}elseif(R-rch==NULL){q=R;R=R-lch;deleteq;}else{q=R;s=R-lch;while(s-rch!=NULL){q=s;s=s-rch;}R-data=s-data;if(q!=R)北京邮电大学信息与通信工程学院第6页q-rch=s-lch;elseR-lch=s-lch;deletes;}}voidDeletedata(BiNode*&R,intkey){if(R==NULL)return;if(R-data==key)Delete(R);elseif(R-datakey)Deletedata(R-lch,key);elseDeletedata(R-rch,key);}首先先要定位到要删除的节点，不断递归调用deletedata这个函数，找到数值与需要删除节点的数值相等的节点时，调用delete这个函数。删除节点时需要分析三种情况。1）.若该节点为叶子节点，则直接删除；2）.若该节点无左子树，则其双亲节点直接与其右子树根节点连接，再删除该节点；3）.若该节点有左子树，则其左子树的最右节点数值直接覆盖该节点数值，再删除最后节点。算法时间复杂度：O（n^2）2.4其他特殊情况处理：若文件里元素为空，不存在任何元素，则无法完成建树，选择查找操作时也会提示无元素；另外，若查找不存在的元素是，最后查找到空节点也会提示无此元素。北京邮电大学信息与通信工程学院第7页3.程序运行结果分析4.总结4.1实验的难点和关键点本实验的难点和关键点主要在删除元素上，为了保持二叉排序树的有序性。删除特定节点是要分三种情况讨论1）.若该节点为叶子节点，则直接删除；2）.若该节点无左子树，则其双亲节点直接与其右子树根节点连接，再删除该节点；3）.若该节点有左子树，则其左子树的最右节点数值直接覆盖该节点数值，再删除最后节点。北京邮电大学信息与通信工程学院第8页4.2心得体会通过这次试验让我进一步对树的应用有了进一步的了解，同时对查找这种基本数据操作有了较深刻的认识.同时在二叉排序树的删除操作的代码编写时，让我明白了不同情况的不同处理方式。养成了更严谨的编写代码的思维方式。附：程序代码#includeiostream#includefstreamusingnamespacestd;classBiNode{public:intdata;BiNode*lch;BiNode*rch;BiNode():lch(NULL),rch(NULL){};};BiNode*Search(BiNode*R,intkey){if(R==NULL){cout无查询结果endl;returnNULL;}if(R-data==key)returnR;if(R-datakey)returnSearch(R-rch,key);if(R-datakey)returnSearch(R-lch,key);}voidInsert(BiNode*&R,BiNode*S){if(R==NULL)R=S;if(R-dataS-data)Insert(R-rch,S);if(R-dataS-data)Insert(R-lch,S);}BiNode*Create(intdata[],intn){BiNode*R=newBiNode;R=NULL;for(inti=0;in;i++){BiNode*Q=newBiNode;Q-data=data[i];Insert(R,Q);北京邮电大学信息与通信工程学院第9页}returnR;}voidDelete(BiNode*&R){BiNode*q=newBiNode;BiNode*s=newBiNode;if(R-lch==NULL){q=R;R=R-rch;deleteq;}elseif(R-rch==NULL){q=R;R=R-lch;deleteq;}else{q=R;s=R-lch;while(s-rch!=NULL){q=s;s=s-rch;}R-data=s-data;if(q!=R)q-rch=s-lch;elseR-lch=s-lch;deletes;}}voidDeletedata(BiNode*&R,intkey){if(R==NULL)return;if(R-data==key)Delete(R);elseif(R-datakey)Deletedata(R-lch,key);elseDeletedata(R-rch,key);}voidDeleteall(BiNode*&R,intdata[],intn){北京邮电大学信息与通信工程学院第10页for(inti=0;in;i++){Deletedata(R,data[i]);}}voidmain(){intdata[200];BiNode*Root;Root=NULL;ifstreamifile(D://TEST//data.txt);inti=0,n=0;cout从文件读入数据如下：endl;while(ifiledata[i]){coutdata[i];i++;n++;}Root=Create(data,n);while(1){cout\n请输入进行的操作：\n1.查找\n2.插入\n3.删除\n4.销毁\n5.退出\n;intchoice;cinchoice;while(choice!=1&&choice!=2&&choice!=3&&choice!=4&&choice!=5){cout无该选项，请重新输入;cinchoice;}switch(choice){case1:{cout请输入查找的数据endl;intn;inti;cinn;BiNode*R;R=Search(Root,n);if(R-lch!=NULL){cout该数据节点左孩子数据为R-lch-dataendl;}if(R-rch!=NULL){cout该数据节点右孩子数据为R-rch-dataendl;}if(R-lch==NULL&&R-rch==NULL){cout该数据节点为叶子节点;}break;}case2:{北京邮电大学信息与通信工程学院第11页cout请输入插入数据endl;intt;cint;BiNode*w=newBiNode;w-data=t;Insert(Root,w);cout插入成功endl;cout目前关键码为：;for(inti=0;in;i++){coutdata[i];}couttendl;break;}case3:{intk;cout请输入删除数据endl;ints,judge=1;cins;for(k=0;kn;k++){if(data[k]==s)break;}if(k==n){cout该数据不存在endl;}else{Deletedata(Root,s);cout删除成功;}cout剩余关键码为:;for(intq=0;qn;q++){if(q==k)q++;coutdata[q];}break;}case4:Deleteall(Root,data,n);break;case5:return;}}system(pause);}北京邮电大学信息与通信工程学院第12页