二叉排序树的操作

《数据结构》课程设计说明书题目二叉排序树的操作学号姓名李阳指导教师康懿日期2015年7月2日2内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目二叉排序树的操作指导教师康懿时间2015年春学期第17周至第19周一、教学要求1.掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。二叉排序树的操作以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。要求设计类（或类模板）来描述二叉排序树，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：创建二叉排序树输出二叉排序树在二叉排序树中查找给定值在二叉排序树中插入新结点在二叉排序树中删除给定值并设计主函数测试该类（或类模板）。三、设计要求及成果1.分析课程设计题目的要求2.写出详细设计说明3.编写程序代码，调试程序使其能正确运行4.设计完成的软件要便于操作和使用5.设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1.根据平时上机考勤、表现和进度，教师将每天点名和检查2.根据课程设计完成情况，必须有可运行的软件。3.根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4.根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1．《数据结构（C语言版）》严蔚敏、吴伟民主编清华大学出版社2004.112．《数据结构课程设计案例精编（用C/C++描述）》，李建学等编著，清华大学出版社2007.23.《数据结构:用面向对象方法与C++语言描述》，殷人昆主编，清华大学出版社2007.63目录第1章需求分析....................................................4第2章总体设计....................................................4第3章抽象数据类型定义............................................43.1TreeNode抽象数据类型的设计......................53.2BiSortTree抽象数据类型的设计...............................5第4章详细设计....................................................54.1工程视图....................................................54.2类图视图....................................................54.3函数的调用关系..............................................64.4主程序流程图................................................64.5主要算法的流程图............................................8第5章测试........................................................9第6章总结.......................................................10附录：程序代码....................................................114第1章需求分析每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。二叉排序树的操作以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。要求设计类（或类模板）来描述二叉排序树，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：创建二叉排序树输出二叉排序树在二叉排序树中查找给定值在二叉排序树中插入新结点在二叉排序树中删除给定值并设计主函数测试该类（或类模板）。通过算法的需求，确定算法的主要模块（建立并输出二叉树、插入结点、删除结点、查找结点、以及主函数模块）对各模块再进行函数的选取与构造，以及变量的控制等。最后，再将各模块结合，形成完整的算法，注意全局变量的选择。第2章总体设计总体设计框架图，如图2.1所示：图2.1总体设计框架第3章抽象数据类型定义系统功能输出查找插入删除5定义格式如下：3.1TreeNode抽象数据类型的设计图3.1TreeNode抽象数据类型设计视图3.2BiSortTree抽象数据类型的设计图3.2BiSortTree抽象数据类型的设计第4章详细设计4.1工程视图图4.1工程视图4.2类图视图6图4.2类图视图4.3函数的调用关系如下图4.3所示：图4.3函数的调用关系4.4主程序流程图主程序流程图如图4.4所示：main（）主程序输出二叉树tree.desplayTree()查找tree.insertTree(number)删除tree.deleteTree(number)插入tree.insertTree(number)7图4.4主程序流程图程序的主要模块，对流程图中出现的模块说明*建立二叉树，用插入函数依次插入用户输入的序列，最后再中序遍历并输出显示*结点的插入，运用递归算法进行结点的插入*结点的删除，是该算法中较为复杂的一个模块，需判定用户输入的结点是根，还是叶子，这关系到删除的结点在序列中的位置*结点的查找，在根指针所指二叉排序树中递归查找关键字等于key的数据元素；开始建立二叉树：①依次输入n个关键字②插入二叉排序树中③显示操作结果结点的插入结点的删除结点的查找显示操作结果是否继续结束8若成功，返回指向该数据元素结点的指针；否则返回空指针；4.5主要算法的流程图主要所发流程图如图4.5所示：图4.5主程序算法流程图开始初始化空节点，叶子节点读入字符是否为-1输入结束继续输入，输入-1为止按主函数菜单进行插入，删除，查找，输出等操作tree.insertTree(number)tree.deleteTree(number)tree.searchTree(number)tree.desplayTree()结束程序9第5章测试图5.1二叉树的建立图5.2输出二叉树图5.3在二叉树中插入节点10图5.4在已输入的二叉树中查找节点图5.5在已输入的二叉树中删除节点第6章总结在本次数据结构课程设计的过程中，深刻的意识到对程序代码设计的难度，不过这更让我在这过程中受益匪浅，体味到计算机系的高大上。这个课程具有很高的挑战性和耐性。进行程序设计的时候注意模块的划分，从各个小模块开始进行设计。设计的过程中，出现了很多错误，但是通过查找资料，反复对比内容的真伪性，找出了问题的所在，并最终解决了问题，这过程中结果并不显的那么重要，因为有艰辛的过程，所以才显出了结果的完美，它让我更加坚定了在这条路上的努力发展。11附录：程序代码#includeiostream#includevectorusingnamespacestd;typedefstructTreeNode//声明树的结构{intkey;//存放关键字structTreeNode*left;//存放左子树的指针structTreeNode*right;//存放右子树的指针}treeNode;classBiSortTree{public:BiSortTree(void);voiddesplayTree(void);//显示这个树voidinsertTree(intkey);//在树中插入一个结点intdeleteTree(intkey);//在树中删除一个结点treeNode*searchTree(intkey);//在树中查找一个结点~BiSortTree();private:treeNode*buildTree(treeNode*head,intnumber);//建立一个树treeNode*search(treeNode*head,intkey);//查找treeNode*searchParent(treeNode*head,treeNode*p);//查找出p的父亲节点的指针treeNode*searchMinRight(treeNode*head);//找到右子树中最小的节点voidshowTree(treeNode*head);//显示voiddestroyTree(treeNode*head);//删除treeNode*Head;};BiSortTree::BiSortTree(){cout建立一棵二叉排序树,请输入你要建树的所有数(以-1作为结束标志!):endl;//循环输入调用BuildTree函数Head=NULL;intnumber;cinnumber;while(number!=-1)12{Head=buildTree(Head,number);cinnumber;}}treeNode*BiSortTree::buildTree(treeNode*head,intnumber)//建立一个二叉排序树{treeNode*p;p=newtreeNode;p-key=number;p-left=p-right=NULL;if(head==NULL){returnp;}else{if(p-keyhead-key)head-left=buildTree(head-left,number);elsehead-right=buildTree(head-right,number);returnhead;}}voidBiSortTree::insertTree(intkey)//插入一个结点通过调用BuildTree函数{Head=buildTree(Head,key);}treeNode*BiSortTree::searchTree(intkey)//查找一个节点调用search函数{returnsearch(Head,key);}treeNode*BiSortTree::search(treeNode*head,intkey)//查找13{if(head==NULL)returnNULL;if(head-key==key)returnhead;else{if(keyhead-key)//如果所要查找的关键字的值小于根结点则在其左子树中查找否则在其右子树中查找returnsearch(head-left,key);elsereturnsearch(head-right,key);}}intBiSortTree::deleteTree(intkey)//删除一个结点{treeNode*p;p=NULL;p=search(Head,key);//通过search函数先找到关键字if(p==NULL)//结点为空找不到关键字{coutCan'tfindthekey;}if(p==Head)//如果为头结点则直接删除{Head=NULL;}else//否则分为叶子结点，有孩子的结点和左右孩子都有的结点讨论{treeNode*parent;parent=searchParent(Head,p);if(p-left==NULL&&p-right==NULL)//叶子节点即p的左右子树都为空{if(parent-left==p)//if(!parent){parent-left=NULL;}14else{par