HFUT数据结构实验三预习报告20072851李亚东.docVIP

计算机与信息学院 数据结构 实验预习报告 专 业 班 级 学生姓名及学号 课程教学班号 任 课 教 师 胡学钢 实验指导教师 张晶 实验地点 学年第 学期 实验序号及名称：实验 三 二叉树实验 一、实验目的和要求∶ (1)掌握二叉树的动态链表存储结构及表示。 (2)掌握二叉树的三种遍历算法（递归和非递归两类）。 (3)运用二叉树三种遍历的方法求解有关问题。 二、实验环境和仪器设备∶ Windows xp Dev C++ 三、相关资料和参考文献(教材和实验指导书以外)∶ （无） 四、实验任务∶ 1求二叉树的高度。 2设计算法按中序次序输出二叉树中各结点的值及其所对应的层次数。 3将按顺序方式存储在数组中的二叉树转换为二叉链表形式。 4复制一棵二叉树T到T1。 5交换二叉树中每个结点的左右孩子指针的值。 6设计算法以实现下面所提到以扩展二叉树的先序序列作为输入构建二叉树的功能。 五、实验内容（步骤）∶ 1设计循环链表、双链表、链表的数据结构，并根据数据结构设计算法实现。 2编写源代码 3上机调试 4总结  六、实验预习过程记录（以文字、图表方式记录设计思想、设计步骤、设计初步方案、程序框架、流程图、预定相关测试数据、预期结果等）∶ 1求二叉树的高度。 依次遍历每一个叶子结点，找到它们中的最大层次数。 第一组数据： full41.cbt 结果：4 第二组数据： cbitre.cbt 结果：6 2设计算法按中序次序输出二叉树中各结点的值及其所对应的层次数。 使用递归函数调用，输出中序次序。 第一组数据： full41.cbt 结果：DCEBGFHAKJLINMO 第二组数据： cbitre.cbt 结果：EDFCGBIHJAMLNKPQOSRUT 3将按顺序方式存储在数组中的二叉树转换为二叉链表形式。 二叉树的构造问题。第n个结点的左右孩子分别为第2n+1和2n+2。 第一组数据： full41.cbt 第二组数据： cbitre.cbt 4复制一棵二叉树T到T1。 二叉树的构造问题。遍历二叉树，然后访问每一个结点以创建新的二叉树。 5交换二叉树中每个结点的左右孩子指针的值。 遍历二叉树，对于每一个遍历到的结点交换其左右孩子指针。 第一组数据： full41.cbt 第二组数据： cbitre.cbt 6设计算法以实现下面所提到以扩展二叉树的先序序列作为输入构建二叉树的功能。 二叉树的构造问题。 第一组数据： full41.cbt 第二组数据： cbitre.cbt 试验数据： 扩展二叉树ABCD..E..FG..H..IJK..L..MN..O.. 顺序存储方式ABICFJMDEGHKLNO................ 扩展二叉树abcde..f..g..hi..j..klm..n..op.q..rs..tu... 顺序表存储方式 abqcnrvdkop.swy.elm......tu.x.z..fh.....................................gij............................................. ...........................................................................................................................