数据结构2叉数遍历.doc

内蒙古工业大学信息工程学院 实 验 报 告 课程名称： 实验名称 实验类型： 验证性综合性 □设计性□实验室名称： 班级： 学号： 姓名： 组别：同组人： 成绩： 实验日期： 实验报告撰写要求 实验前用预习报告纸撰写预习报告，预习报告包括以下内容 实验目的 实验用仪器设备、器材或软件环境 实验原理、方案设计、程序框图、预编程序等 实验过程中需要记录的实验数据表格 实验过程中，要认真观察，仔细记录 完成实验后用实验报告纸撰写实验报告，包括以下内容 仪器设备型号及编号 实验器材或软件环境 实验步骤、程序调试方法 实验数据处理及结果分析 实验中存在的问题 体会及思考题 报告撰写时，要求格式规范、书写整齐 预习报告成绩： 指导教师审核（签名）： 年 月 预习报告 实验二 二叉树遍历算法的设计 一、目的 本实验的目的是理解二叉树的逻辑结构和二叉链表存储结构，进一步提高使用理论知识指导解决实际问题的能力，并对算法性能进行分析。 题目 二叉树遍历算法的设计。 实验类型 设计性。 方案一采用递归算法实现二叉树遍历算法。 方案二采用非递归算法实现二叉树遍历算法。 四、要求及提示 要求： （1）两种算法以及各种基本操作（创建二叉树）定义为独立函数（注意函数接口的规定）。 （2）采用菜单驱动方式调用各种功能。 （3）用测试数据测试程序的正确性，如下面的二叉树： （4）对同一棵二叉树，分别调用两种算法，单步跟综递归程序的执行过程并观察调用堆栈。 （5）分析算法的时间复杂度。 提示： 二叉链表可以采用数据类型定义： typedef struct node { datatype data; //每个结点的数据域 struct node *lchild, *rchild; // 结点的左孩子指针域lchild，右孩子指针域rchild }BinNode; 五、实验报告 1、写出每个算法的思想和关键代码。 2、画出算法流程图。 3、调试程序出现的问题及解决的方法。 4、报告给出测试的结果并写出设计体会。 5、列表对比分析两种算法的时间复杂度、空间复杂度，阐明产生差异的原因。 6、根据实例归纳将递归算法改写为非递归算法的步骤。 一：流程图 先序遍历流程图： 中序遍历流程图： 后序遍历流程图： 递归代码： #includestdio.h #includestdlib.h #includemalloc.h typedef struct node { char data;struct node *lchild,*rchild; }BinNode; BinNode *createbn( ) { BinNode *q;struct node *m[30];int j,i,x; printf(建立二叉树，输入结点对应的编号和值\n); printf(i,x = ); scanf(%d,%c,i,x); while(i != 0 x != 0) {q=(BinNode*)malloc(sizeof(BinNode)); q-data = x; q-lchild = NULL; q-rchild = NULL; m[i] = q; if(i != 1) {j = i / 2;if(i % 2 == 0) m[j]-lchild = q; else m[j]-rchild = q; } printf(i,x = ); scanf(%d,%c,i,x); } return m[1]; } void BinNodePreorder(BinNode*bn) {if(bn!=NULL) { printf(%c ,bn-data); BinNodePreorder(bn-lchild); BinNodePreorder(bn-rchild); } } void BinNodeInorder(BinNode*bn) { if(bn!=NULL) { BinNodeInorder(bn-lchild); printf(%c ,bn