课程设计判断完全二叉树.docx

1、课程设计判断完全二叉树长治学院课程设计报告课程名称：数据结构课程设计 设计题目： 完全二叉树判断 系 别： 计算机系 专 业： 组 别： 第三组 学生姓名: 学 号: 起止日期: 指导教师: 第一章 需求分析 21.1课程设计任务及要求 21.2课程设计思想及开发环境 2第二章 概要设计 32.1 总体方案 32.2 功能模块说明 3第三章调试与操作说明 4第四章课程设计总结与体会 4第五章致谢 7第六章参考文献 7附录（源代码） 7第一章 需求分析1.1课程设计任务及要求该课程设计的题目为：完全二叉树的判别。也就是对于输入的二叉树进行判定，看是否为完全二叉树。为实现此次课程设计的完成，对程序

2、设计作了相应的定义与限制。首先，为了输入的简洁，将树的结点树不大于20；其次，对于二叉树的输入就按照前序遍历的顺序进行输入；最后，对于程序的测试，应该从正反两面进行测试，即输入一个是完全二叉树和一个不是完全二叉树的。由于输入二叉树时，对于不是完全二叉树的，有的结点会没有左子树或右子树，甚至两子树都没有，为跟好的表示没有子树的情况，在此次程序设计中用“.”来表示1.2课程设计思想及开发环境编写语言： C语言开发工具： Visual C+ Visual Studio 6.0VC+是微软公司开发的一个IDE(集成开发环境)。学习VC要了解很多Windows平台的特性并且还要掌握MFC、ATL、COM

3、等的知识， VC基于C，C+语言，主要由是MFC组成，是与系统联系非常紧密的编程工具，它兼有高级，和低级语言的双重性，功能强大，灵活，执行效率高，几乎可说VC在 Windows平台无所不能。 最大缺点是开发效率不高。对于二叉树的构造，可以运用插入建立，还可以用递归建立。在此次设计中运用的是递归建立。运用队列的进队函数进行对二叉树的结点的输入。对于进队的第一个数据为二叉树的根结点，如果为非空，则继续输入第二个进队元素，将其设置为该根结点的左子树，然后将该左子树作为新的根结点，依次进行到下一层的结点，直至到达叶节点（即既没有左子树也没有右子树），然后对于这以后进队的元素则作为右子树，用相同的方法建

4、树。第二章概要说明2.1判定是否为完全二叉树的算法 判定完全二叉树，首先要知道什么是完全二叉树，对完全二叉树定义以前，要明白满二叉树的定义。一棵深度为k且有2k-1个结点的二叉树称为满二叉树。对满二叉树的你借点进行连续编号，约定编号从根结点起，自上而下，自左而右。由此引出完全二叉树的定义。深度为k的，右n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树的编号从1至n的结点一一对应时，称之为完全二叉树。所以对于二叉树的判定，假如某一结点有右子树但没有左子树则该树不是完全二叉树。如果某一结点没有右子树或没有左子树，但是其后的结点有左子树或右子树，则该树不是完全二叉树。根据这种判定方法，可

5、以判定其是不是完全二叉树。2.2功能模块说明程序各模块之间的关系图图1程序模块关系图第三章调试与操作说明3.1编码设计编码建立上一步详细设计结果的基础上，对编码进行调试。3.2调试调试一向是我感觉很头疼的一个环节，因为程序中会因为各种各样的原因出现很多错误。所以在调试前应该做好充分的准备，比如说准备一本高级语言程序设计的教材以及先建立好工程和文件。在设计中，我使用的是Visual C+ 6.0为平台对程序进行调试。调试之前就是要把源程序输入进去，我建立了一个.c文件。输完源代码后对代码进行编译，出现了诸多问题。比如说，会在语句后面丢掉分号、输入的标点符号不是英语输入中的而是中文输入中的、语法错

6、误、函数调用不匹配的问题等等。对于这些错误需要相当大的耐性，但是都不难解决，只要细心的检查程序就可以更正了。可以在调试错误中找到出错的地方，根据错误信息提示进行改错。对于有的错误提示并不明白是什么错误，也是通过查资料书和在网络上搜索到底是什么错误，在寻求解决方法。在编译没有错误之后开始组建。在组建出现了内存泄露，这是在编程中经常出现的问题。产生这种问题的原因也有很多种。大多数情况下就是指针出现错误。于是我就开始检查程序中使用到指针的地方，进行检测，最后查出来问题并更正了。调试没有错误以后，就是进行程序执行。4.程序运行结果 系统菜单图：图2人机交互界面按照扩展先序遍历序列建立二叉树：图3建立二

7、叉树打印输入的二叉树： 图4打印输入的二叉树判断完全二叉树： 图5得出结论 第四章课程设计总结与体会在这次课程设计中，我还学到了许多东西。对于程序设计中的错误处理也有了更多的认识，也掌握了关于内存泄露的相关知识。而且对于二叉链表也有了更好的理解，对于用递归法建立二叉树也有了更多的理解。对于程序设计也有了更好的理解，程序设计不光只是要得到相应的运行结果就可以的，还有考虑它的健壮性，以及与用户之间的交流，要能够直观的，简洁的表示该程序的使用方法和功能，而且还要有很好的重复使用性，这样的算法才是好的算法。当然在这方面上我还有很多的不足，需要更多的努力，在反复实践过程中不断地完善自己在这方面的能力。这

8、次的设计，让我大大地感觉到，对于程序设计中，对语言再熟悉也比不过在设计中算法和结构分析的真知灼见。当然，成功的程序设计是要建立在熟悉语言的基础之上的。平时语言的基本功要扎实。而每一次程序设计的经营能大大地增加对语言的熟悉和感知。程序设计的技能来自多方面，每一次的亲自实践、思考揣摩、刨根问底就会让自己更加清楚所欠缺的是什么。所以，现在觉得在设计实践中作为参考的书册阅读和研究远远比过单纯的阅读，因为它是在最紧迫的时间上填补自己最紧迫的不足。第五章 致谢感谢所有帮助我的人，是你们不计回报的付出，除了帮我完成了这份课程设计，也让我感受到了身边的温暖。感谢马强老师，您平常的教导，到现在我才明白是多么的有

9、用，谢谢您的督促。感谢陌生的朋友，在知道我需要帮助后，第一时间提供了具有很大价值的参考资料，也明白自己还需要更多的努力。这次的设计，让我大大地感觉到，对于程序设计中，对语言再熟悉也比不过在设计中算法和结构分析的真知灼见。当然，成功的程序设计是要建立在熟悉语言的基础之上的。平时语言的基本功要扎实。而每一次程序设计的经营能大大地增加对语言的熟悉和感知。程序设计的技能来自多方面，每一次的亲自实践、思考揣摩、刨根问底就会让自己更加清楚所欠缺的是什么。所以，现在觉得在设计实践中作为参考的书册阅读和研究远远比过单纯的阅读，因为它是在最紧迫的时间上填补自己最紧迫的不足。第六章 参考文献1：严蔚敏，吴伟民，数

10、据结构（C语言版），北京：清华大学出版社，2009年2：王昆仑，李红。数据结构与算法。北京：中国铁道出版社3：耿国华，数据结构北京：高等教育出版社，20054：谭浩强，C程序设计（第三版）M，北京：清华大学出版社，2008年附录 源代码/判断完全二叉树算法描述#include#include#define true 1#define false 0/二叉树数据结构typedef struct BiTNodechar data;struct BiTNode *LChild, *RChild;BiNode,*BiTree;/含头尾指针的链队列数据结构typedef struct QueueNode

11、BiTree data;struct QueueNode *next;LinkQueueNode;typedef struct LinkQueueNode *front;LinkQueueNode *rear;LinkQueue;/函数声明void Print(BiTree *root);void Choose(int choice,BiTree *root);void ReadPreOrder(BiTree *root);void PrintPreOrder(BiTree root);int CompleteBinaryTree(BiTree root);int InitQueue(Link

12、Queue *Q);int EnterQueue(LinkQueue *Q,BiTree x);int DeleteQueue(LinkQueue *Q);/主函数int main()BiTree root; root=NULL;/初始化 无头结点system(color b);Print(&root);while(true) printf(Press enter to continue.); getchar(); getchar(); system(cls); Print(&root);return 0;void Print(BiTree *root)int choice;printf(-n

13、);printf(使用说明:本程序可实现基于队列的广度优先遍历算法判断完全二叉树.n);printf(-n);printf(1.输入扩展先序遍历序列并建立对应的二叉树.n);printf(2.打印当前的二叉树的扩展先序遍历序列.n);printf(3.判断当前的二叉树是否为完全二叉树.n);printf(4.按其它任意键退出.n);printf(-n);printf(请选择你要的操作:);scanf(%d,&choice);getchar();/此处getchar存储回车，避免对后面函数的影响！（很重要！）Choose(choice,root);void Choose(int choice,B

14、iTree *root)switch(choice)case 1: ReadPreOrder(root); break;case 2: PrintPreOrder(*root); printf(n); break;case 3: if(CompleteBinaryTree(*root) printf(当前二叉树是完全二叉树！n); else printf(当前二叉树不是完全二叉树！n); break;default: exit(0);void ReadPreOrder(BiTree *root)/先序遍历二叉树，root为指向二叉树（或某一子树）根结点的指针char ch;ch=getchar

15、();/使用getchar输入时必须谨记前面有没有多余的回车if(ch=.) (*root)=NULL;else (*root)=(BiNode *)malloc(sizeof(BiNode); (*root)-data=ch; ReadPreOrder(&(*root)-LChild); ReadPreOrder(&(*root)-RChild);void PrintPreOrder(BiTree root)if(root!=NULL) printf(%c,(root)-data); PrintPreOrder(root-LChild); PrintPreOrder(root-RChild)

16、;else printf(.);/完全二叉树判断函数/先利用队列找出二叉树中第一个没有包含两个孩子的节点（即第一个非正常节点）/从第一个非正常节点后面开始出队的所有节点均不含子节点则该二叉树为完全二叉树int CompleteBinaryTree(BiTree root)int flag;LinkQueue BiNode;/创建队列InitQueue(&BiNode);/初始化队列EnterQueue(&BiNode,root);/将根节点入队while(BiNode.front!=BiNode.rear)/当队列不为空时进行广度优先扫描二叉树/当发现非正常节点时跳出循环 if(BiNode.

17、front-next-data-LChild!=NULL&BiNode.front-next-data-RChild!=NULL) /当左右孩子均有 /左右孩子入队 EnterQueue(&BiNode,BiNode.front-next-data-LChild); EnterQueue(&BiNode,BiNode.front-next-data-RChild); DeleteQueue(&BiNode);/节点出队 else break;/下面分三种情况讨论/左孩子没有 右孩子没有，继续扫描if(BiNode.front-next-data-LChild=NULL&BiNode.front

18、-next-data-RChild=NULL) DeleteQueue(&BiNode); while(BiNode.front!=BiNode.rear) if(BiNode.front-next-data-LChild!=NULL | BiNode.front-next-data-RChild!=NULL) return false; DeleteQueue(&BiNode); return true;/左孩子有 右孩子没有，继续扫描else if(BiNode.front-next-data-LChild!=NULL&BiNode.front-next-data-RChild=NULL)

19、 EnterQueue(&BiNode,BiNode.front-next-data-LChild); DeleteQueue(&BiNode); while(BiNode.front!=BiNode.rear) if(BiNode.front-next-data-LChild!=NULL | BiNode.front-next-data-RChild!=NULL) return false; DeleteQueue(&BiNode); return true;/左孩子没有 右孩子有，非完全二叉树else if(BiNode.front-next-data-LChild=NULL&BiNode

20、.front-next-data-RChild!=NULL) return false;/队列的初始化函数int InitQueue(LinkQueue *Q)/将Q初始化为一个空的链队列Q-front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode);if(Q-front!=NULL) Q-rear=Q-front; Q-front-next=NULL; return true;else return false;/溢出/入队函数int EnterQueue(LinkQueue *Q,BiTree x)/将数据元素x插入到队列Q中LinkQueueN

21、ode *NewNode;NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode);if(NewNode!=NULL) NewNode-data=x; NewNode-next=NULL; Q-rear-next=NewNode; Q-rear=NewNode; return true;else return false;/溢出/出队操作int DeleteQueue(LinkQueue *Q)/将队列Q的队头元素出队，并存放到x所指的存储空间中LinkQueueNode *p;if(Q-front=Q-rear) return false;/队列为空 均指向头结点p=Q-front-next;Q-front-next=Q-front-next-next;/队头元素p出队if(Q-rear=p)/如果队中只有一个元素p，则p出队后成为空队 Q-rear=Q-front;free(p);/释放存储空间return true;指导教师评语： 指导教师签名： 年 月 日成绩评定项 目权重成绩1、设计过程中出勤、学习态度等方面0.12、设计技术水平0.43、编程风格0.24、设计报告书写及图纸规范程度0.3总 成 绩