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

实用文档数据结构实验报告实验名称：______二叉排序树___________学生：____________________班级：_______________班序号：_______________________学号：________________日期：________________

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