数据结构课程设计报告(2013江苏大学版本)

1江苏大学数据结构——课程设计学院：计算机科学与通信工程学院班级：软件1001学号：3100608024姓名：张建彬2011-12-302班级：软件1001姓名：张建彬学号：3100608024完成日期：2011-12-30题目：二叉排序树的建立、插入、删除和查找给出一组关键值，建立相应的二叉排序树，完成：（1）结点的删除操作。要求可以实现删除根节点叶子结点以及其他任意结点的功能；（2）插入一个新结点的操作；（3）对给定的值在二叉排序树进行查找；（4）随时显示操作结果。一.需求分析：1.运行环境MicrosoftVisualStudio20082.程序所实现的功能：主菜单的调用及跳出主菜单；二叉排序树的建立；数值的插入、删除及查找；3.程序的输入，包含输入的数据格式及说明：序列输入为整型，菜单输入为字符型；4.程序的输出，程序输出形式：以序列形式输出；5.测试数据，如果程序输入的数据量比较大，需要给出测试数据：67、78、5、45、34、90、89、33、12、6二.设计说明1.算法设计的思想：首先，用结构体定义了树的结点；然后，定义二叉排序树类，在类公有函数中定义建树函数voidcreat(void)、中序遍历输出函数voiddesplayinorder(void)、先序遍历输出函数voiddesplaypreorder(void)、后序遍历输出函数voiddesplaypostorder(void)、插入函数treeNode*InsertA(intnumber)、查找函数treeNode*searchTree(intkey)、删除函数treeNode*deleteTree（intkey）以及主菜单函数charmainmenu()最后，分别写出各函数；2.程序的主要流程图3成功失败不存在存在存在此数不存在3.程序的主要模块，要求对主要流程图中出现的模块进行说明：1）建树模块voidBiSortTree::creat(void){cout请输入正整数，建立一棵二叉排序树(以-1作为结束):endl;cout输入序列：endl;Head=NULL;intnumber;cinnumber;while(number!=-1)//若无输入结束信号{Head=InsertB(Head,number);cinnumber;}}说明：利用二叉排序树的插入算法，可以很方便的建立二叉排序树。从空的二叉排序树开始，一个主菜单选择1选择2选择3选择4选择0Create（）中序遍历先序遍历后序遍历返回主菜单查找函数查找成功查找失败插入函数中序遍历先序遍历后序遍历返回主菜单删除函数中序遍历先序遍历后序遍历返回主菜单查找失败，删除失败中序遍历先序遍历后序遍历跳出主菜单Therehasnodenumber中序遍历先序遍历后序遍历4结点一个结点逐步插入，从而建立起最终的二叉排序树。2）查找模块treeNode*BiSortTree::search(treeNode*head,intkey){if(head==NULL){cout查找失败;coutendl;returnNULL;}//查找失败if(head-key==key){cout查找成功;coutendl;returnhead;}//查找成功else{if(keyhead-key)//左子树上的递归查找returnsearch(head-left,key);else//右子树上的递归查找returnsearch(head-right,key);}}说明：在二叉排序树上进行查找的过程，是从根结点开始，沿某一个分支逐层向下进行比较判等的过程，这是一个递归的过程。设要在二叉排序树中查找关键字为key的结点，查找过程从根结点开始，如果根指针为null，则查找不成功；否则给定值key与根结点的关键字进行比较：如果给定值等于根结点的关键字，则查找成功，返回查找成功信息，并报告查找的结点地址；如果给定值等于根结点的关键字，则在根结点的左子树上递归查找；否则，在根结点的右子树上递归查找。3）插入模块treeNode*BiSortTree::InsertB(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=InsertB(head-left,number);elseif(p-keyhead-key)//否则放在右子树上head-right=InsertB(head-right,number);else{couttherehasnodenumberendl;}returnhead;//返回根节点的关键字5}}说明：为了向二叉排序树中插入一个新元素，必须检查这个元素在二叉排序树中是否已经存在。因此，在插入之前首先在二叉排序树中检查待插入的数据元素，如果查找成功，说明树中已经存在这个数据元素，则不再插入；如果查找不成功，说明树中不存在关键字等于给定值的数据元素，则吧新元素插到查找操作失败的地方。4）删除模块treeNode*BiSortTree::deleteTree(intkey){treeNode*p;p=NULL;p=search(Head,key);if(p==NULL)//删除失败{cout删除失败;coutendl;returnHead;}if(p==Head){Head=NULL;}else{treeNode*parent;parent=searchParent(Head,p);if(p-left==NULL&&p-right==NULL)//叶子节点{if(parent-left==p){parent-left=NULL;}//若相等则置为空else{parent-right=NULL;}//若相等则置为空}else//非叶子节点{if(p-right==NULL)//该节点没有右孩子{if(parent-left==p){parent-left=p-left;}else{parent-right=p-left;}}else//该点有左右孩子6{treeNode*rightMinSon,*secondParent;//secondParent为右子树中的最小节点的父亲rightMinSon=searchMinRight(p-right);secondParent=searchParent(p-right,rightMinSon);secondParent-left=rightMinSon-right;if(p-right==rightMinSon)//右子树中的最小节点的父亲为p{p-right=rightMinSon-right;}p-key=rightMinSon-key;}}}returnp;}说明：如果被删除的数据元素是叶子，则只需将其双亲的指向它的指针置空，再释放该数据元素的存储空间即可；如果被删除的数据元素只有左子树而没有右子树，则可以用它的左孩子顶替它的位置，再释放该数据元素的存储空间即可；如果被删除的数据元素只有右子树而没有左子树，则可以用它的右孩子顶替它的位置，再释放该数据元素的存储空间即可；如果被删除的数据元素左右子树都存在，则有两种处理方法：其一，可以在它的右子树中寻找关键字值最小的数据元素（中序遍历中的第一个被访问的数据元素）X，用X的值代替被删除数据元素的值，再来删除数据元素X（X没有左子树）；其二，可以在它的左子树中寻找关键字值最大的数据元素（中序遍历中的最后一个被访问的数据元素）X，用X的值代替被删除数据元素的值，再来删除数据元素X（X没有右子树）；5）主菜单模块charBiSortTree::mainmenu(){charn;cout***********************二叉排序树*************************endl;cout-------------------------------------------------------------------endl;cout--------------------------------------------------------------------------endl;cout1.建立二叉排序树endl;cout2.查找endl;cout3.插入endl;cout4.删除endl;cout0.退出系统endl;cout---------------------------------------------------------------------------endl;cout--------------------------------------------------------------------endl;cout请选择功能按钮：;cinn;returnn;7}说明：根据个人所需要的操作选择按钮；三、上机结果及体会1.输出结果输入原数据：67、78、5、45、34、90、89、33、12、61）建立二叉树2）查找模块A查找存在的数B查找不存在的数83）插入模块A插入已存在的数B插入不存的数94）删除模块A删除存在的数B删除不存在的数5）退出系统102.实际完成情况说明a.能实现二叉树的建立,查找，插入，删除及中序，先序，后序遍历b.适用于整型数据。3.上机过程中出现的问题及其解决方法a.开始时主菜单中我定义的按钮为int类型，当我输入字符类型时无法执行，后来我将其改成字符类型就不再出现问题。b.开始时我选择删除操作时，输入不存在的输系统提示写入发生冲突，后来我在删除函数中添加返回值就正确了。4.收获及体会此次课程设计让我对二叉树以及二叉排序树的操作有了更深的了解。还让我学会了虚心请教。由此我还看到了自己的不足，输入程序时太过粗心，出现很多小错误，以及对知识点掌握不透彻。为此更确定了上课应该认真听讲的重要性。四.参考文献：《数据结构——C++实现》11附录：源程序//1.cpp:定义控制台应用程序的入口点。#includestdafx.h#includeiostreamusingnamespacestd;typedefstructTreeNode//-----------------------------------------定义结点{intkey;//关键字structTreeNode*left;structTreeNode*right;//左右孩子指针域}treeNode;classBiSortTree//-------------------------------------------二叉排序树定义{public:charmainmenu();//主菜单voidcreat(void);//建立二叉树voiddesplayinorder(void);//中序输出这个树voiddesplaypreorder(void);//先序输出这个树voiddesplaypostorder(void);//后序输出这个树treeNode*deleteTree(intkey);//在树中删除一个值treeNode*InsertA(intnumber);//在树中插入一个值treeNode*searchTree(intkey);//在树中查找一个值~BiSortTree();//析构函数private:treeNode*InsertB(treeNode*head,intnumber);插入操作treeNode*search(treeNode*head,int