二叉树实验报告

1、数据结构课程设计报告专 业 计算机科学与技术 班 级 3班 姓 名 学 号 指导教师 起止时间 2012.122013.1 课程设计：二叉树一、任务描述 二叉树的中序、前序、后序的递归、非递归遍历算法，应包含建树的实现。任务：设计一个程序，实现二叉树的前序、中序、后序的递归遍历运算。要求： （1）创建二叉树；（2）二叉树的前序、中序、后序的递归遍历运算实现。二、问题分析1、功能分析 分析设计课题的要求，要求编程实现以下功能：（1） 二叉树的建立即创建二叉树；（2） 二叉树的遍历二叉树的前序、中序、后序操作；2、数据对象分析 二叉树的遍历：包括前序、中序、后序将二叉树补充到完全二叉树在输入，才能

2、正确创建二叉树三、数据结构设计二叉树的建立和遍历的实现。有关的定义如下：typedef int Status;typedef char TElemType; /定义二叉树结点值的类型为字符型struct BiTNode /定义二叉树结点类型栈结点的类型TElemType data; /数据域 BiTNode *lchild,*rchild;/指针域;BiTNode *BiTree;四、功能设计（一）主控菜单设计程序运行后，输入提示，如下：“创建二叉树，请按前序序列输入各节点值：”正确输入二叉树后，提示“已成功创建二叉树”（二）程序模块结构由课题要求可将程序划分为以下几个模块（即实现程序功能所需

3、的函数）：l 创建二叉树的函数void CreateBiTree(BiTree &T);l 二叉树的前序遍历函数 Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType); l 二叉树的中序遍历函数Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType);l 二叉树的后序遍历函数Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType)；l 最简单的visit函数Status Visit(TElemType e);（三

4、）函数调用关系程序的主要结构（函数调用关系）如下图所示。 Main()Visit()CreateBiTree() PreOrderTraverse() InOrderTraverse() PostOrderTraverse()其中main()是主函数，它进行菜单驱动。BiTree T;int n=0;printf(创建二叉树，请按前序序列输入各节点值：n);CreateBiTree(T);printf(n); printf(已成功创建二叉树n);PreOrderTraverse( T,Visit);printf(n);InOrderTraverse(T,Visit);printf(n);Pos

5、tOrderTraverse(T,Visit);printf(n);（四）文件结构1、tree.h：二叉树相关的定义与声明2、tree.cpp：二叉树运算的实现5、mn.cpp：主函数 （五）各函数的算法设计1、CreateBiTree()算法原理：按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，构造二叉链表流程图： 输入一个字符 申请内存是否成功 生成根结点退出程序 构造左子树 构造右子树代码描述：void CreateBiTree(BiTree &T)char ch; ch=getchar(); /读入一个字符 printf(%c,ch); if (ch= ) T=NULL;

6、 else if (!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); /内存分配成功 T-data = ch; /生成根结点 CreateBiTree(T-lchild); CreateBiTree(T-rchild); 算法的时间复杂度分析：O(1)2、PreOrderTraverse ()算法原理：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树流程图：流程图 存在一个二叉树 是否为空树 访问根结点退出程序 先序遍历左子树 先序遍历右子树代码描述：Status PreOrderTraverse

7、(BiTree T,Status (*visit)(TElemType e) /*功能:先序遍历二叉树;参数:T为二叉树的根,visit为对结点的处理方法*/ if (T) /若根结点不空 if(visit(T-data) /访问根结点 if (PreOrderTraverse(T-lchild,visit) /先序遍历根的左子树 if(PreOrderTraverse(T-rchild,visit) /先序遍历根的右子树 return OK; 算法的时间复杂度分析：O(n)3、InOrderTraverse ()算法原理：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（

8、3）中序遍历右子树；流程图： 存在一个二叉树 是否为空树中序遍历左子树退出程序 访问根节点 中序遍历右子树代码描述：Status InOrderTraverse (BiTree T,Status (*visit)(TElemType e) /*功能:中序遍历二叉树;参数:T为二叉树的根,visit为对结点的处理方法*/ if (T) /若根结点不空 if (InOrderTraverse(T-lchild,visit) /中序遍历根结点的左子树 if(visit(T-data) /访问根结点 if(InOrderTraverse(T-rchild,visit) /中序遍历根结点的右子树 ret

9、urn OK; 算法的时间复杂度分析：O(n)4、PostOrderTraverse()算法原理：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点流程图： 存在一个二叉树 是否为空树后序遍历左子树退出程序 后序遍历右子树 访问根节点代码描述：Status PostOrderTraverse (BiTree T,Status (*visit)(TElemType e) /*功能:后序遍历二叉树;参数:T为二叉树的根,visit为对结点的处理方法*/ if (T) /若根结点不空 if (PostOrderTraverse(T-lchild,visit) /后序遍历根结点的左子树 if(PostOrderTraverse(T-rchild,visit) /后序遍历根结点的右子树 if(visit(T-data) /访问根结点 return OK; 算法的时间复杂度分析