北理工数据结构实验遍历二叉树.doc

本科实验报告 实验名称： 遍历二叉树 课程名称： 数据结构 实验时间： 任课教师： 实验地点： 良乡机房 实验教师： 实验类型： □ 原理验证 ■ 综合设计 □ 自主创新 学生姓名： 学号/班级： 组 号： 学 院： 同组搭档： 专 业： 成 绩： 实验目的 1、熟悉VC环境，学习使用C语言实现树的基本操作。 2、通过编程、上机调试，进一步理解数、二叉数、拓展二叉数的基本概念。 3、了解并熟悉二叉数的存储结构及其各种操作，掌握各种二叉数的遍历方法。 4、锻炼动手编程，独立思考的能力。 二、实验题目 遍历二叉树 （1）问题描述 遍历二叉树： 要求：请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。 例如：124*5***3** 三、实验基础知识 线性表、二叉树的基本概念的熟练掌握并实际运用。并了解创建树、遍历二叉树的思想解决问题的能力 四、实验设计方法 1、概要设计 为实现上述程序功能，首先需要二叉树的抽象数据结构。 ⑴二叉树的抽象数据类型定义为： ADT BinaryTree { 数据对象D： D是具有相同特性的数据元素的集合。 数据关系R： 若D=Φ，则R=Φ，称BinaryTree为空二叉树； 若D≠Φ，则R={H}，H是如下二元关系； （1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱； （2）若D-{root}≠Φ，则存在D-{root}={D1,Dr}，且D1∩Dr =Φ； （3）若D1≠Φ，则D1中存在惟一的元素x1，root,x1∈H，且存在D1上的关系H1 ?H；若Dr≠Φ，则Dr中存在惟一的元素xr，root,xr∈H，且存在上的关系Hr ?H；H={root,x1,root,xr,H1,Hr}； （4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。 基本操作： CreateTree(T) 操作结果：按先序次序建立二叉链表表示的二叉树T PreOrderTraverse( T,Visit()) 初始条件：二叉树T已经存在，visit是对结点操作的应用函数 操作结果：先序遍历二叉树T ，对每个结点调用visit函数仅一次；一旦visit（）失败，则操作失败。 InOrderTraverse(T,Visit()) 初始条件：二叉树T已经存在，visit是对结点操作的应用函数 操作结果：中序遍历二叉树T ，对每个结点调用visit函数仅一次；一旦visit（）失败，则操作失败。 PostOrderTraverse(T,Visit)()) 初始条件：二叉树T已经存在，visit是对结点操作的应用函数 操作结果：后序遍历二叉树T ，对每个结点调用visit函数仅一次；一旦visit（）失败，则操作失败。 } ADT BinaryTree (2)、宏定义 #define ok 1 #define error 0 (3)主程序流程 主程序先调用CreateTree(BiTree T)函数，根据输入的先序序列构造出一棵二叉树，再依次调用PreOrderTraverse(BiTree T,int (*visit)(char e))，InOrderTraverse(BiTree T,int (*visit)(char e))，PostOrderTraverse(BiTree T,int (*visit)(char e))函数，对该二叉树进行先序、中序、后序遍历并输出结果。 (4)模块调用关系 由主函数调用创建模块，再调用计算模块，由计算模块将结果输出。 (5)流程图 开始 开始 生成二叉树CreatBiTree 先序遍历并输出PreOrderTraverse 中序遍历并输出InOrderTraverse 后序遍历并输出PostOrderTraverse 结束 五、实验结果及数据分析 1、124*5***3** 2、123**4**5*** 六、总结 此次编程实验，让我了解到全面思考的重要性，再开始的程序设计中，我只想着直接建立树，没想到用队列辅助，在开始的时候一直测试失败，这让我想到知识是相互联系的，必须全面学习。 七、附录 程序清单 #includestdio.h #includestdlib.h #define ok 1 #define error 0 /* 二叉链表的结点 */ typedef struct BiTNode { char data; struct BiTNode * lchi