二叉树数据结构课程设计

目录TOC\o"1-5"\h\z第一章需求分析 1\o"CurrentDocument"1・1课程设计题目 11.2课程设计任务及要求 1\o"CurrentDocument"1.21课程设计目的 1\o"CurrentDocument"1.22设计要求 1\o"CurrentDocument"1.3课程设计思想 2\o"CurrentDocument"1.4软件运行环境及开发工具 2\o"CurrentDocument"第二章概要设计 3\o"CurrentDocument"2.1数据结构 3\o"CurrentDocument"2.2所用方法及其原理说明 3\o"CurrentDocument"第三章详细设计 4\o"CurrentDocument"3.1详细设计方案 4\o"CurrentDocument"3.2模块设计 4\o"CurrentDocument"3.21二叉树定义 4\o"CurrentDocument"3.22树状显示二叉树设计 7\o"CurrentDocument"3.22主函数设计 10\o"CurrentDocument"第四章调试和操作说明 11\o"CurrentDocument"4.1调试 11\o"CurrentDocument"4.2操作说明 12\o"CurrentDocument"第五章总结与体会 12\o"CurrentDocument"5.1本文的主要工作 12\o"CurrentDocument"5.2存在问题 12\o"CurrentDocument"5.3心得体会 12\o"CurrentDocument"致谢 13\o"CurrentDocument"参考文献 14第一章需求分析课程设计题目树状显示二叉树：编写函数displaytree（二叉树的根指针，数据值宽度，屏幕的宽度）输出树的直观示意图。输出的二叉树是垂直打印的，同层的节点在同一行上。［问题描述］假设数据宽度datawidth=2,而屏幕宽度screenwidth为64=26,假设节点的输出位置用（层号，须打印的空格数）来界定。第0层：根在（0，32）处输出；第1层：因为根节点缩进了32个空格，所以下一层的偏移量（offset）为32/2=16=screenwidth/22。即第一层的两个节点的位置为（1，32-offset）,（1,32+offset）即（1，16），（1，48）。第二层：第二层的偏移量offset为screenwidth/23。第二层的四个节点的位置分别是（2，16-offset），（2，16+offset），（2，48-offset），（2，48+offset）即（2，8），（2，24），（2，40），（2，56）。第i层：第i层的偏移量offset为screenwidth/2i+1。第i层的每个节点的位置是访问第i-1层其双亲节点时确定的。假设其双亲的位置为（i-1,parentpos）。若其第i层的节点是其左孩子，那末左孩子的位置是（i,parentpos-offset）,右孩子的位置是（i,parentpos+offset）。［实现提示］利用二叉树的层次遍历算法实现。利用两个队列Q，QI。队列Q中存放节点信息，队列QI中存相应于队列Q中的节点的位置信息，包括层号和需要打印节点值时需要打印的空格数。当节点被加入到Q时，相应的打印信息被存到QI中。二叉树本身采用二叉链表存储。课程设计任务及要求1.21课程设计目的据结构是计算机专业的核心课程，是一门实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段，要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C（C++）程序并上机调试的基本方法，还要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。1.22设计要求1、 课程设计题目每组一题，每个学生必须独立完成；2、 课程设计时间为2周；3、 设计语言C（C++）不限；4、上机任务1）选择合适的数据结构，并定义数据结构的结构体；2）根据程序所要完成的基本要求，设计出完整的算法；3）设计出主程序（main函数），使其成为完整的程序。6、 上机时间：按照实验室上机时间安排计划执行7、 无论在校外、校内，都要严格遵守学校和所在单位的学习和劳动纪律、规章制度，学生有事离校必须请假。课程设计期间，无故缺席按旷课处理；缺席时间达四分之一以上者，其成绩按不及格处理。课程设计思想二叉树是一种树形结构，它的特点是每个结点至多有两棵子树，即二叉树中不存在度大于2的结点，并且二叉树的子树有左右之分，其次序不能任意颠倒。本设计主要根据二叉树的性质原理为设计的主体思路，二叉树的性质如下:性质1：在二叉树的第i层上至多有2i-i个结点（i>=l）；，性质2：深度为K的二叉树至多有2k-i个结点（K>=1）；性质3：如果一棵有n各结点的完全二叉树的结点按层次编号，则对任一结点i（1〈二i〈二n）,有：（1） 若2i>n,则结点无左孩子，否则其左孩子是结点2i；（2） 若2i+1>n,则结点i无右孩子，否则其右孩子为2i+1；另外，本设计利用二叉树的广度优先搜索算法实现。利用两个队列Q,QI。队列Q中存放节点信息，队列QI中存相应于队列Q中的节点的位置信息，包括层号和需要打印节点值时需要打印的空格数。当节点被加入到Q时，相应的打印信息被存到QI中。二叉树本身采用二叉链表存储。本设计应用了C语言中的类来自定义头文件，将任务分成多个的模块，增强了可读性和简单性，同时为日后的编写，调试，维护提供了极大地方便。软件运行环境及开发工具本设计用到的软件是MicrosoftVisualC++6.0程序开发软件，MicrosoftVisualC++6.0是20世纪90年代中期由美国微软公司推出的一个强大的Windows应用程序开发平台，是“真正的程序员”首选的开发工具之一，也是有志于程序设计的程序员、大中专院校学生进入高级程序设计领域的首选软件之一。MicrosoftVisualC++6.0程序开发软件提供了一个可视化集成编程环境，能自动生成Windows应用程序的共有部分，帮助程序设计人员直接切入实际功能部分的代码编制主题，从而大大简化了复杂的Windows应用程序开发过程，极大的提高了程序设计的效率，其次，VC++功能强大，内容浩瀚在该环境下用户可以开发有关C和C++的各种应用程序，应用程序的开发包括建立、编辑、浏览、链接和调试等操作。第二章概要设计数据结构树状显示二叉树是二叉树的一种自然显示方法，本设计结果将二叉树形象的显示在屏幕上，直观易懂。因此本设计将对树状显示二叉树的设计步骤进行详细说明。首先得构造一个数组来存储整个二叉树的结点信息，建立两个队列Q和QI,队列Q中存放节点信息，队列QI中存相应于队列Q中的节点的位置信息，包括层号和需要打印节点值时需要打印的空格数。当节点被加入到Q时，相应的打印信息被存到QI中。然后通过插入排序算法来构造一个二叉树，并用二叉树的层次遍历来使二叉树有顺序的存入队列Q，最后通过队列QI使得二叉树树状的显示在屏幕上。该程序的主要流程图如图2-1所示。所用方法及其原理说明本设计主要运用了树的广度优先搜索和队列的先进先出的特点，树的广度优先搜索功能如下：假设从图中某顶点v出发，在访问了v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。队列是一种先进先出的线性表，它只允许在表的一端进行插入，而在另一端删除元素。在队列中允许插入的一端叫队尾，允许删除的一端叫对头。队列的示意图如下：艺出心—a!a2a3..,an疋““对头 队尾图1二叉树示意图第三章详细设计详细设计方案本设计利用两个队列Q,QI,队列Q中存放结点信息，队列QI中存相应于队列Q中的节点的位置信息，包括层号和需要打印节点值时需要打印的空格数。当节点被加入到Q时，相应的打印信息被存到QI中。用二叉树(二叉树本身采用二叉链表存储)的层次遍历算法实现了二叉树的树状显示。本设计应用了C语言中的类来自定义头文件，将任务分成多个的模块，增强了可读性和简单性，同时为日后的编写，调试，维护提供了极大地方便。模块设计本程序包括三部分，即二叉树定义部分(MyHeap.h)，树状显示二叉树的实现(MyHeap・cpp)部分以及最重要的主函数部分(main.cpp)。下面将对各模块设计思想及设计方法进行详细的说明。3.21二叉树定义需要显示的二叉树的示意图如下：04816i-jiLirefitpoa-offeaci.尹renSpFeiLi-1cpn「04816i-jiLirefitpoa-offeaci.尹renSpFeiLi-1cpn「umLpg2.242.402.82,56图2树状二叉树#include<stdio・h>#include<stdlib・h>#include<malloc・h>#defineTElemTypechar#defineOK1#defineERROR0#defineOVERFLOW-2#defineTRUE1#defineFALSE0typedefintStatus;#defineMAXQSIZE100typedefstructBiNode{intdata;structBiNode*lchild;structBiNode*rchild;}BiNode,*BiTree;typedefintElemType;typedefstruct{ElemType*base;/*数组首地址*/intfront; /*头指针,若队列不空，指向队列头元素*/intrear; /*尾指针,若队列不空，指向队列尾元素的下一个位置*/}SqQueue;typedefstruct{intlevel;intpos;boolenter;intspaceNum;}DisplayInfo;Statusinsert(BiTreebt,intkey){BiTreep,q,newNode;newNode=(BiTree)malloc(sizeof(BiNode));p=NULL;q=bt;while(q){p=q;if(key<q->data)q=q->lchild;elseq=q->rchild;}if(p){if(key<p->data)p->lchild=newNode;elsep->rchild=newNode;}elsebt=newNode;}StatusInitQueue(SqQueue*Q){Q->base=(ElemType*)malloc(MAXQSIZE*sizeof(ElemType));if(!Q->base){printf("分配空间失败!");returnOVERFLOW;}Q->front=0;Q->rear=0;returnOK;}EnQueue(SqQueue*Q,ElemTypee){/*插入元素e为新的队尾元素*/if((Q->rear+1)%MAXQSIZE==Q->front){printf("队列满了!");returnERROR;}Q->base[Q->rear]=e;Q->rear=(Q->rear+1)%MAXQSIZE;}DeQueue(SqQueue*Q,ElemType*e){/*删除队头元素，并由e返回其值*/if(Q->front==Q->rear)returnERROR;*e=Q->base[Q->front];Q->front=(Q->front+1)%MAXQSIZE;}StatusIsEmpty(SqQueue*Q){if(Q->front==Q->rear)returnOK;elsereturnERROR;}BiTreeCreateBiTree(BiTreebt){charch;scanf("%c",&ch);if(ch=='.')bt=NULL;else{bt=(BiTree)malloc(sizeof(BiNode));/*生成根结点*/bt->data=ch;bt->lchild=CreateBiTree(bt->lchild);/*生成左子树*/bt->rchild=CreateBiTree(bt->rchild);/*生成右子树*/}returnbt;}程序功能说明：该段程序分别用三个结构体定义了二叉树、队列和树的显示信息，还包含该程序需要用到C语言头文件、数据定义和二叉树的建立、队列的插入与删除等函数，是整个程序的基础。3.22树状显示二叉树设计主要运用树的广度优先搜索，树的广度优先搜索功能如下：假设从图中某顶点v出发，在访问了v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。广度优先搜索的过程如下：VIv3①©v5v6©v83@a3VIv3①©v5v6©v83@a3 广度优先搜索二叉树voidBFSDisplayTree(BiTreebt){SqQueueQ;BiTreecurNode;printf("BFSDisplayTree:\n");EnQueue(&Q,curNode);while(!IsEmpty(&Q)){DeQueue(&Q,&curNode);*curNode=Q.front;

if(curNode->lchild)EnQueue(&Q,curNode->lchild);if(curNode->rchild)EnQueue(&Q,curNode->rchild);printf("%d",curNode->data);}printf("\n");}voidNatureDisplayTree(BiTreebt){inti;SqQueueQ;SqQueueQI;intscreenWidth=64;intdataWidth=2;DisplayInfoinfo;DisplayInfopreInfo;BiTreecurNode;DisplayInfocurInfo;if(!bt){printf("Treeisempty!\n");return;}printf("NatureDisplayTree:\n");EnQueue(&Q,bt);/*若二叉树bt非空，则根结点bt入队，开始层次遍历info.level=1;info.enter=true;info.spaceNum=screenWidth>>info.level;info.pos=info.spaceNum;EnQueue(&QI,info);preInfo=info;while(!IsEmpty(&Q)){curNode=Q.front;DeQueue(&Q,&e);curNode=QI.front;if(!curInfo.enter)printf("\n\n");for(i=0;i<curInfo.spaceNum;i++)printf("");printf("%2d",curNode->data);DeQueue(&QI,&curNode);if(!curNode->lchild){EnQueue(&Q,curNode->lchild);Info.level=curInfo.level+1;Info.pos=curInfo.pos-(screenWidth>>Info.level);if(Info.level>preInfo.level){Info.enter=true;Info.spaceNum=Info.pos;}else{Info.enter=false;Info.spaceNum=Info.pos-preInfo.pos;}Info.spaceNum-=dataWidth;EnQueue(&QI,Info);preInfo=Info;}if(!curNode->rchild){EnQueue(&Q,curNode->rchild);info.level=curInfo.level+1;Info.pos=curInfo.pos+(screenWidth>>info.level);if(info.level>preinfo.level){info.enter=true;info.spaceNum=info.pos;}else{info.enter=false;info.spaceNum=info.pos-preInfo.pos;}info.spaceNum-=dataWidth;EnQueue(&QI,info);preinfo=info;}}printf("\n");}voidDisplay(int*A,intn){inti;printf("ArrayInfo:\n");for(i=0;i<n;i++){printf("%d\t",A[i]);}printf("\n");}程序功能说明：程序先用广度优先搜索遍历二叉树(类似于二叉树的按层次遍历)，使二叉树的各结点依次进入队列Q,然后定义了另一个队列QI,它和队列Q形成一一对应关系，其中存放Q中结点的打印信息,每次从Q中取出一个节点curNode,对应的打印信息为curInfo，当结点的输出位置用层号level(需打印的空格数)来界定，当level和….不同时，换行，通过Q与QI的结合，最后使二叉树树状的显示在屏幕上。3.22主函数设计主函数是一个程序最重要的部分，本程序也不例外。voidmain(){BiTreebt,t;inti;intdata[9]={5,4,2,7,1,9,3,0,6};Display(data,9);//打印数组for(i=0;i<9;i++)insert(bt,data[i]);bt=CreateBiTree(bt);BFSDisplayTree(bt); //广度优先打印二叉树NatureDisplayTree(bt); //自然显示打印二叉树}程序功能说明：该主函数首先定义了存储二叉树结点的数组，并将数组打印出来，然后定义了一个二叉树对象myBST,调用函数insert(data[i])将数组中的树依次插入到二叉树中，最后用队列Q和QI实现了二叉树的广度优先搜索，把二叉树以树状的形式显示到屏幕上。第四章调试和操作说明调试1．在课程设计的过程中，写代码是一个方面，程序的调试才是最重要的，它是一个相当繁琐的过程，有许多新的问题需要被解决；但是同时它也是一个比较重要的过程，因为在程序调试的过程中你可以学到很多新的知识，从而增加你编程的经验。在程序中有下面的代码：if(np->key二二1),刚开始做的时候，写成了if(np->key=l)，错误不太容易发现，主要是混淆了判断语句与赋值语句的区别。查到一个小小的建议，变量和常量比较时，把常量放在==号的左边，这样如果你错写为=时，编译器就会报出禁止为常量赋值的错。因此，好的编程习惯的很重要。2、程序编写好后将程序在VC++环境中经过编译确认无误后调试并运行，得运行结果如下图。r人二丨」k口XK丄操作说明程序还提供二叉树的结点个数及结点值的修改，若想修改结点的个数和结点的值，只需找到主函数(main())中的“intdata[9]={5,4,2,7,l,9,3,0,6}”语句，把数组个数“9”改成结点的个数，把数组元素改成需要的结点值即可。如把主函数中“intdata[9]={5,4,2,7,1,9,3,0,6}”改成“intdata[12]={6,&4,3,1,7,9,5,2,10,12,15}”后的输出结果如下：第五章总结与体会本文的主要工作本设计的主要难点在于二叉树的层次遍历、队列模型的建立及队列与队列之间建立联系的设计与分析，以及程序的编译与运行。存在问题虽然经过努力，最终完成了树状显示二叉树的设计，但是我觉得在设计过程中还存在很多不足，例如：对一些C语言的编程思路不清楚，对实验软件运行步骤方法不熟悉，使得我在设计过程中遇到很多困难。心得体会紧张的两周数据结构实训很快过去了，通过这周的学习使我巩固了以前的知识并在此基础上对数据结构的特点和算法有了更深的了解，数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且已经成为其他理工专业的热门选修课。从设计中我学到了很多东西，最重要的是去做好一件事的心态，拿到题目的时候也许你觉得很难，但是只要你充满信心，一步一个脚印去实现它，不要怕麻烦，功夫不怕有心人，相信你一定会成功的。所以说，坐而言不如立而言，对于这些编程设计还是应该自己动手实际操作才会有深刻理解。首先这两周的学习，使我在巩固了原有的理论知识上，培养了我灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力，使我体会到自身知识和能力在实际中的应用和发挥。其次，激发了我创新意识，开发创造的能力和培养沟通能力。另外，让我进一步熟悉了数据结构的设计应用。每一处编码都是在反复的熟悉数据结构的结构特性，及其语法、函数和程序设计思想的过程，对我数据结构的学习和提高很有益处，并且使我明白了程序设计过程有如解决一实际问题，从解决实际问题的角度，我们可以这样来看：第一要了解这个问题的基本要求，即输入、输出、完成从输入到输出的要求是什么；第二，从问题的要害入手，从前到后的解决问题的每个方面，即从输入开始入手，着重考虑如何从输入导出输出，在这个过程中，可确定所需的数据结构的基本类型——线性表、栈、队列、串、数组、广义表、树和二叉树以及图等，然后确定处理过程——算法，可得最后结论。最后，在这次实训过程中，我深刻的认识到了自己在学习方面的不足之处，我知道我还有太多的基本的思想没有真正的理解，当然我不会灰心，我会在以后的日子里努