数据结构实验6.doc

"数据结构实验6" 在这个实验报告中，我们将探索树和二叉树的操作，包括树的结构特征、二叉树的存储结构、指针变量和动态内存分配的使用、二叉树的遍历方法等。 一、实验目的及要求 1. 进一步掌握指针变量、动态变量的含义。 2. 掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。 3. 掌握用指针类型描述、访问和处理二叉树的运算。 4. 掌握用二叉树前序、中序、后序、层次遍历的方法。 二、实验设备（环境）及要求 * 微型计算机 * Windows 操作系统 * Microsoft Visual Studio 6.0 集成开发环境 三、实验内容与步骤 1. 根据下图中的树回答问题 * 列出所有的叶子结点 * 列出 G 结点的双亲 * 列出 E 结点的孩子 * 列出 I 结点所有的堂兄弟 * 列出 B 结点所有的子孙 * 结点 E 的度是多少 * 树的度是多少 * 结点 E 的层次是多少 * 树的深度是多少 2. 根据 P129 的方法，将 a*b-((c+d*e/f)+g) 转化为表达式二叉树，并写出表达式二叉树的前序、中序和后序遍历顺序。 3. 画出和下列二叉树相应的森林 4. 链式表表示和实现二叉排序树 四、编程实现 1. 编写函数实现前序、中序和后序遍历 2. 编写函数实现计算叶节点个数 3. 编写函数实现层序遍历 4. 编写函数实现查询二叉树中的某个结点 5. 编写函数实现求二叉树的深度 6. 编写函数实现中序非递归遍历（利用栈） 五、选做题 1. 如果通讯字符 a，b，c，d 出现频度分别为 7，5，2，4，某同学设计了如下程序，请根据程序画出对应的二叉树，计算所画出的二叉树的带权路径长度 这个实验报告涵盖了树和二叉树的基本概念和操作，包括树的结构特征、二叉树的存储结构、指针变量和动态内存分配的使用、二叉树的遍历方法等。通过这个实验，我们可以更好地理解树和二叉树的基本概念，并掌握使用指针变量和动态内存分配来实现二叉树的操作的方法。