实验3 二叉树的存储和遍历.doc

### 实验3 二叉树的存储和遍历 #### 实验目的 通过本次实验，学生将能够： 1. **进一步理解指针变量的概念及其在数据结构中的应用**。 2. **深入掌握二叉树的基本结构特点，以及不同存储结构（如顺序存储与链式存储）的优缺点和适用场景**。 3. **熟练使用指针来描述、访问和处理二叉树的各种操作，包括但不限于创建、遍历和查询等**。 #### 实验要求 为了顺利完成本次实验，需要完成以下任务： 1. **认真阅读并理解实验提供的程序代码**。 2. **上机调试并运行程序，确保对程序逻辑有清晰的认识**。 3. **保存并打印出程序的运行结果，结合实际输出进行深入分析**。 4. **根据个人需求修改主程序，增加或调整二叉树的操作功能，并再次运行程序以验证修改后的效果**。 #### 实验内容详解 本次实验的主要内容是利用二叉树实现一个快速搜索磁盘文件记录系统。实验具体分为三个主要部分： 1. **构建二叉树**：用户需要按照先序方式输入二叉树的节点值。对于没有子节点的情况，可以输入数字“0”表示结束。 2. **先序遍历二叉树**：程序将展示二叉树的先序遍历结果，即按照根节点→左子树→右子树的顺序访问所有节点。 3. **根据学号查找内存地址**：用户可以输入特定的学号，程序会返回该学号对应的记录所在的内存地址。如果找不到相应的学号，则会提示不存在。 下面详细介绍各个部分的具体实现细节和技术要点。 ##### 创建二叉树 创建二叉树时，需要定义二叉树的节点结构。在这个实验中，二叉树的每个节点包含两部分信息： - `stuId`：表示学生的学号。 - `memoryAdd`：表示该学生记录在内存中的地址。 节点结构定义如下： ```c typedef struct{ long stuId; // 学号 long memoryAdd; // 内存地址 } Record,*RecordType; typedef struct BiTnode{ RecordType data; struct BiTnode* lchild,*rchild; } BiTnode,*BiTree; ``` 创建二叉树的过程可以通过递归实现，用户输入节点值来构建整棵树。具体的创建过程需要根据输入的节点值，逐步构建出完整的二叉树结构。 ##### 先序遍历 先序遍历是一种常见的遍历二叉树的方式，其步骤为： 1. 访问根节点。 2. 遍历左子树。 3. 遍历右子树。 先序遍历的代码实现通常采用递归的方法： ```c void PreOrderTraverse(BiTree t){ if (t != NULL) { // 访问当前节点 printf("学号：%ld 内存地址：%ld\n", t->data.stuId, t->data.memoryAdd); // 遍历左子树 PreOrderTraverse(t->lchild); // 遍历右子树 PreOrderTraverse(t->rchild); } } ``` ##### 根据学号查找节点 查找特定学号的节点可以通过递归地比较当前节点的学号与目标学号来实现。具体实现如下： ```c BiTnode* FindNode(BiTree t, long stuId) { if (t == NULL) return NULL; // 未找到 if (t->data.stuId == stuId) return t; // 找到目标节点 // 递归查找左子树 BiTnode* leftResult = FindNode(t->lchild, stuId); if (leftResult != NULL) return leftResult; // 递归查找右子树 return FindNode(t->rchild, stuId); } ``` 通过以上实验内容的学习与实践，学生不仅能够深入理解二叉树的存储结构与遍历方法，还能掌握如何利用二叉树解决实际问题的能力，这对于进一步学习更复杂的数据结构与算法具有重要的意义。