数据结构课设

1、课程设计报告排序二叉树 完成日期：2015/01/03目录一、需求分析1. 运行环境；2. 程序所实现的功能；3. 程序的输入：4. 程序的输出：5. 测试数据，6. 合作人及其分工二、设计说明1. 算法设计的思想；2. 主要的数据结构设计说明；3. 程序的主要流程图；4. 程序的主要模块，；5. 程序的主要函数及其伪代码说明 .6. 合作人设计分工。三、上机结果及体会1. 合作人编码分工；2. 实际完成的情况说明；3. 程序的性能分析；4. 打印程序运行时的初值和运行结果，画出相应的图示；5. 上机过程中出现的问题及其解决方案；6. 程序中可以改进的地方说明；7. 收获及体会；8. 源程序清

2、单并附上注释。四、参考文献1、 需求分析1.运行环境 a软件环境操作系统：windows 7 编译器 microsoft visual studio 2010 b硬件环境联想 n480 2.程序所实现的功能1. 创建二叉树：（1） 按提示信息输入一组关键字值，并建立相应的二叉排序树。（2） 按照先序遍历方式显示建立的二叉排序树。（3） 按照中序遍历方式显示建立的二叉排序树。（4） 按照后序遍历方式显示建立的二叉排序树。2. 显示二叉排序树：（1） 按照先序遍历方式显示二叉排序树。（2） 按照中序遍历方式显示二叉排序树。（3） 按照后序遍历方式显示二叉排序树。（4） 按照层次遍历方式显示二叉排序

3、树。3. 删除一个结点：要求可以实现删除根结点、叶子结点以及其它任意结点的功能。（1） 按照先序、中序、后序方式显示删除前的二叉排序树。（2） 按提示信息输入被删除结点的值，并在二叉排序树进行删除。（3） 显示删除是否成功的结果。（4） 若删除成功，则按照先序、中序、后序方式显示删除后的二叉排序树。4. 插入一个结点：（1） 按照先序、中序、后序方式显示插入前的二叉排序树。（2） 按提示信息输入要插入结点的值，并在二叉排序树进行插入。（3） 显示插入是否成功的结果。（4） 若插入成功，则按照先序、中序、后序方式显示插入后的二叉排序树。5. 查找给定值的结点：（1） 按照先序、中序、后序方式显示

4、二叉排序树。（2） 按提示信息输入待查找的值，并在二叉排序树进行查找。（3） 显示查找是否成功的结果。6. 交换二叉排序树：（1） 按照先序、中序、后序方式显示初始的二叉排序树。（2） 按照先序、中序、后序方式显示交换左右子树后的二叉排序树。7. 退出：退出整个算法演示程序。3.程序的输入：输入为整形数据，输入一串数字序列并以-1结束，且以回车键相隔。4.程序的输出：通过用户手动选择操作指令，经由程序内部处理，输出相应的结果到显示屏。5.测试数据，用户手动输入一个数字序列进行数据测试二、设计说明1算法设计的思想 根据算法的需求，确定算法的主要模块（建立二叉树、显示二叉树，插入结点、删除结点、查

5、找结点、退出系统。以及主函数模块）对各模块再进行函数的选取与构造，以及变量的控制等。最后，再将各模块结合，形成完整的算法，由主函数来调用。并设计界面。程序运行时在界面上显示及选择。注意全局变量的选择。2主要的数据结构设计说明；设计了一个排序二叉树的数据结构，包括查找，删除等功能。首先使用类模板建立排序二叉树类，及结点类存储结构。因显示函数中的层次遍历需要用到队列，所以定义了一个链式队列类，二叉树函数成员中包括查找，删除，显示，插入函数。下面分别写出几个函数的代码。主函数部分包括一个主函数和一个界面模块。主函数调用部分1.建立二叉树即循环调用插入函数。并调用遍历函数，2.遍历显示，调用遍历函数。

6、3.删除，首先由查找函数查找到关键字的地址，再传递给删除函数，进行删除。4.插入，插入前，插入后分别调用遍历函数并且调用插入函数即可，插入函数中，调用了查找函数。5.查找，调用查找函数，并显示查找结果，成功或者失败。6.退出系统，整个主函数循环选择功能序号的条件是number不等于6。7.交换功能3.程序的主要流程图；4.程序的主要模块，要求对主要流程图中出现的模块进行说明；a. 创建二叉树：循环条件调用插入函数。b.显示二叉排序树：调用desplayTree函数，desplayTree函数调用先中后序遍历。调用层次遍历函数。c.删除一个结点：首先由查找函数查找到关键字的地址，再传递给删除函数

7、，进行删除。并在删除前后显示遍历结果。d.插入一个结点：插入前，插入后分别调用遍历函数并且调用插入函数即可，插入函数中，调用了查找函数。e.查找给定值的结点：查找，调用查找函数，并显示查找结果，成功或者失败。f.交换二叉排序树：g.退出：5.程序的主要函数及其伪代码说明 a. 删除函数P定义为叶结点p->leftChild = NULL&&p->rightChild = NULL如果p的左孩子右孩子均为空delete p;直接删除pelse if (p->leftChild = NULL)tmpPtr=p;p=p->rightChild;delete t

8、mpPtr;如果被删除的元素只有右子树，没有左子树，则可以拿他的左孩子顶替他的位置，再释放该元素的存储空间即可；只有左子树没有右子树同理。tmpF=p;tmpPtr=p->leftChild;while (tmPtr->rightChild != NULL)/查找p在中序序列中直接前驱tmpPtr及其双亲tmpFtmpF=tmpPtr;tmpPtr=tmpPtr->rightChild;p->data=tmpPtr->data;/将tmpPtr指向结点的数据元素值赋值给被删除的结点if (tmpF->rightChild = tmpPtr) /删除tmpPt

9、r的结点Delete(tmpF->rightChild);elseDelete(tmpF->rightChild);elseDelete(tmpF->leftChild);如果被删除的元素左右孩子都存在的话，则在他的左子树中寻找关键字值最大的数据元素x,用x的值代替被删除元素的值，再来删除数据元素的值x。b.交换函数(head->leftChild=NULL&&head->rightChild=NULL)如果左右孩子均为空，则不需要交换。temp=head->leftChild;head->leftChild=head->righ

10、tChild;head->rightChild=temp;如果不为空，则定义中间变量，进行左右交换。if(head->leftChild)ExchangeTree(head->leftChild);如果被交换的结点存在树的左子树上则递归递归调用交换函数。存在于右子树上同理。c.查找函数BinTreeNode<ElemType> *p=r;指向当前结点f=NULL;指向p的双亲。从根节点开始将根节点的关键字与给定值比较如果相同则成功。if (key < p->data)f=p;p=p->leftChild;else f=p;p=p->righ

11、tChild;f=NULL;如果给定值小于根节点的关键字，则在根节点的左子树上递归查找。大于则在右子树上递归查找。d.插入函数（FindTree(e, f) = NULL)首先查找给定值是否在书中已存在。if (f=NULL)r=p;如果为空树，则新节点为根节点。else if (e<f->data)f->leftChild=p;else f->rightChild=p;如果小于双亲，则插入结点为左孩子。大于双亲，则插入结点为右孩子。return true;elsereturn false;如果查找成功，则插入失败。e.先中后以及层次遍历函数void BinarySor

12、tTree<ElemType>:desplayTree()由该函树调用先中后序遍历，以先序遍历为例。if(r !=NULL)cout<<r->data<<' 'PreOrder (r->leftChild);PreOrder (r->rightChild);如果以r为跟的二叉树为空，则遍历结束，如不为空，首先访问根节点再先序遍历他的左子树。然后再先序遍历它的右子树。中序，首先中序遍历他的左子树，再访问他的根节点，最后中序遍历它的右子树。后序首先后序遍历他的左子树，再后序遍历它的右子树，最后访问根节点。层次遍历LinkQueu

13、e<BinTreeNode<ElemType> *> q;BinTreeNode<ElemType> *w;if (r!=NULL) q.EnQueue (r);while (!q.IsEmpty() q.DelQueue(w);cout<<w->data<<' 'if (w->leftChild != NULL)q.EnQueue(w->leftChild);if (w->rightChild != NULL)q.EnQueue(w->rightChild);1. 首先初始化队列，并将根

14、节点入队。2.当队列非空时，取出队头结点转3否则结束遍历。3.访问结点p如果该节点有左孩子则将其左孩子入队；如果 该节点有右孩子，则将其右孩子入队。4.重复步骤2 3 直到队列为空为止。6.合作人设计分工 经由郭凯迪同学指错改错。三、上机结果及体会1.实际完成的情况说明所要求的功能均能实现，数据类型为整形数据2.程序的性能分析，包括时空分析函数时间复杂度空间复杂度查找O(log2n)-O(n+1)/2)O(1)插入O(log2n)O(1)删除O(1)O(1)先中后遍历O(n)O(n)层次遍历O(n)O(n)交换O(1)O(1) 3.打印程序运行时的初值和运行结果A. 初始界面B.建树C.显示D

15、.删除E.查找F.交换G.退出H.插入4. 上机过程中出现的问题及其解决方案出现许多语法问题例如定义函数与声明不匹配，函数名称是否正确，if else的匹配问题，通过一步一步的修改最终实现程序。界面部分修改的更合理。创建函数部分，循环调用插入函数时输入是在调用前还是在调用后。删除函数部分首先需要查找关键字结点，查找返回的为地址，所以中间传递变量应为指针，以及参数数量应相等。5.程序中可以改进的地方说明界面可以进行进一步优化。6.收获及体会 a.进行程序设计的时候注意模块的划分，从各个小 模块开始进行设计 b.熟练掌握各函数的成员构成 c.交流与合作7.打印一份源程序清单并附上注释。#inclu

16、de<iomanip>#include<string.h>#include<malloc.h>#include<stdio.h> template<class ElemType> struct Node ElemType data; Node<ElemType> *next; Node(ElemType &e) data=e; next=NULL; ; Node() next=NULL; ; template<class ElemType> class LinkQueue public: Node<

17、;ElemType> *front, *rear; LinkQueue(); virtual LinkQueue(); bool IsEmpty();void DelQueue(ElemType &e); void EnQueue(const ElemType e); ; template<class ElemType> bool LinkQueue<ElemType>:IsEmpty() if(front=rear) return true;elsereturn false; template<class ElemType> LinkQueu

18、e<ElemType>:LinkQueue() rear=front=new Node<ElemType> template<class ElemType> LinkQueue<ElemType>:LinkQueue() template<class ElemType> void LinkQueue<ElemType>:EnQueue( ElemType e) Node<ElemType> *p; p=new Node<ElemType>(e); if(p) rear->next=p; rea

19、r=rear->next; template<class ElemType>void LinkQueue<ElemType>:DelQueue(ElemType &e) if (!IsEmpty() Node<ElemType> *p=front->next; e=p->data; front->next=p->next; if (rear = p) rear=front; delete p; template <class ElemType> struct BinTreeNode/声明树结构 ElemTyp

20、e data;BinTreeNode<ElemType> *leftChild;/存放左子树的指针BinTreeNode<ElemType> *rightChild;BinTreeNode();BinTreeNode( ElemType &e); ;template <class ElemType> BinTreeNode<ElemType>: BinTreeNode(ElemType &e) data=e; leftChild=NULL; rightChild=NULL; template <class ElemType&

21、gt; BinTreeNode<ElemType>: BinTreeNode() leftChild=NULL; rightChild=NULL; template <class ElemType>class BinarySortTreepublic:BinTreeNode<ElemType> *r; BinarySortTree(); void desplayTree(void);/显示这个数 bool insertTree( ElemType &e);/在树中插入一个节点 virtualBinarySortTree();BinTreeNode&l

22、t;ElemType> *head;void PreOrder(BinTreeNode<ElemType> *r);void InOrder(BinTreeNode<ElemType> *r);void PostOrder(BinTreeNode<ElemType> *r);void LevelOrderTree(); BinTreeNode<ElemType>* buildTree(BinTreeNode<ElemType>* head,int number);/建立一个树bool DeleteTree(BinTreeNode

23、< ElemType> * &p, BinTreeNode< ElemType> * &fq);void ExchangeTree(BinTreeNode<ElemType> *head);BinTreeNode<ElemType> *FindTree( ElemType &key,BinTreeNode<ElemType> *&f) const; void destroyTree(BinTreeNode<ElemType> * &r); ;template <class El

24、emType>BinarySortTree<ElemType>:BinarySortTree()r=NULL;template <class ElemType>BinarySortTree<ElemType>:BinarySortTree() /调用析构函数，运用递归删除所有的new节点 cout<<"已?经-消?除y了?一?棵?树骸?!"<<endl; destroyTree(r);template <class ElemType>bool BinarySortTree<ElemType&

25、gt;:DeleteTree(BinTreeNode< ElemType> * &p, BinTreeNode< ElemType> * &fq)BinTreeNode<ElemType> *tmpPtr, *tmpF;if (p->leftChild=NULL&&p->rightChild=NULL&&fq!=NULL) /叶子结点?delete p;if (fq != NULL)if (fq->leftChild = p)fq->leftChild = NULL;else fq-&g

26、t;rightChild = NULL;p = NULL;else if (p->leftChild = NULL) /有右子树结点if(fq=NULL)r=p->rightChild;else if (fq->leftChild = p)fq->leftChild = p->rightChild;else fq->rightChild = p->rightChild;delete p;p = NULL;else if (p->rightChild = NULL) /有左子树结点if(fq=NULL)r=p->leftChild;if (f

27、q->leftChild = p)fq->leftChild = p->leftChild;else fq->rightChild = p->leftChild;delete p;p = NULL;else /左右子树都有tmpF = p;tmpPtr = p->leftChild;while (tmpPtr->rightChild != NULL) /找左子树的右子树最后一个结点循环结束tmpPtr指向目标结点，tmpF指向目标结点的父母.tmpF = tmpPtr;tmpPtr = tmpPtr->rightChild;p->data

28、= tmpPtr->data;if (tmpF->rightChild = tmpPtr)DeleteTree(tmpF->rightChild, tmpF);elseDeleteTree(tmpF->leftChild, tmpF);return true;template <class ElemType>void BinarySortTree<ElemType>:ExchangeTree(BinTreeNode<ElemType> *head)BinTreeNode<ElemType>* temp=NULL;if(he

29、ad->leftChild=NULL&&head->rightChild=NULL)return;elsetemp=head->leftChild;head->leftChild=head->rightChild;head->rightChild=temp;if(head->leftChild)ExchangeTree(head->leftChild);if(head->rightChild)ExchangeTree(head->rightChild);template <class ElemType>Bi

30、nTreeNode<ElemType> *BinarySortTree<ElemType>:FindTree( ElemType &key,BinTreeNode<ElemType> *&f) constBinTreeNode<ElemType> *p=r;/指向当前节点f=NULL;/指向p的双亲while (p != NULL && p->data != key)/查找关键字为key的节点if (key < p->data)/key比p的值小，则在p的左子树上进行查找f=p;p=p->l

31、eftChild;else /key比p的值大，则在p的右子树上进行查找f=p;p=p->rightChild;return p;template <class ElemType>bool BinarySortTree<ElemType>:insertTree(ElemType &e)/f=NULL;/ 指向被查找节点的双亲BinTreeNode<ElemType> *f;BinTreeNode<ElemType> *p;if (FindTree(e, f) = NULL) / 查找失败，插入成功。p= new BinTreeNod

32、e<ElemType> (e);if (f=NULL)/空二叉树，新节点为根节点r=p;else if (e<f->data)/e小于其双亲，插入结点为f的左孩子f->leftChild=p;else /e大于其双亲，插入结点为f的右孩子f->rightChild=p;return true;elsereturn false;template <class ElemType>void BinarySortTree<ElemType>:desplayTree()cout<<"前序 " PreOrder(r

33、);cout<<endl;cout<<"中序 " InOrder(r);cout<<endl;cout<<"后序 "PostOrder(r); cout<<endl;template <class ElemType>void BinarySortTree<ElemType>:PreOrder(BinTreeNode<ElemType> *r) if(r !=NULL)cout<<r->data<<' '/首先访问根

34、节点PreOrder (r->leftChild);/再先序遍历r的左子树PreOrder (r->rightChild);/再先序遍历r的右子树template <class ElemType>void BinarySortTree<ElemType>:InOrder(BinTreeNode<ElemType> *r) if(r !=NULL)InOrder (r->leftChild);/首先中序遍历r的左子树cout<<r->data<<' '/再访问根节点?InOrder (r->

35、rightChild);/最后中序遍历r的右子树template <class ElemType>void BinarySortTree<ElemType>:PostOrder(BinTreeNode<ElemType> *r)if(r !=NULL)PostOrder (r->leftChild);/首先后序遍历r的左子树 PostOrder (r->rightChild);/再后序遍历r的右子树cout<<r->data<<' '/再访问根节点rtemplate <class ElemTyp

36、e>void BinarySortTree<ElemType>:LevelOrderTree() LinkQueue<BinTreeNode<ElemType> *> q;/定义队列qBinTreeNode<ElemType> *w;if (r!=NULL) q.EnQueue (r);while (!q.IsEmpty() q.DelQueue(w);cout<<w->data<<' 'if (w->leftChild != NULL)q.EnQueue(w->leftChild)

37、;if (w->rightChild != NULL)q.EnQueue(w->rightChild);template <class ElemType>void BinarySortTree<ElemType>:destroyTree(BinTreeNode<ElemType> * &r) if(r!=NULL) destroyTree(r->leftChild ); destroyTree(r->rightChild ); delete r; #include<iostream>#include"tr

38、ee.h"using namespace std;void menu()cout<<endl; cout<<"*以下是对二叉排序树的基本操作* "<<endl; cout<<"| 0.创建二叉树 | "<<endl; cout<<"| 1.显示二叉树 | "<<endl; cout<<"| 2.删除一个节点 | "<<endl; cout<<"| 3.插入一个节点 | &quo

39、t;<<endl; cout<<"| 4.查找一个节点 | "<<endl; cout<<"| 5.交换二叉树 | "<<endl; cout<<"| 6.退出 | "<<endl; cout<<"* "<<endl;void main() BinarySortTree< int > tree;BinTreeNode< int > *p=NULL;BinTreeNode<int&

40、gt; *q; int number; int choiceNumber=8; while(choiceNumber!=6) menu () ; cout<<" 请选择你进行的操作06)"<<endl; cin>>choiceNumber; switch(choiceNumber) case 0: cout<<"请输入建树骸的数据，以-1结尾:"<<endl; cin>>number; while(number!=-1) tree.insertTree(number); cin>>number; tree.desplayTree(); cout<<endl; break; case 1: tree.desplayTree();cout<<"层次遍历 "tree.LevelOrderTree(