1、目 录 1 前言1 2 需求分析 1 2.1 课程设计目的 1 2.2 课程设计任务 1 2.3 设计环境 1 3 概要设计 1 3.1 数据结构设计 1 3.2 模块设计 6 4 详细设计 7 5 测试分析 . 14 6 课程设计总结 . 16 参考文献 . 17 致谢 17 1 1 前言 二叉树是一种数据结构，用于保存和处理树状的数据，比如家谱。他的应用极 为广泛，因为根据数据结构的理论，任何复杂的树够可以转换为二叉中并进行处 理，二叉树在排序、查找、大规模数据索引方面有很多很多应用， 而且二叉树排序是 简单算法排序中速度最快的。 在二叉树的一些应用中，常常要求在树中查找具有某种特征的节点
2、，或者对树 中全部节点逐一进行某种处理。这就提出了遍历二叉树。根据遍历的方向的选择， 就有了前序遍历，中序遍历和后序遍历以及层次遍历二叉树。因此掌握二叉树的各 种遍历二叉树算法非常重要，而且高效的遍历算法能够节省很多成本。 2 需求分析 2.1 课程设计目的 学生在教师指导下运用所学课程的知识来研究、解决一些具有一定综合性问题 的专业课题。通过课程设计（论文），提高学生综合运用所学知识来解决实际问题、 使用文献资料、及进行科学实验或技术设计的初步能力，为毕业设计（论文）打基 础。 2.2 课程设计任务 （一）任务 二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算 法的实现，
3、应包含建树的实现。 要求：多个测试用例,且画出其二叉树。 2.3 设计环境 （1）WINDOWS 2000/2003/XP/7/Vista系统 （2）Visual C+或TC集成开发环境 3 概要设计 3.1 数据结构设计 2 1、二叉树的抽象数据类型定义 ADT BinaryTree 数据对象 D：D 是具有相同特性的数据元素的集合。 数据关系 R： 若D=，则R=，称BinaryTree 为空二叉树； 若D，则R=H，H是如下二元关系； （1）在D中存在惟一的称为根的数据元素 root，它在关系 H 下无前驱； （2）若D-root，则存在D-root=D1,Dr，且D1Dr =； （3）
4、若D1，则 D1中存在惟一的元素x1，H，且存在 D1上 的关系 H1 H；若 Dr，则 Dr中存在惟一的元素xr，H，且存在 Dr上的关系Hr H；H=,H1,Hr； （5）(D1,H1)是一棵符合本定义的二叉树，称为根的左子树；(Dr,Hr) 是一棵符合本定义的二叉树，称为根的右子树。 基本操作： InitBiTree( t=creatree(); printf(“n递归先序序列:“); preorder(t); printf(“n递归中序序列:“); inorder(t); printf(“n递归后序序列:“); postorder(t); printf(“n非递归中序遍历序列:“);
5、nrinorder(t); printf(“n层次遍历序列:“); levelorder(t); 2、数据类型的定义 （1）二叉树的二叉链表存储类型 typedef struct node char data; struct node *lchild,*rchild; bitnode,*bitree; （2）队列类型的定义 typedef struct elements 1 elemN; /*存放二叉链表结点指针*/ int front;int rear; int LEN ; bitree qN; 3、主要模块的算法描述 （1）建立二叉树 初始化队列，建立一棵二叉树 /*按完全二叉树形式输入各
6、结点,创建一棵二叉树*/ bitree creatree() /*队列初始化*/ 9 int front=0,rear=-1;char ch; bitree root,s; printf(“请输入字符并以#结束n“); ch=getchar(); while (ch!=#) if (ch!=$) s=(bitree)malloc(LEN); s-data=ch; s-lchild=s-rchild=NULL; else s=NULL; rear+; qrear=s; if (rear=0) root=s; else if (s else qfront-rchild=s; if (rear%2=0) front+; ch=getchar(); return root; 10 二叉树建立的流程图如图4.2： 图 4.2 二叉树的建立 （2）递归先序遍历算法 利用文件写入二叉树的各个结点。对二叉树进行递归先序遍历 v
