数据结构课程设计报告(2013江苏大学版本)(共17页).doc

《数据结构课程设计报告(2013江苏大学版本)(共17页).doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告(2013江苏大学版本)(共17页).doc（17页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上江苏大学数据结构 课程设计学院：计算机科学与通信工程学院班级：软件1001 学号： 姓名：张建彬 2011-12-30班级：软件1001 姓名：张建彬 学号： 完成日期：2011-12-30 题目：二叉排序树的建立、插入、删除和查找给出一组关键值，建立相应的二叉排序树，完成：（1）结点的删除操作。要求可以实现删除根节点叶子结点以及其他任意结点的功能；（2）插入一个新结点的操作；（3）对给定的值在二叉排序树进行查找；（4）随时显示操作结果。一. 需求分析：1. 运行环境Microsoft Visual Studio 20082. 程序所实现的功能：主菜单的调用及跳出主菜

2、单；二叉排序树的建立；数值的插入、删除及查找；3. 程序的输入，包含输入的数据格式及说明：序列输入为整型，菜单输入为字符型；4. 程序的输出，程序输出形式：以序列形式输出；5. 测试数据，如果程序输入的数据量比较大，需要给出测试数据：67、78、5、45、34、90、89、33、12、6二.设计说明1 . 算法设计的思想： 首先，用结构体定义了树的结点；然后，定义二叉排序树类，在类公有函数中定义建树函数void creat(void)、中序遍历输出函数void desplayinorder(void)、先序遍历输出函数void desplaypreorder(void)、后序遍历输出函数voi

3、d desplaypostorder(void)、插入函数treeNode* InsertA( int number)、查找函数treeNode* searchTree(int key)、删除函数treeNode* deleteTree（int key）以及主菜单函数char mainmenu()最后，分别写出各函数；2.程序的主要流程图主菜单选择0 选择1选择4选择2选择3 Create（）跳出主菜单删除函数插入函数查找函数 Therehasnode number中序遍历 成功 失败 不存在 存在 存在此数 不存在中序遍历中序遍历查找失败，删除失败查找失败查找成功先序遍历先序遍历先序遍历中序

4、遍历中序遍历后序遍历后序遍历后序遍历先序遍历先序遍历返回主菜单后序遍历后序遍历返回主菜单返回主菜单3.程序的主要模块，要求对主要流程图中出现的模块进行说明：1）建树模块void BiSortTree:creat(void)cout请输入正整数，建立一棵二叉排序树(以-1 作为结束): endl;cout输入序列：number;while(number!=-1)/若无输入结束信号Head=InsertB(Head,number);cinnumber; 说明：利用二叉排序树的插入算法，可以很方便的建立二叉排序树。从空的二叉排序树开始，一个结点一个结点逐步插入，从而建立起最终的二叉排序树。2）查找模

5、块treeNode* BiSortTree:search(treeNode* head ,int key) if(head=NULL)cout查找失败;coutkey=key)cout查找成功;coutendl;return head;/查找成功else if(keykey )/左子树上的递归查找return search( head-left,key);else/右子树上的递归查找return search(head-right,key);说明：在二叉排序树上进行查找的过程，是从根结点开始，沿某一个分支逐层向下进行比较判等的过程，这是一个递归的过程。设要在二叉排序树中查找关键字为key的结点

6、，查找过程从根结点开始，如果根指针为null，则查找不成功；否则给定值key与根结点的关键字进行比较：如果给定值等于根结点的关键字，则查找成功，返回查找成功信息，并报告查找的结点地址；如果给定值等于根结点的关键字，则在根结点的左子树上递归查找；否则，在根结点的右子树上递归查找。3）插入模块treeNode* BiSortTree:InsertB(treeNode* head,int number) treeNode *p; p=new treeNode;p-key=number;p-left =p-right=NULL;if(head=NULL)return p;else if(p-key k

7、ey)/如果插入的关键字小于根节点的关键字，则将其放到其左子树上head-left=InsertB(head-left,number);else if(p-key head-key)/否则放在右子树上head-right=InsertB(head-right,number);else coutthere has node numberendl; return head;/返回根节点的关键字说明：为了向二叉排序树中插入一个新元素，必须检查这个元素在二叉排序树中是否已经存在。因此，在插入之前首先在二叉排序树中检查待插入的数据元素，如果查找成功，说明树中已经存在这个数据元素，则不再插入；如果查找不成

8、功，说明树中不存在关键字等于给定值的数据元素，则吧新元素插到查找操作失败的地方。4）删除模块treeNode* BiSortTree:deleteTree(int key)treeNode *p;p=NULL;p=search(Head,key);if(p=NULL)/删除失败cout删除失败;coutleft=NULL&p-right=NULL)/叶子节点 if(parent-left=p)parent-left=NULL;/若相等则置为空elseparent-right=NULL;/若相等则置为空else/非叶子节点if(p-right=NULL)/该节点没有右孩子if(parent-le

9、ft=p)parent-left=p-left ;elseparent-right=p-left;else/该点有左右孩子treeNode * rightMinSon,* secondParent;/secondParent为右子树中的最小节点的父亲rightMinSon=searchMinRight(p-right);secondParent=searchParent(p-right ,rightMinSon);secondParent-left=rightMinSon-right;if(p-right=rightMinSon)/右子树中的最小节点的父亲为pp-right=rightMinS

10、on-right ; p-key=rightMinSon-key ; return p;说明：如果被删除的数据元素是叶子，则只需将其双亲的指向它的指针置空，再释放该数据元素的存储空间即可；如果被删除的数据元素只有左子树而没有右子树，则可以用它的左孩子顶替它的位置，再释放该数据元素的存储空间即可；如果被删除的数据元素只有右子树而没有左子树，则可以用它的右孩子顶替它的位置，再释放该数据元素的存储空间即可；如果被删除的数据元素左右子树都存在，则有两种处理方法：其一，可以在它的右子树中寻找关键字值最小的数据元素（中序遍历中的第一个被访问的数据元素）X，用X的值代替被删除数据元素的值，再来删除数据元素X

11、（X没有左子树）；其二，可以在它的左子树中寻找关键字值最大的数据元素（中序遍历中的最后一个被访问的数据元素）X，用X的值代替被删除数据元素的值，再来删除数据元素X（X没有右子树）；5）主菜单模块char BiSortTree:mainmenu()char n;cout *二叉排序树* endl;cout -endl;cout-endl;cout 1.建立二叉排序树 endl;cout 2.查找 endl; cout 3.插入 endl;cout 4.删除 endl;cout 0.退出系统 endl; cout-endl; cout -endl; coutn;return n ;说明：根据个人所

12、需要的操作选择按钮；三、上机结果及体会1.输出结果 输入原数据：67、78、5、45、34、90、89、33、12、61）建立二叉树2）查找模块A查找存在的数B查找不存在的数3）插入模块A插入已存在的数B插入不存的数4）删除模块A删除存在的数B删除不存在的数5）退出系统2 .实际完成情况说明a. 能实现二叉树的建立,查找，插入，删除及中序，先序，后序遍历b. 适用于整型数据。3. 上机过程中出现的问题及其解决方法a.开始时主菜单中我定义的按钮为int类型，当我输入字符类型时无法执行，后来我将其改成字符类型就不再出现问题。b.开始时我选择删除操作时，输入不存在的输系统提示写入发生冲突，后来我在删

13、除函数中添加返回值就正确了。4.收获及体会此次课程设计让我对二叉树以及二叉排序树的操作有了更深的了解。还让我学会了虚心请教。由此我还看到了自己的不足，输入程序时太过粗心，出现很多小错误，以及对知识点掌握不透彻。为此更确定了上课应该认真听讲的重要性。四.参考文献：数据结构C+实现附录：源程序/ 1.cpp : 定义控制台应用程序的入口点。#include stdafx.h#includeusing namespace std;typedef struct TreeNode /-定义结点int key;/关键字struct TreeNode *left;struct TreeNode *right

14、;/左右孩子指针域treeNode;class BiSortTree /-二叉排序树定义public:char mainmenu(); /主菜单void creat(void); /建立二叉树void desplayinorder(void); /中序输出这个树void desplaypreorder(void);/先序输出这个树void desplaypostorder(void); /后序输出这个树treeNode* deleteTree(int key);/在树中删除一个值treeNode* InsertA( int number);/在树中插入一个值treeNode* searchTr

15、ee(int key);/在树中查找一个值BiSortTree(); /析构函数private:treeNode* InsertB(treeNode* head,int number); 插入操作treeNode* search(treeNode* head ,int key);/查找treeNode* BiSortTree:searchParent(treeNode* head,treeNode* p);/查找出p的父亲节点的指针treeNode* BiSortTree:searchMinRight(treeNode* head);/找到右子树中最小的节点void inorder(treeN

16、ode* head);/中序遍历void preorder(treeNode* head);/ 先序遍历void postorder(treeNode* head);/后序遍历treeNode *Head;void BiSortTree:creat(void)-建立二叉树cout请输入正整数，建立一棵二叉排序树(以-1 作为结束): endl;cout输入序列：number;while(number!=-1)/若无输入结束信号Head=InsertB(Head,number);cinnumber; treeNode* BiSortTree:InsertA(int key)-插入操作return

17、 InsertB(Head,key);treeNode* BiSortTree:InsertB(treeNode* head,int number) treeNode *p; p=new treeNode;p-key=number;p-left =p-right=NULL;if(head=NULL)return p;else if(p-key key)/如果插入的关键字小于根节点的关键字，则将其放到其左子树上head-left=InsertB(head-left,number);else if(p-key head-key)/否则放在右子树上head-right=InsertB(head-ri

18、ght,number);else coutthere has node numberendl; return head;/返回根节点的关键字treeNode* BiSortTree:searchTree(int key)-查找操作return search(Head,key);treeNode* BiSortTree:search(treeNode* head ,int key) if(head=NULL)cout查找失败;coutkey=key)cout查找成功;coutendl;return head;/查找成功else if(keykey )/左子树上的递归查找return search

19、( head-left,key);else/右子树上的递归查找return search(head-right,key);treeNode* BiSortTree:searchParent(treeNode* head,treeNode* p)/查找结点的父亲结点if(head-left=p|head-right=p|head=p|head=NULL)/如果结点的左孩子或右孩子或者为空树或者等于该节点则返回该节点return head;elseif(p-keykey)/若小于则继续查找左孩子的父亲结点return searchParent(head-left ,p);else/若大于则继续查找

20、右孩子的父亲结点return searchParent(head-right ,p);treeNode* BiSortTree:searchMinRight(treeNode* head)/找到右子树中最小的节点if(head-left =NULL|head=NULL)return head;elsereturn searchMinRight(head-left);treeNode* BiSortTree:deleteTree(int key)-删除操作treeNode *p;p=NULL;p=search(Head,key);if(p=NULL)/删除失败cout删除失败;coutleft=

21、NULL&p-right=NULL)/叶子节点 if(parent-left=p)parent-left=NULL;/若相等则置为空elseparent-right=NULL;/若相等则置为空else/非叶子节点if(p-right=NULL)/该节点没有右孩子if(parent-left=p)parent-left=p-left ;elseparent-right=p-left;else/该点有左右孩子treeNode * rightMinSon,* secondParent;/secondParent为右子树中的最小节点的父亲rightMinSon=searchMinRight(p-rig

22、ht);secondParent=searchParent(p-right ,rightMinSon);secondParent-left=rightMinSon-right;if(p-right=rightMinSon)/右子树中的最小节点的父亲为pp-right=rightMinSon-right ; p-key=rightMinSon-key ; return p;void BiSortTree:desplayinorder(void)/-中序遍历的输出inorder(Head);coutleft ) ;coutkeyright) ;void BiSortTree:desplaypreo

23、rder(void)/-先序遍历的输出preorder(Head);coutendl;void BiSortTree:preorder(treeNode* Head) /先序遍历二叉排序树的递归算法 if(Head!=NULL)coutkeyleft ) ;preorder(Head-right) ;void BiSortTree:desplaypostorder(void)/-后序遍历输出树postorder(Head);coutleft ) ;postorder(Head-right) ;coutkey ;BiSortTree:BiSortTree()char BiSortTree:mai

24、nmenu()/-主菜单char n;cout *二叉排序树* endl;cout -endl;cout-endl; cout 1.建立二叉排序树 endl; cout 2.查找 endl; cout 3.插入 endl; cout 4.删除 endl; cout 0.退出系统 endl; cout-endl; cout -endl; coutn; return n ;void main()/-主函数BiSortTree tree;char n;int i;int number;int k=1;while(k=1)n=tree.mainmenu();switch(n) case 1:tree.

25、creat();cout中序遍历序列应为：;tree.desplayinorder();cout先序遍历结果为：;tree.desplaypreorder();cout后序遍历序列应为：;tree.desplaypostorder();break;case 2:couti;coutendl; cout查找结果：;tree.searchTree(i);break;case 3:cout输入要插入的整数：m;tree.InsertA(m); cout插入后的中序遍历序列应为：;tree.desplayinorder(); cout插入后的先序遍历结果为：;tree.desplaypreorder(); cout插入后的后序遍历序列应为;tree.desplaypostorder();break; case 4:cout输入要删除的整数：number;tree.deleteTree(number); cout删除后的中序遍历序列应为：;tree.desplayinorder(); cout删除后的先序遍历结果为：;tree.desplaypreorder(); cout删除后的后序遍历序列应为：;tree.desplaypostorder();break;case0:k=0;break;附录二：流程图专心-专注-专业