数据结构课程设计叉树及应用.docVIP

“数据结构”课程设计 报告 系 （院）： 信息工程学院 设计题目： 二叉树及应用  课程设计目的 1、能够灵活地应用所学数据结构知识，根据加工数据对象的特征，选择适当的数据结构、存贮结构及相应算法，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2. 初步掌握各种算法在时间和空间的分析技巧；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3. 能够进行算法设计和程序设计，并且使所设计的程序结构清楚，正确易读，并上机调试通过；提高综合运用所学的理论知识和方法独立分析和解决问题的能力。 4.用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。 5. 培养较强的实习和实践能力；较强的分析问题和解决问题的能力。 课程设计任务与要求： 二叉树及应用 (1)二叉树的建立与遍历 [问题描述] 建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。 [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。 [测试数据] ABфDффCEфFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEF 中序：BDAEFC 后序：DBFECA [选作内容] 采用非递归算法实现二叉树遍历。 （2）打印二叉树结构 [问题描述] 按凹入表形式横向打印二叉树结构，即二叉树的根在屏幕的最左边，二叉树的左子树在屏幕的下边，二叉树的右子树在屏幕的上边。 例如： [测试数据] 由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空二叉树。 [实现提示] （1）利用RDL遍历方法； （2）利用结点的深度控制横向位置。 *2、打印树结构 [问题描述] 按凹入表形式打印树形结构。 例如： [测试数据] 由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空树。 [实现提示] （1）利用树的先根遍历方法； （2）利用结点的深度控制横向位置。 [实现提示] 　先创建一棵二叉树，按先序输入，输入空格表示为空具体细节如图所示: 一 需求分析 1、 有完整的界面； 2、 能够完整实现算法； 3、 有图形辅助说明； 4、 有适当的帮助功能； 二 概要设计 应用二叉树实现题目中的要求 三 详细设计 新建模块void CreateBiTree(BiTree *t)新建二叉树并储存。 先序遍历模块（递归法）: void PreOrder(BiTree p)对树进行先序遍历。 先序遍历模块（非递归法）: void PreOrder_f(BiTree p)对树进行先序遍历。 中序遍历模块: void InOrder(BiTree root)对树进行中序线索遍历。 后序遍历模块: void PostOrder(BiTree root)对树进行后序线索遍历。 打印二叉树模块：void PrintTree(BiTree bt,int nLayer)对树进行打印 删除模块: void Release(BiTree t)删除所有节点。 四 用户手册 注：任意输入一个数据后进入系统，然后根据系统提示操作即可。 五 测试成果 六 附录（源程序清单） #include stdio.h #include stdlib.h #define MAX 20 //#define nLayer 1 typedef char DataType; typedef struct Node { DataType data; struct Node *LChild; struct Node *RChild; }BiTNode,*BiTree; void CreateBiTree(BiTree *t){ /* 先序遍历创建二叉树*/ char s; BiTree q; //printf(\nplease input data:(exit for #)); s=getchar(); if(s== ){*t=NULL; return;} q=(Node *)malloc(sizeof(struct Node)); if(q==NULL){printf(Memory alloc failure!); } q-data=s; *t=q; CreateBiTree(q-LChild); /*递归建立左子树*/ CreateBiTree(q-RC