二叉树的遍历和应用

内蒙古科技大学课程设计说明书PAGE13内蒙古科技大学本科生课程设计说明书题目：数据结构课程设计——二叉树的遍历和应用学生姓名：学号：专业：班级：指导教师：2013年5月29日内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目二叉树的遍历和应用指导教师时间2013.6.20——2013.6.30一、教学要求1.掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。二叉树的遍历和应用以二叉链表表示二叉树，在此基础上实现对二叉树的遍历和应用。要求设计类（或类模板）来描述二叉树，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：创建二叉树输出二叉树二叉树的先序、中序、后序遍历二叉树的按层遍历统计二叉树的叶子结点、计算二叉树的深度并设计主函数测试该类（或类模板）。三、设计要求及成果1.分析课程设计题目的要求

2.写出详细设计说明

3.编写程序代码，调试程序使其能正确运行

4.设计完成的软件要便于操作和使用

5.设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1.根据平时上机考勤、表现和进度，教师将每天点名和检查2.根据课程设计完成情况，必须有可运行的软件。

3.根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4.根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1．《数据结构（C语言版）》严蔚敏、吴伟民主编清华大学出版社2004.112．《数据结构课程设计案例精编（用C/C++描述）》，李建学等编著，清华大学出版社2007.23.《数据结构:用面向对象方法与C++语言描述》，殷人昆主编，

清华大学出版社2007.6目录内蒙古科技大学课程设计任务书 I目录 III第一章需求分析 41.1 课程设计目的 41.2 任务概述 41.3 课程设计内容 4第二章 概要设计 62.1 设计思想 62.2 二叉树的遍历 62.3 运行界面设计 7第三章 详细设计 83.1 二叉树的生成 83.2 二叉树的先序遍历 83.3 二叉树的中序遍历 93.4 二叉树的后续遍历 93.5 主程序的设计 9第四章 测试分析 124.1 二叉树的建立 124.2 二叉树的先序、中序、后序遍历 12第五章 课程设计总结 14附录：程序代码 15致谢 20第一章需求分析课程设计目的培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的动手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用；通过课程设计的实践，学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。任务概述学生必须仔细阅读《数据结构》课程设计方案，认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时向教师汇报。课程设计按照教学计划需要一周时间完成，一周中每天至少要上两小时的上机来调试C或C++语言设计的程序，总共至少要上机调试程序10小时。属教师安排上机时间学生不得缺席。课程设计内容二叉树的遍历和应用以二叉链表表示二叉树，在此基础上实现对二叉树的遍历和应用。要求设计类（或类模板）来描述二叉树，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：创建二叉树输出二叉树二叉树的先序、中序、后序遍历二叉树的按层遍历统计二叉树的叶子结点、计算二叉树的深度并设计主函数测试该类（或类模板）。概要设计设计思想以广义表格式输入一个二叉树，将其接收至一维数组中，利用栈结构建立二叉链表树；通过先、中、后访问根结点递归算法遍历二叉树。例如：a(c(,d)，f(g,))建立如下图所示二叉树。ccadfg二叉树的遍历结点为空结点为空N访问根节点先序遍历方式遍历左子树先序遍历方式遍历右子树结束Y开始运行界面设计主菜单主菜单先序递归遍历中序递归遍历后序递归遍历先序非递归遍历中序非递归遍历后序非递归遍历层次遍历结束将以广义表形式输入的二叉树接收到数组str[80]中，成功建立二叉树详细设计二叉树的生成structbtnode*bt;intk;{ intb;structbtnode*p,*t; printf("请输入b:"); scanf("%d",&b); if(b!=0) { p=(structbtnode*)malloc(sizeof(structbtnode)); p->d=b;p->lchild=NULL;p->rchild=NULL; if(k==0)t=p; if(k==1)bt->lchild=p; if(k==2)bt->rchild=p; creatbt(p,1);creatbt(p,2); } return(t);}二叉树的先序遍历pretrav(bt)/***二叉树的先序遍历***/structbtnode*bt;{ if(bt!=NULL) { printf("%d",bt->d); pretrav(bt->lchild); pretrav(bt->rchild); } return;}二叉树的中序遍历intrav(bt)/***二叉树的中序遍历**/structbtnode*bt;{ if(bt!=NULL) { intrav(bt->lchild); printf("%d",bt->d); intrav(bt->rchild); } return;}二叉树的后续遍历postrav(bt)/***二叉树的后序遍历****/structbtnode*bt;{ if(bt!=NULL) { postrav(bt->lchild); postrav(bt->rchild); printf("%d",bt->d); } return;}主程序的设计main(){ structbtnode*bt; intk;chari; bt=(structbtnode*)malloc(sizeof(structbtnode)); k=0; printf("输入字符'0',退出程序\n"); printf("输入字符'1',生成二叉树\n"); printf("输入字符'2',二叉树的先序遍历\n"); printf("输入字符'3',二叉树的中序遍历\n"); printf("输入字符'4',二叉树的后序遍历\n"); printf("请输入字符'0'-'4':"); scanf("%s",&i); for(;i!='0';) { switch(i) { case'1': { bt=creatbt(bt,k); break; } case'2': { pretrav(bt); printf("\n"); break; } case'3': { intrav(bt); printf("\n"); break; } case'4': { postrav(bt); printf("\n"); break; } default:break; } printf("输入字符'0',退出程序\n"); printf("输入字符'1',生成二叉树\n"); printf("输入字符'2',二叉树的先序遍历\n"); printf("输入字符'3',二叉树的中序遍历\n"); printf("输入字符'4',二叉树的后序遍历\n"); printf("请输入字符'0'-'4':"); scanf("%s",&i); } free(bt);}测试分析二叉树的建立二叉树的先序、中序、后序遍历先序中序后序课程设计总结二叉树是数据结构的的基本内容。虽然程序规模不大，我依然付出了努力，仍免不了各种错误的出现。编程过程需要很大的毅力和耐心，而且要有良好的思维和扎实的专业基础知识，所以我需要不断的学习，发现自身不足之处并改正它，逐步提高自己。培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的动手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用；通过课程设计的实践，学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。通过这次数据结构的课程设计，让我熟悉了二叉树的结构以及其相关的操作程序。尤其二叉树遍历的实现过程。从中我对数据结构这门课程的理解也更深层次。附录：程序代码#include<stdio.h>#include<stdlib.h>structbtnode{ intd; structbtnode*lchild; structbtnode*rchild;};structbtnode*creatbt(bt,k)/*二叉树的生成*/structbtnode*bt;intk;{ intb;structbtnode*p,*t; printf("请输入b:"); scanf("%d",&b); if(b!=0) { p=(structbtnode*)malloc(sizeof(structbtnode)); p->d=b;p->lchild=NULL;p->rchild=NULL; if(k==0)t=p; if(k==1)bt->lchild=p; if(k==2)bt->rchild=p; creatbt(p,1);creatbt(p,2); } return(t);}pretrav(bt)/***二叉树的先序遍历***/structbtnode*bt;{ if(bt!=NULL) { printf("%d",bt->d); pretrav(bt->lchild); pretrav(bt->rchild); } return;}intrav(bt)/***二叉树的中序遍历**/structbtnode*bt;{ if(bt!=NULL) { intrav(bt->lchild); printf("%d",bt->d); intrav(bt->rchild); } return;}postrav(bt)/***二叉树的后序遍历****/structbtnode*bt;{ if(bt!=NULL) { postrav(bt->lchild); postrav(bt->rchild); printf("%d",bt->d); } return;}main(){ structbtnode*bt; intk;chari; bt=(structbtnode*)malloc(sizeof(structbtnode)); k=0; printf("输入字符'0',退出程序\n"); printf("输入字符'1',生成二叉树\n"); printf("输入字符'2',二叉树的先序遍历\n"); printf("输入字符'3',二叉树的中序遍历\n"); printf("输入字符'4',二叉树的后序遍历\n"); printf("请输入字符'0'-'4':"); scanf("%s",&i); for(;i!='0';) { switch(i) { case'1': { bt=creatbt(bt,k); break; } case'2': { pretrav(bt); printf("\n"); break; } case'3': { intrav(bt); printf("\n"); break; }