用顺序和二叉链表作存储结构实现二叉排序树全代码.docx

安徽新华学院数据结构课程设计报告题目：用顺序和二叉树存储结构实现二叉树排序学院：信息工程专业：信息与计算科学班级：12信科本一班姓名：李智学号：1242155110指导教师：李明设计时间：20131216至2(H31230课程设计任务书-设计任务研究关于如何创立二叉排序树并对树进行遍历，查找和删除等操作，同时关注用顺序和二叉链表作存储结构带来的区别。二.设计要求(1) .利用顺序存储和链式存储两种算法计算实现二叉搜索树的创立。(2) .利用顺序存储和链式存储两种算法计算实现中序遍历。(3) .利用顺序存储和链式存储两种算法计算实现查找结点。(4) .利用顺序存储和链式存储两种算法计算实现删除结点。.设计期限2013-12-16三2013-12-30前言数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科本课程设计中的二叉排序树，可以用顺序存储和链式存储两种算法计算。本课程设中的二叉排序树，一共要实现四项根本的功能。它们分别是二叉搜索树的创立、中序遍历、查找结点和删除结点。二叉树是树形结构的一个重要的类型，二叉树是n(n>=0)个结点的有限集，它或者是空集(n=0),或者由个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。二叉树的存储结构和算法比拟简单，特别适合计算机处理。即使一般形式的树也可简单的转换为二叉树。二叉树的顺序存储结构是把二叉树的所有结点，按照一定的次序顺序，存储到一片连续的存储单元中。遍历二叉树就是沿某有前序遍历、中条搜索路径周游二叉树，对树中每个结点访问一次且仅访问一次。在遍历方案中主要序遍历、后序遍历。现实中有许多应用到二叉树的例子，所以我们要把理论与现实结合起来。在学习中主要掌握怎么求二叉树的高度、叶子结点个数、总结点个数以及熟练三种遍历的方法。目录1需求分析21. 1问题的提出2任务与分析22总体设计2二叉排序树的建立2二叉排序树的中序遍历3二叉排序树中元素的查找3二叉排序树中元素的删除32. 5总体设计流程图3详细设计错误!未定义书签。3.1 中序遍历模块73.2 删除模块74编码与调试94.1顺序存储104.2二叉链表存储105总结11总结错误!未定义书签。心得体会12参考文献12全部代码13二叉链表结构C13二叉链表结构C+15顺序存储结构Cl81需求分析1.1 问题的提出研究关于如何创立二叉排序树并对树进行遍历，查找和删除等操作，同时关注用顺序和二叉链表作存储结构带来的区别。1.2 任务与分析用顺序和二叉链表作存储结构实现二叉排序树：(I)以回车('n')为输入结束标志,输入数列1.,生成一棵二叉排序树T；(2)对二叉排序树T作中序遍历，输出结果；(3)输入元素X,查找二叉排序树T,假设存在含X的结点,那么删除该结点,并作中序遍历(执行操作2)；否那么输出信息“无x”O2总体设计二叉排序树的建立建二叉树的结点至少应当包含三个域，分别存放结点的数据data,左子女结点指针IeftChild和右子女结点指针righlChik1.整个二叉树的链表要有一个表头指针，它指向二叉树的根结点，其作用是当作树的访问点从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。根据二叉排序树的定义，建立一棵二叉排序树的过程是按照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。假设P为根结点指针，b为当前待插入元素，其过程可以描述为：假设为空树(p=nil),动态生成一个结点，其数据域为当前待插入元素b,左、右指针域为“空”,P指向该结点。假设非空树，比拟b与根结点数据daia(p)如果b<data(p),将b插入左子树中；如果b>data(p),将b插入右子树中；左、右子树的插入方式与二叉排序树的插入方式相同。不断调用上述的插入过程，直到所有待排序序列均排入后，就形成一棵二叉排序树。由此可见，建立二叉排序树就是屡次调用二叉排序树的插入算法。二叉排序树的中序遍历中序遍历二叉树算法的框架是：假设二叉树为空，那么空操作；否那么中序遍历左子树(1.)；访问根结点(V)；中序遍历右子树(R)o0二叉排序树中元素的查找在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比拟判等的过程。它可以是一个递归的过程。假设我们想要在二叉排序树中查找关键码为X的元素，查找过程从根结点开始。如果根指针为NU1.1.,那么查找不成功；否那么用给定值X与根结点的关键码进行比拟；如果给定值等于根结点的关键码，那么查找成功，返回查找成功的信息，并报告查找到的结点地址。如果给定值小于根结点的关键码，那么继续递归查找根结点的左子树；否那么，递归搜索根结点的右子树。二叉排序树中元素的删除对于二叉排序树，删去树上的一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性即可。假设在二叉排序树上被删除结点为*P(指向结点的指针是P),其双亲结点为*f(结点指针为f),且不失一般性，可设*P是*f的左孩子，假设*P结点为叶子结点，即P和1均为空，只需修改其双亲结点指针即可。假设*P结点只有左子树或者只有右子树，只要令左子树或右子树直接成为其双亲结点即可。假设左子树和右子树都不为空，令*P的直接前驱替代*P,然后从二叉排序树中删除它的直接前驱，即可。总体设计流程图3.详细设计>Tnode的声明typedefstructTnodeintdata;structTnode*lchild,*rchild;*node,BSTnode; searchBST的声明SearchBST(nodet,intkey,nodef,node*p)(if(1t)*p=f;return(O);elseif(key=t->data)*p=t;return(1);elseif(key<t->data)searchBST(t->lchild,key,t,p);elsesearchBST(t->rchiId,key,t,p);) insertBST的声明insertBST(node*t,intkey)(nodep=NU1.1.,s=NU1.1.;if(!searchBST(*t,key,NU1.1.,&p)(s=(node)malIoc(siZeof(BSTnode);s->data-key;s->lchild=s->rchiId=NU1.1.;if(!p)*t=s;elseif(key<p->data)p->lchild=s;elsep->rchild=s;return(1);)elsereturn(O);) inorderTraverse类的声明inorderTraverse(node*t)if(inorderTraverse(&(*t)->lchiId)printf(zz%d,z,(*t)->data);if(inorderTraverse(&(*t)->rchild);return(1);)Delete类的声明nodeDelete(nodet,intkey)nodep=t,q=NU1.1.,s,f;whiIe(p!=NU1.1.)if(p->data=key)break;q=P；if(p->data>key)p=p->lchild;elsep=p->rchild;)if(P=NU1.1.)returnt;if(p->IchiId=NU1.1.)(if(q=NU1.1.)t=p->rchild;elseif(q->lchild-p)q->lchild=p->rchiId;elseq->rchild=p->rchiId;free(p);)elsef=P；s=p->lchild;while(s->rchild)f=s;s=s->rchild;if(f=p)f->lchild=s->lchiId;elsef->rchild=s->lchiId;p->data=s->data;free(三);returnt;1.1 中序遍历模块系统将提示用户输入新添加的数据，输入结束后进行中序遍历关键代码：InorderTraverse(node*t)/*中序遍历函数*/(if(*t)if(inorderTraverse(&(*t)->lchild)/*中序遍历根的左子树*/printfCz%d",(*t)->data);/*输出根结点*/if(inorderTraverse(&(*t)->rchiId);/*中序遍历根的右子树*/)return(1);3. 2删除模块系统将对用户输入的数进行查找，查找到之后删除此数，并对全部数据进行中序遍历。关键代码：nodeDelete(nodet,intkey)*删除函数*/nodep=t,q=NU1.1.,s,f;while(p!=NU1.1.)*查找要删除的点*/(if(p->data-key)break;q=p;if(p->data>key)p=p->lchild;elsep=p->rchiId;)if(p=NU1.1.)returnt;*查找失败*/if(p->lchiId=NU1.1.)*p指向当前要删除的结点*/(if(q=NU1.1.)t=p->rchild;*q指向要删结点的父母*/elseif(q->lchild=p)q->lchild=p->rchiId;*p为q的左孩子*/elseq->rchild=p->rchild;/*p为q的右孩子*/free(p);)else*P的左孩子不为空*/f=p;s=p->lchiId;While(s->rchild)*左拐后向右走到底*/f=s;s=s->rchiId;if(f-p)f->lchild=s->lchiId;/*重接f的左子树*/elsef->rchi1d=s->!child;/*重接f的右子树*/p->data=s->data;free(三);returnt;4编码与调试首先进入VC+6.0,翻开工程zjr.dsw,然后进入源程序，也可以不翻开工程，直接双击Zjr文件夹下的zjr.exe文件即可运行程序。4.1顺序存储图.1翻开程序，成功显示提示信息图输入数据，以O结束输入，操作成功图功能1：中序输出数据，操作成功图功能2：删除数据，显示提示信息，操作成功图删除数据，操作成功图重复执行程序，操作成功4. 2二叉链表存储图翻开程序，显示提示信息，操作成功图功能1：输入数据，进行中序遍历，操作成功图功能2：输入数据，进行删除，操作失败，因为没有此数据，显示错误信息功能2：输入数据，进行中序遍历，操作成功通过上述测试，本系统实现了二叉树的生成，中序遍历，查找删除功能，能防止数据的输入错误等。验证结果正确，说明其符合算法设计的要求：(1)正确性、可读