数据结构实验五B.doc

数据结构与算法分析实验报告书学期：2014 2015 学年第 2 学期 班 级： 信息管理与信息系统2班 学 号： 1310030217 姓 名： 田洪斌 实验类别： （ ）基础型 （）设计型 实验时间： 成 绩： 信息管理系一、 实验内容1. 实现程序，按满二叉树给元素编号并输入的方式构造二叉树。2. 实现程序，构造二叉树的链式存储结构，并完成递归先序、中序、后序遍历操作。二、 实验目的1、 掌握二叉树的静态及操作特点；2、 掌握二叉树的各种遍历方法；3、 掌握二叉树的存储、线索化等在C语言环境中的实现方法；4、 掌握哈夫曼树的构造方法及编码方法。三、 需求分析用二叉树结构表示来完成输入、编辑、调试、运行的全过程。并规定：a. 手动输入数字建立二叉树b. 程序可以输入、调试、运行、显示、遍历c. 测试数据：用户手动输入的数据四、 系统设计1数据结构设计在本程序中对二叉树的存储主要用的是顺序存储结构，将二叉树存储在一个一维数组中。数据的输入输出都是采用整型数据进行。在主函数中只是定义数据类型，程序的实现功能化主要是在主函数中通过给要调用的函数参数来实现程序要求的功能。2 程序结构设计（1）程序中主要函数功能：main()/主函数menu()/菜单PostOrderTraverse(BiTree T)/后序遍历InOrderTraverse(BiTree T)/中序遍历PreOrderTraverse(BiTree T)/先序遍历二叉树BiTree CreateBiTree()/先序建立二叉树（2） 函数调用关系 见图7-1。mainmeun()PreOrderTraverse(BiTree T)InOrderTraverse(BiTree T)BiTree CreateBiTree()PostOrderTraverse(BiTree T)图图7-1 函数关系图五、 调试分析1.算法和函数中出现了一些系统无法识别的变量，照成程序出现了错误。原因是没有注意算法与源程序的区别。算法是简单的对源程序进行描述的，是给人阅读的，所以有些变量没有定义我们就能看懂。而程序中的变量一定要先定义才能够被引用，才能被计算机识别。2.在调试过程中遇到问题是利用C+程序进行调试的，找出错误并改正。3.数据输出函数运行不正常，经检查程序，发现是定义错误，更改后错误排除；六、 测试结果1运行时输入正确密码进入主界面，系统根据输入的数字选项来调用相应的函数。主要实现“功能选择”的界面，在这个界面里有显示系统的五大功能，根据每个功能前面的序号进行选择。以下为该界面：图7-2 主界面2.当选择1录入完成输入时，运行结果如下图：图7-3 二叉树的建立3.当建立完成输入二叉树的输出时，运行结果如下图：图7-4二叉树的输出4.当选择二叉树的先序遍历时，运行结果如下图： 图7-5二叉树的先序遍历5. 当选择二叉树的中序遍历时，运行结果如下图：图7-6二叉树的中序遍历6. 当选择二叉树的后序遍历时，运行结果如下图：图7-7二叉树的后序遍历测试中，分别录入2,5,8,3,7,9,1,0,7,3,8,0作为顺序表的初始值，输出数据后显示正常；经测试，本程序达到了先、中、后遍历的预期设计功能，具有一定的健壮性。七、 经验和体会本次试验利用C语言编程，完成了二叉树中的建立、输出、先序遍历、中序遍历、后序遍历等功能，提升了我的C语言编程能力，同时也加深了我对数据结构中关于二叉树结构有关基础概念、基本算法的理解，同时，通过程序的调试及观察分析程序运行的情况，也进一步增加了我调试程序的经验，并使我认识到了二叉树的结构。八、 程序源代码#include #define ElemType char/二叉树的二叉链表存储表示typedef struct BiTNode int data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/先序建立二叉树BiTree CreateBiTree() int x; BiTree T;printf(n请输入数字n); scanf(%d,&x); if(x=0)T=NULL; else T = (BiTree)malloc(sizeof(BiTNode); T-data = x; T-lchild = CreateBiTree(); T-rchild = CreateBiTree(); return T;/返回根节点/先序遍历二叉树void PreOrderTraverse(BiTree T) if(T) printf(%d,T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); /中序遍历void InOrderTraverse(BiTree T) if(T) PreOrderTraverse(T-lchild); printf(%d,T-data); PreOrderTraverse(T-rchild); /后序遍历void PostOrderTraverse(BiTree T) if(T) PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); printf(%d,T-data); /菜单void menu()printf(ntt*【菜单】*n);printf(nt1:二叉树的建立n);printf(nt2:二叉树的输出n);printf(nt3:二叉树的先序遍历n);printf(nt4:二叉树的中序遍历n);printf(nt5:二叉树的后序遍历n);printf(nt6:退出系统n);/主函数void main()int x,y=1;BiTree T;while(y)menu();printf(nt请选择菜单n);scanf(%d,&x);switch(x) case 1:T = CreateBiTree();break; case 2:PreOrderT