二叉排序树实验报告.doc

数 据 结 构实验报告实验名称：_二叉排序树_学生姓名：_班 级：_班内序号：_学 号：_日 期：_1实验要求根据二叉排序树的抽象数据类型的定义，使用二叉链表实现一个二叉排序树。二叉排序树的基本功能：1.二叉排序树的建立2.二叉排序树的查找3.二叉排序树的插入4.二叉排序树的删除5.二叉排序树的销毁6.其他：自定义操作编写测试main()函数测试二叉排序树的正确性2. 程序分析2.1 存储结构 二叉链表 2.2 程序流程 (或程序结构、或类关系图等表明程序构成的内容，一般为流程图等) 2.2.1.流程2.1 关键算法分析 查找BiNode* Search(BiNode* R,int key) if(R=NULL) return NULL; if(R-data=key) return R; if(R-datarch,key); if(R-datakey) return Search(R-lch,key);删除void Delete(BiNode* &R)BiNode* q=new BiNode;BiNode *s=new BiNode;if(R-lch=NULL)q=R;R=R-rch;delete q;else if(R-rch=NULL)q=R;R=R-lch;delete q;elseq=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;delete s;void Deletedata(BiNode* &R, int key)if(R=NULL) return;if(R-data=key) Delete(R);else if(R-datakey) Deletedata(R-lch,key);else Deletedata(R-rch,key);首先先要定位到要删除的节点，不断递归调用deletedata这个函数，找到数值与需要删除节点的数值相等的节点时，调用delete这个函数。删除节点时需要分析三种情况。1）.若该节点为叶子节点，则直接删除；2）.若该节点无左子树，则其双亲节点直接与其右子树根节点连接，再删除该节点；3）.若该节点有左子树，则其左子树的最右节点数值直接覆盖该节点数值，再删除最后节点。算法时间复杂度：O（n2）插入void Insert(BiNode* &R,BiNode* S)if(R=NULL) R=S;if(R-datadata) Insert(R-rch,S);if(R-dataS-data) Insert(R-lch,S);二叉树的建立BiNode* Create(int data,int n)BiNode* R=new BiNode;R=NULL;for(int i=0;idata=datai;Insert(R,Q);return R;2.4 其他特殊情况处理：若文件里元素为空，不存在任何元素，则无法完成建树，选择查找操作时也会提示无元素；另外，若查找不存在的元素是，最后查找到空节点也会提示无此元素。程序运行结果分析总结4.1实验的难点和关键点 本实验的难点和关键点主要在删除元素上，为了保持二叉排序树的有序性。删除特定节点是要分三种情况讨论 1）.若该节点为叶子节点，则直接删除；2）.若该节点无左子树，则其双亲节点直接与其右子树根节点连接，再删除该节点；3）.若该节点有左子树，则其左子树的最右节点数值直接覆盖该节点数值，再删除最后节点。4.2心得体会 通过这次试验让我进一步对树的应用有了进一步的了解，同时对查找这种基本数据操作有了较深刻的认识.同时在二叉排序树的删除操作的代码编写时，让我明白了不同情况的不同处理方式。养成了更严谨的编写代码的思维方式。附：程序代码#include#includeusing namespace std;class BiNodepublic:int data;BiNode* lch;BiNode* rch; BiNode():lch(NULL),rch(NULL);BiNode* Search(BiNode* R,int key) if(R=NULL) cout无查询结果data=key) return R; if(R-datarch,key); if(R-datakey) return Search(R-lch,key);void Insert(BiNode* &R,BiNode* S)if(R=NULL) R=S;if(R-datadata) Insert(R-rch,S);if(R-dataS-data) Insert(R-lch,S);BiNode* Create(int data,int n)BiNode* R=new BiNode;R=NULL;for(int i=0;idata=datai;Insert(R,Q);return R;void Delete(BiNode* &R)BiNode* q=new BiNode;BiNode *s=new BiNode;if(R-lch=NULL)q=R;R=R-rch;delete q;else if(R-rch=NULL)q=R;R=R-lch;delete q;elseq=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;delete s;void Deletedata(BiNode* &R, int key)if(R=NULL) return;if(R-data=key) Delete(R);else if(R-datakey) Deletedata(R-lch,key);else Deletedata(R-rch,key);void Deleteall(BiNode* &R,int data,int n)for(int i=0;in;i+)Deletedata(R,datai);void main()int data200;BiNode *Root;Root=NULL;ifstream ifile(D:/TEST/data.txt);int i=0,n=0;cout从文件读入数据如下：datai)coutdatai ;i+;n+;Root=Create(data,n);while(1)coutchoice; while(choice!=1&choice!=2&choice!=3&choice!=4&choice!=5) coutchoice;switch(choice)case 1: cout请输入查找的数据n;BiNode* R;R=Search(Root,n);if(R-lch!=NULL)cout该数据节点左孩子数据为lch-datarch!=NULL)cout该数据节点右孩子数据为rch-datalch=NULL&R-rch=NULL)cout该数据节点为叶子节点;break; case 2: cout请输入插入数据t; BiNode* w=new BiNode; w-data=t; Insert(Root,w); cout插入成功endl; cout目前关键码为：; for(int i=0;in;i+) coutdatai ; coutt endl; break; case 3: int k; cout请输入删除数据s; for(k=0;kn;k+) if(datak=s) break; if(k=n)cout该数据不存在e