利用二叉排序树对顺序表进行排序

1、长沙学院课程设计说明书题目利用二叉排序树对顺序表进行排序系（部）专业（班级）姓名学号指导教师起止日期2015.12.82015.12.15课程设计任务书课程名称：数据结构与算法课程设计设计题目：为了充分调动学生的学习积极性与主动性，适应不同兴趣、不同程度的学生对课程设计的要求，本课程设计提供四个任选题。每个学生可以根据本人的兴趣及能力选择教师指定的选题，也可以自定其他的选题。1、一元多项式计算问题2、迷宫问题3、利用二叉排序树对顺序表进行排序4、交通咨询系统5、内部排序算法的比较已知技术参数和设计要求：需求说明及要求题目三：利用二叉排序树对顺序表进行排序问题描述：利用二叉排序树对顺序表进行排序

2、。基本要求：(1)生成一个顺序表L;(2)对所生成的顺序表L构造二叉排序树；(3)利用栈结构实现中序遍历二叉排序树；(4)中序遍历所构造的二叉排序树将记录由小到大输出。测试数据：用伪随机数产生程序产生，表长不小于20。选作内容：用实现二叉排序树的插入和删除操作。各阶段具体要求：1、需求分析阶段熟悉系统业务，从业务中抽取出系统的需求，形成完善的需求说明书。2、系统设计阶段根据需求，进行程序设计，包括定义系统的界面、定义系统数据的存储方式等，形成完善的设计说明书。3、编码实现阶段(1)完成代码编写(2)要求代码编写规范4、系统测试阶段(1)完成功能调试(2)要求完成必要的测试工作5、交付实施阶段(

3、1)提交可正常执行的系统(2)提交系统需求说明书、设计说明书、程序代码(3)撰写课程设计报告书(4)要求规范地书写文档设计工作量：(1)软件设计：完成问题陈述中所提到的所有需求功能。(2)论文：要求撰写不少于3000字的文档，详细说明各阶段具体要求。工作计划：数据结构课程设方t总学时数为2周，其进度及时间大致分配如下：序号设计内容天数1 分析问题，给出数学模型，选择数据结构12 设计算法，给出算法描述23 给出源程序清单14 编辑、编译、调试源程序55 编写课程设计报告1总计10注意事项提交文档?长沙学院课程设计任务书(每学生1份)?长沙学院课程设计鉴定表(每学生1份)?长沙学院课程设计说明书

4、(每学生1份)指导教师签名：日期：教研室主任签名：日期：系主任签名：日期：长沙学院课程设计鉴定表姓名学号专业班级设计题目利用二叉排序树对顺序表进行排序指导教师指导教师意见：评定等级：教师签名：日期：答辩小组意见：评定等级：答辩小组长签名：日期：教研室总见：教研室主任签名：日期：系（部）意见：系主任签名：日期：说明课程设计成绩分“优秀”、“良好”、“及格”、“不及格”四类；摘要数据结构是研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简称数据结构。当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存储结构。相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。本次课程设计，

5、是基于链式顺序表建立二叉排序树。主要功能有建立、重建、插入、删除以及遍历。关键词：二叉排序树、中序遍历、插入结点、删除结点目录第1章设计内容与要求61.1 课程名称：数据结构与算法课程设计61.2 设计要求：6第2章需求分析72.1 设计目的72.2 设计环境8第三章概要设计83.1 功能结构83.2 函数的结构体93.3 系统主要的函数10第四章详细设计114.1 插入模块的设计114.2 删除模块的设计124.3 遍历模块设计134.4 树型打印模块的设计144.5 重建二叉树模块的设计15第五章模块测试165.1 插入模块测试165.2 删除插入模块测试175.3 遍历模块测试185.4

6、 树型打印模块测试195.5 二叉排序树重建模块测试20第六章总结22第七章附录源代码23第1章设计内容与要求1.1 课程名称：数据结构与算法课程设计设计题目：利用二叉排序树对顺序表进行排序问题描述：利用二叉排序树对顺序表进行排序。1.2 设计要求：(1)生成一个顺序表L;(2)对所生成的顺序表L构造二叉排序树(3)利用栈结构实现中序遍历二叉排序树；(4)中序遍历所构造的二叉排序树将记录由小到大输出。测试数据：用伪随机数产生程序产生，表长不小于20。选作内容：用实现二叉排序树的插入和删除操作。第2章需求分析2.1 设计目的二叉树的中序本次构造的是一个二叉排序树，主要的功能有二叉排序树的建立、节

7、点的插入与删除,遍历、树型打印、以及重建一个新的二叉排序树。图2.1系统功能模块图2.2 设计环境Windows10系统、visualstudio2015下编译运行第三章概要设计3.1功能结构本程序主要实现的有七个功能，首先创建二叉排序树，完成后出现菜单界面，菜单界面的功能有：二叉排序树的插入、删除、中序遍历、树形输出、二叉排序树的重建、退出。创建二叉树Switch(1)Switch(2)中序遍历Switch(3)Exit(0)退出Switch(4)树型打印Switch(5)Switch(6)图3.1主要功能结构流程图3.2函数的结构体typedefintkeytype;typedefintv

8、aluetype;typedefintlisttype;/structlinkliststructlinklist*next;intelement;/参数的数值；/顺序表结点的结构体structint_linkliststructlinklist*head;/顺序表的头结点的定义intcounts;/对顺序表的元素的多少进行统计/typedefstructBSTNodekeytypedata;/存放关键字的datastructBSTNode*lchild,*rchild;/定义二叉排序树的指针BTNode,*Btree;/typedefBtreeSelem;typedefstructsnode

9、Selemdata;/定义栈的存储的数据structsnode*next;/栈的指针snode,*linkst;typedefstructlinkstacklinksttop;/定义栈的栈顶指针intcount;/统计栈里面的元素linkstack;3.3系统主要的函数structint_linklist*init();/初始化链式顺序表voidadd(structint_linklist*,int);/链式顺序表增加结点voidprintf_list(structint_linklist*);/输出已经创建好的顺序表/voidemptyMessage(char*);/输出错误的提示voidi

10、nitstack(linkstack*);/初始化链式栈voidpushstacks(linkstack*,Selem);/进栈函数voidpopstacks(linkstack*,Selem&);/出栈函数boolempty_stack(linkstack*);/判断栈是否为空的函数/BTNode*init_BSTree(Btree);/初始化二叉排序树BtreeBSTree_fund();/建立一个二叉排序树的函数boolSearch_BSTree(Btree,keytype,BTNode&,BTNode&);/判断该值是否在二叉树存在boolinsert_BSTr

11、ee(Btree&,valuetype);/插入一个数值，返回0或1,判断是否插入成功boolDelete_BSTree(Btree&,keytype);/删除函数，找到要删除的数值，调用delete_value(Btree&tree),返回0或1判断删除是否成功voiddelete_value(Btree&tree);/删除这个结点voidinoder_rec(Btree);/中序非递归遍历二叉排序树voidPrintTree(Btree,int);/按树状图就行输出/voidmenu(Btree);/函数的菜单界面第四章详细设计4.1插入模块的设计boolS

12、earchBSTree(Btreetree,keytypevalue,Btree&parents,Btree&child)/寻找函数，判断二叉排序树中是否有该值，有返回1,无返回0child=tree;/子节点等于根节点while(child)/如果子节点child不为空，则执行下面代码if(value=child->data)/如果值等于child->data,则表示找到，返回1return1;elseif(value<child->data)/如果该值小于child->data,则向左子树进行查找纪录child结点的上一个结点，相当于记录父节点

13、parents=child;/parentschild=child->lchild;elseparents=child;child=child->rchild;return0;/如果不执行上面一段代码，或者没有找到，返回0/'boolinsert_BSTree(Btree&tree,keytypevalue)Btreeparents,child;/定义指针if(!Search_BSTree(tree,value,parents,child)/如果二叉排序树找不到该值，则插入BtreeS=(BTNode*)malloc(sizeof(BTNode);申请一个结构体空间

14、S->data=value;/赋值S->lchild=NULL;S->rchild=NULL;if(!tree)tree=S;/如果tree为空，则tree为s,设置根结点elseif(value<parents->data)/如果value<parents->data,就插入至U左子树return1;/returntree;4.2删除模块的设计boolDeleteBSTree(Btree&tree,keytypevalue)/删除函数if(!tree)return0;/tree为空，则表示删除功能不能执行elseif(value=tree-&

15、gt;data)/如果找到与value值相同的指针，调用delete_value函数进行删除deletevalue(tree);return1;elseif(value<tree->data)/value小于结点的值，往左子树进行寻找returnDelete_BSTree(tree->lchild,value);)elsereturnDelete_BSTree(tree->rchild,value);)/printf("%dn",tree->data);Ivoiddelete_value(Btree&p)Btreeq=NULL,s=NU

16、LL;if(p->lchild&&p->rchild)/删除的结点，左右子树都不为空的情况q=p;s=p->lchild;/q记录,s设为删除结点的左结点while(s->rchild)q=s;s=s->rchild;/进行循环，找到最右边的那个结点p->data=s->data;/把找到的最右边结点的关键字赋值给p的关键字if(q!=p)q->rchild=s->lchild;/挂接左右子树elseq->lchild=s->lchild;/printf("%dt%dt%dt%dn",q-&g

17、t;data,q->data,s->data,tree->data);free(s);/删除s这个结点elseif(!p->rchild)/右子树为空，所以挂接到左子树上q=p;p=p->lchild;free(q);elseq=p;p=p->rchild;free(q);/左子树为空，所以挂接到右子树上/printf("%dt%dt%dn",q->data,q->data,tree->data);4.3 遍历模块设计voidinoder_rec(BtreeT)linkstackS;|initstack(&S);

18、/初始化一个栈Seleme;Btreep=T;while(p|!(S.count=0)/当栈不为空或者p不为空时执行while(p)push_stacks(&S,p);/p不为空，则进栈p=p->lchild;/对左子树进行遍历)if(!empty_stack(&S)e=Get_top(S,e);/当栈不为空时，取栈顶，输出栈顶指针所指向的data值printf("%dn",e->data);pop_stacks(&S,p);/出栈，对右子树进行遍历p=p->rchild;)/*if(T)ninoderrec(T->lchil

19、d);printf("%dn",T->data);inoderrec(T->rchild);*/menu(tree);4.4 树型打印模块的设计voidPrintTree(Btreebt,intnlayer)/采用先序遍历的方法，进行树型打印if(bt)PrintTree(bt->rchild,nlayer+10);for(inti=0;i<nlayer;i+)printf("");printf("%dn",bt->data);PrintTree(bt->lchild,nlayer+10);4.5

20、重建二叉树模块的设计BtreeBSTree_fund()structint_linklist*lists=NULL;Btreetree=NULL;intn;lists=init();/初始化顺序表srand(unsigned)time(NULL);/伪随机函数的初始化printf("pleaseinputhowmanynumbers:n");scanf_s("%d",&n);输入要插入多少的数for(inti=0;i<n;i+)add(lists,rand();/构造顺序表structlinklist*p;/Btreetree=NULL;t

21、ree=initBSTree(tree);/初始化二叉树p=lists->head->next;while(p!=NULL)insertBSTree(tree,p->element);p=p->next;/调用insertBSTree函数构造二叉树returntree;第五章模块测试5.1插入模块测试pleaseinputhowujajiylumbers:6BStra好mpnu1.BStree_insert2iBStree_delete3.inoderBStree4、exit5.Treeoutput6.ReconstructiontheBStreepleaseinput

22、yourwant二1pleaseinputtheinsertnumbers：100successinsert!BStreemenu1. BStree_insert24BStree_delete2. inoderBStree4.exit5. Tts?ourput6,ReeonsTrucriontheBStreebleaseinputyourwant;5.2删除插入模块测试EiW's状二建屋设计Dmtnjgt七二课程曲十X3.inoderBStree4.exitt),treeoutput6.ReconstructiontheBStreepleaseinputyourwant：3100得09

23、964216532211431375BSrreemenuLBStrce_insert2.BStrce_dclete3. inoderBStree4.exit,Treeoutput6,ReconstructiontheBStreepleaseinputycurwant:oz.pleaseinputth?deletekevnumbers；7520succeeddelete!BStreemenuLEStrce_inserr2.BStree_dclete&inoderBStree4.exitt>+Treeoutput6.ReconstructiontheBStreepleaseinput

24、yourwant*5.3遍历模块测试ij二曲毓巾比加浜±二婕设计.«31009961216532211431375BStrt?yiiieriukBStree_insert2.BStree_delete3.inoderBStree4.exitb.Ireecutpiit6.KeconstructionthfBStreepleaseinputyoi;rwnntrB1009964216532211431375一一j-BStreemenu1,13Srree_insert2,UStree_delete3.inoderBStree4.exit5xTreeoutput6.Reconstru

25、ctiontheBStreepleaseinputyourwant15.4树型打印模块测试?软A二曲院设计DmbugWt二谓程iStt.eT照Xpleaseinputyourwant:31009964216532211431375BStreemenu1.BStree_inseit2.BStree_deleteinoderBStree4.exitn.Treeourput6,ReconstructiontheBStre?pleaseinputyourwant：53137522114216539964100.BStreemenu1,inserr2.UStree_delete3,inoderBStre

26、e4.exitSxTreeDLitput6.Recunsti'uctiontheBStreepleaseinputyourwant15.5二叉排序树重建模块测试31375216539964100BStreemenuLBStreeinsert2.BStreedeleteB.inoderBStree5. Treepleast?6please10SIJ：（*EKoutputinputinputBStree4.exit6. ReconstructiontheBStreeyourwant：howmanynumbers:menuIkBStree_insert2,BStree_delete3.ino

27、derBSti*ee4.exittheRStrepTreeoutput6.Reconstructionpleaseinputyourwant：13941803上二；，尤为第六章总结通过这次课程设计，我对二叉排序树的整个构造流程更加了解了，同时也对顺序表和栈这两种数据结构做了一次复习，但同时也存在了很多问题。我在删除函数中因为有些指针没有用好，所以最开始只是跟我报错说是read()出错，我反复的检查许久一直找不到出错的地方在哪，不得已，只能重新写了一遍删除函数，发现我分成两个删除函数去执行(一个函数去找那个需要删除的结点，另一个函数则是对这已经找到的结点进行删除)，没有问题。而对于中序遍历函数，

28、我先用递归做测试，先把其他功能做完善以后，再用栈来实现中序非递归遍历。第七章附录源代码#include<iostream>#include<malloc.h>#include<cstdio>#include<stdlib.h>|#include<time.h>/#include<graphics.h>/usingnamespacestd;/unsignedintn=30;/typedefintkeytype;typedefintvaluetype;typedefintlisttype;/structlinkliststru

29、ctlinklist*next;intelement;structint_linkliststructlinklist*head;intcounts;/typedefstructBSTNode|keytypedata;structBSTNode*lchild,*rchild;BTNode,*Btree;/typedefBtreeSelem;typedefstructsnodeSelemdata;structsnode*next;snode,*linkst;typedefstructlinkstacklinksttop;intcount;linkstack;/structintlinklist*

30、init();voidadd(structintlinklist*,int);voidprintf_list(structint_linklist*);/voidemptyMessage(char*);voidinitstack(linkstack*);voidpush_stacks(linkstack*,Selem);voidpop_stacks(linkstack*,Selem&);boolempty_stack(linkstack*);/BTNode*init_BSTree(Btree);BtreeBSTree_fund();boolSearch_BSTree(Btree,key

31、type,BTNode&,BTNode&);boolinsert_BSTree(Btree&,valuetype);boolDelete_BSTree(Btree&,keytype);voiddelete_value(Btree&tree);voidinoder_rec(Btree);voidPrintTree(Btree,int);/voidmenu(Btree);/、intmain()Btreetree=NULL;/printf_list(lists);tree=BSTreefund();/printf("n");/printf(

32、"%dn",tree->data);|/printf("n");/inoder_rec(tree);menu(tree);return0;/structintlinklist*init()structint_linklist*lists;lists=(structintlinklist*)malloc(sizeof(structintlinklist*);lists->head=(structlinklist*)malloc(sizeof(structlinklist);lists->head->element=-1;lists-

33、>counts=0;lists->head->next=NULL;returnlists;|)voidadd(structint_linklist*lists,intvalue)structlinklist*p;p=(structlinklist*)malloc(sizeof(structlinklist);p->next=NULL;p->element=value;p->next=lists->head->next;lists->head->next=p;lists->counts+;/returnlists;voidprin

34、tf_list(structint_linklist*lists)structlinklist*p;p=lists->head->next;while(p!=NULL)printf("%dn",p->element);p=p->next;/voidemptyMessage(char*s)printf("%sn",s);exit(1);voidinitstack(linkstack*stacks)/linkst*p;stacks->top=(linkst)malloc(sizeof(snode);if(stacks->t

35、op=NULL)emptyMessage("itisfalse");stacks->top=NULL;stacks->count=0;/stacks.top->next=NULL;SelemGet_top(linkstackstacks,Selem&e)if(stacks.top=NULL)emptyMessage("itisempty");e=stacks.top->data;returne;voidpushstacks(linkstack*stacks,Seleme)linkstp=(linkst)malloc(siz

36、eof(snode);if(p=NULL)emptyMessage("False");p->data=e;p->next=stacks->top;stacks->top=p;stacks->count+;voidpop_stacks(linkstack*stacks,Selem&e)linkstp;if(stacks->count=0)emptyMessage("itisempty");e=stacks->top->data;p=stacks->top;/printf("%dn&qu

37、ot;,p->data);|stacks->top=stacks->top->next;free(p);stacks->count-;boolempty_stack(linkstack*stacks)if(stacks->count=0)return1;elsereturn0;/BTNode*init_BSTree(Btreetree)Btreeroot=tree;returnroot;boolSearchBSTree(Btreetree,keytypevalue,Btree&parents,Btree&child)/if(tree!=NUL

38、L)child=tree;while(child)if(value=child->data)return1;elseif(value<child->data)parents=child;child=child->lchild;elseparents=child;child=child->rchild;return0;/boolinsertBSTree(Btree&tree,keytypevalue)Btreeparents,child;if(!SearchBSTree(tree,value,parents,child)BtreeS=(BTNode*)mal

39、loc(sizeof(BTNode);S->data=value;S->lchild=NULL;S->rchild=NULL;if(!tree)tree=S;elseif(value<parents->data)parents->lchild=S;return1;/returntree;/menu(tree);BtreeBSTree_fund()structint_linklist*lists=NULL;Btreetree=NULL;intn;lists=init();srand(unsigned)time(NULL);printf("please

40、inputhowmanynumbers:n");scanfs("%d",&n);for(inti=0;i<n;i+)add(lists,rand();structlinklist*p;/Btreetree=NULL;tree=init_BSTree(tree);p=lists->head->next;while(p!=NULL)insert_BSTree(tree,p->element);p=p->next;returntree;boolDelete_BSTree(Btree&tree,keytypevalue)if(

41、!tree)return0;elseif(value=tree->data)deletevalue(tree);returnDelete_BSTree(tree->rchild,value);)printf("%dn",tree->data);voiddelete_value(Btree&p)Btreeq=NULL,s=NULL;if(p->lchild&&p->rchild)|q=p;s=p->lchild;while(s->rchild)Iq=s;s=s->rchild;|)p->data=s

42、->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;/printf("%dt%dt%dt%dn",q->data,q->data,s->data,tree->data);free(s);)elseif(!p->rchild)q=p;p=p->lchild;free(q);)elseq=p;p=p->rchild;free(q);)/printf("%dt%dt%dn",q->data,q->data,tree->data);)voidinoder_rec(BtreeT)linkstackS;initstack(&S);Seleme;Btreep=T;while(p|!(S.count=0)while(p)push_stacks(&S,p);p=p->lchild;)if(!empty_stack(&S)e=Get_top(S,e);printf("%dn",e->data);pop_stacks(&S,p);p=p->rchild;/*