二叉排序树的操作.doc

内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目二叉排序树的操作指导教师孙涛时间2011/6/132011/6/23一、教学要求1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。二叉排序树的操作以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。要求设计类（或类模板）来描述二叉排序树，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v 创建二叉排序树v 输出二叉排序树v 在二叉排序树中查找给定值v 在二叉排序树中插入新结点v 在二叉排序树中删除给定值 并设计主函数测试该类（或类模板）。三、设计要求及成果1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行4. 设计完成的软件要便于操作和使用5. 设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1. 根据平时上机考勤、表现和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1数据结构 （C语言版）严蔚敏、吴伟民 主编 清华大学出版社 2004.112数据结构课程设计案例精编（用C/C+描述），李建学 等 编著，清华大学出版社 2007.23.数据结构:用面向对象方法与C+语言描述，殷人昆 主编，清华大学出版社 2007.6内蒙古科技大学本科生课程设计论文题 目：二叉排序树的操作学生姓名：罗芳学 号：0967111248专 业：计算机科学与技术班 级：09-2班指导教师：孙涛 2011年 6月 23日二叉排序树的操作二叉排序树的特点：若它的左子树不为空，则它的左子树上所有结点的值均小于它的根节点；若它的右子树不为空，则它的右子树上所有结点的值均小于它的根节点；它的左右子树也分别为二叉排序树； 二叉排序树的结构不是一次生成的，而是在查找过程中，当树中不存在该关键字时再进行插入。1 各成员函数的基本功能根据二叉排序树的特点，可由如下函数来实现二叉排序树的操作： bool SearchBST(int key,BiNode f,BiNode &p)根据关键字key查找结点，若存在关键字与key相同的结点，则函数的返回值为ture,并使f指向该结点的双亲结点，p指向该结点；若不存在，则函数返回false。void InSertBST(int e)先调用bool SearchBST(int key,BiNode f,BiNode &p函数查找是否已经存在关键字为e的结点，若不存在，则生成一个关键字为e的结点，若存在，则给出提示。void Create()函数通过调用void InSertBST(int e)创建一个个结点，并使得第一个结点为根节点，关键字比第一个结点的小的结点在根节点的左子树上，关键字比根节点的大的结点在根节点的右子树上，从而创建一棵二叉排序树的。void Traverse()函数利用栈来实现二叉排序树的中序遍历，使二叉排序树的关键字从小到大排列输出。在调用void DeleteBST(BiNode &p)前必须调用bool SearchBST(int key,BiNode f,BiNode &p)函数确定关键字为key的结点是否存在，若存在，则删除，若不存在，则给出相应的提示信息。2 各成员函数的具体实现2.1 void Create()生成二叉排序树二叉排序树实在查找过程中动态创建的，所以在Create()函数中，要根据输入的关键字个数m，动态分配m*int大小的内存空间，在输入各个关键字各个关键字，以关键字为形参，调用m次插入函数void BSTree:InSertBST(int e)，逐个生成二叉树的结点，并使得根节点的左子树的关键字都小于根节点右子树的关键字。以输入（23 13 45 21 65 54）为例，生成二叉排序树的过程如图1所示。232313452313214523136521452313546521452313图1 生成二叉排序树2.2 Void InSertBST(int e)函数插入一个新的结点要插入一个新的结点，首先要确定二叉排序树中不存在该关键字的结点，所以先调用bool SearchBST(BiNode B,int key,BiNode f,BiNode &p)。若函数返回值为false，函数中p指向与要插入的关键字大小最接近的叶子结点，生成一个新的结点s并为其分配内存空间，并使得s-data=e，s-lchild=s-rchild=NULL，比较p中data域的值与要插入的关键字key的大小，若keyp-data，则p-rchild=s，若keydata，则p-lchild=s；若函数返回至为true，说明二叉排序树中已经存在关键字为e的结点，则给出提示信息“该关键字已存在！”。由上述插入过程可知，每个新插入的结点都是叶子结点，如图2所示，在图1的基础上插入一个关键字为19的结点。19546521452313546519452113图2 插入结点 图3 删除结点 2.3 void DeleteBST(BiNode &p)函数删除结点在调用删除函数删除节点之前必须要调用bool SearchBST(BiNode B,int key,BiNode f,BiNode &p)函数，因为删除函数的形参是个BiNode类型的值，而我们是根据关键字来删除结点的，调用bool SearchBST(BiNode B,int key,BiNode f,BiNode &p)函数，找到关键字为key的结点p,再用p做形参，执行void DeleteBST(BiNode &p)函数删除结点p。若p-lchild不为空，则执行“q=p;p=p-lchild；delete q;”语句 ，使p的双亲结点指向p的左孩子，再删除pj结点；若p-rchild不为空，则执行“q=p;p=p-rchild；delete q;”语句,使p的双亲结点指向p的右孩子，再删除节点p；若p-lchild、p-rchild均不为空，使q=p;s=p-lchild;，再执行“q=s;s=s-rchild;”直到s-rchild为空，这样就找到了p结点的直接前驱s结点和s的双亲结点q，将s结点的值赋值给p结点，q-rchild赋值给s-lchild，这样就完成了删除操作，如图3所示，在图2的基础上删除关键字为23的结点。2.4 bool BSTree:SearchBST(BiNode B,int key,BiNode f,BiNode &p)函数查找结点bool BSTree:SearchBST(BiNode B,int key,BiNode f,BiNode &p)函数采用递归调用的方式查找结点。并用bool做函数类型，使得其它函数在调用查找函数后能够很简单的根据函数返回值决定下一步操作。函数参数中B为要查找的二叉排序树的根结点，若B=NULL，则直接返回false。key是要查找的关键字，f指向B结点的双亲结点，在第一次调用查找函数时，由于B为根节点，所以f的初值为NULL，p用来返回查找成功后关键字为key的结点。若B-data=key，则将B赋值给p，返回true；若B-datalchild,key,B,p)，即让f指向B结点、B指向B的左孩子结点，再用新f、B的值做参数调用查找函数；若B-datakey，则返回SearchBST(B-rchild,key,B,p)；即让f指向B结点、B指向B的右孩子结点，再用新f、B的值做参数调用查找函数。函数的递归调用一直要到找到关键字为key的结点，返回true，或者在查找了所有结点之后没有找到关键字为key的结点返回false为止。2.5 void Traverse()函数遍历二叉排序树根据二叉排序树的特点：根节点的关键字比左子树的关键字大，比右子树的关键字小，其左右子树又分别是二叉排序树附录：#include#includeusing namespace std;typedef struct BiTreeint data;BiTree *lchild;BiTree *rchild;*BiNode,BiTree;class BSTreeprivate:BiNode T;public: BSTree()delete T; BSTree()T=NULL;BiNode Gethead()return T;void Create(); bool SearchBST(BiNode B,int key,BiNode f,BiNode &p);void InSertBST(int e);void DeleteBST(BiNode &p);void Traverse();bool BSTree:SearchBST(BiNode B,int key,BiNode f,BiNode &p)if(!B)p=f; return false;else if(key=B-data)p=B; return true; else if(keydata)return SearchBST(B-lchild,key,B,p);else return SearchBST(B-rchild,key,B,p);void BSTree:InSertBST(int e)BiNode p,k=T,f=NULL;if(!SearchBST(k,e,f,p)BiNode s=(BiNode)malloc(sizeof(BiTree); s-data=e;s-lchild=s-rchild=NULL;if(!p)T=s;else if (edata)p-lchild=s;elsep-rchild=s;elsecout此关键字已存在！lchild)q=p; p=p-rchild;delete q;else if(!p-rchild)q=p;p=p-lchild;delete q;elseq=p;s=p-lchild;while(s-rchild)q=s;s=s-rchild;p-data=s-data; if(q!=p)q-rchild=s-lchild;else q-lchild=s-lchild;delete s;cout删除后的;void BSTree:Traverse()cout中序遍历结果：;stackbi;BiTree *p;p=T;while(p|!bi.empty()if(p)bi.push(p);p=p-lchild;elsep = bi.top();bi.pop();coutdatarchild;coutendl;void BSTree:Create()int m; coutm;int *s = (int *)malloc(sizeof(int) * m);cout请输入m个数;for(int i=0;isi; InSertBST(si);int main() BSTree B; BiNode p,k,f=NULL; int m,a; char n; B.Create(); B.Traverse(); cout请选择：1 创建二叉排序树 2 查找关键字 3 插入节点 4 删除节点 5退出a; while(a5) if(a=1) B.BSTree(); BSTree B; B.Create(); B.Traverse(); else if(a=2) coutm; if(B.SearchBST(B.Gethead(),m,f,p) cout查找成功！endl; else cout此关键字不存在！已插入！endl; B.InSertBST(m); cout插入后的; B.Trav