实验5——二叉树.docx

### 实验5——二叉树知识点详解 #### 一、实验背景及目标 本次实验的主要目的是让学生们深入了解二叉树这种数据结构，并掌握其基本操作方法。通过具体实践，不仅能够增强理论知识的理解，还能提高编程技能。 **实验目标：** 1. **掌握二叉树的实现方式：** - 学习如何定义二叉树节点结构。 - 掌握二叉树的构建过程。 2. **掌握二叉树遍历算法的实现：** - **递归遍历算法：** - 后序遍历。 - **非递归遍历算法：** - 先序遍历。 - **广度优先遍历算法：** #### 二、实验内容与要求解析 **实验内容：** - 使用给定的学生信息列表，构造一棵完全二叉树，其中每个节点存储学生姓名、学号和成绩信息。 - 对这棵二叉树进行三种遍历操作： - 后序遍历（递归）； - 先序遍历（非递归）； - 广度优先遍历。 **实验要求：** 1. **编写程序实现上述内容。** 2. **程序中包含相应的文档说明：** - 功能性注释：解释每段代码的功能和作用。 - 序言性注释：介绍程序的整体结构、功能和设计思路。 3. **撰写实验报告：** - 包括实验目的、实验步骤、实验结果等。 - 包含完整的程序代码以及程序运行结果。 4. **个人小结：** - 分析实验难点、关键点或知识点总结。 #### 三、二叉树概念回顾 **二叉树定义：** 二叉树是一种树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。根据节点是否为空可以分为以下几种情况： - 满二叉树：除了最后一层外，每一层的节点数都达到最大值；最后一层的节点都靠左排列。 - 完全二叉树：除了最后一层外，每一层的节点数都达到最大值；最后一层的节点可以从任意位置开始，但一旦开始，则必须连续排列至最右侧。 - 空二叉树：不包含任何节点的二叉树。 **二叉树遍历：** 遍历是访问二叉树中所有节点的过程。常见的遍历方式有： 1. **先序遍历：** - 访问根节点； - 遍历左子树； - 遍历右子树。 2. **中序遍历：** - 遍历左子树； - 访问根节点； - 遍历右子树。 3. **后序遍历：** - 遍历左子树； - 遍历右子树； - 访问根节点。 4. **层次遍历（广度优先遍历）：** - 从根节点开始，逐层遍历每一层的节点，从左到右。 #### 四、实验步骤 **步骤1：定义二叉树节点结构** ```c++ struct Node { string name; // 姓名 int number; // 学号 int score; // 成绩 Node* left; // 左子节点指针 Node* right; // 右子节点指针 Node(string n, int num, int s) : name(n), number(num), score(s), left(NULL), right(NULL) {} }; ``` **步骤2：构建完全二叉树** 使用队列来构建完全二叉树，按照学号顺序插入节点。 ```c++ Node* buildTree(vector<Student>& students) { Node* root = new Node(students[0].name, students[0].number, students[0].score); queue<Node*> q; q.push(root); for (int i = 1; i < students.size(); i++) { Node* parent = q.front(); q.pop(); Node* leftChild = new Node(students[i].name, students[i].number, students[i].score); parent->left = leftChild; q.push(leftChild); if (i + 1 < students.size()) { Node* rightChild = new Node(students[i + 1].name, students[i + 1].number, students[i + 1].score); parent->right = rightChild; q.push(rightChild); i++; } } return root; } ``` **步骤3：实现遍历算法** - **递归后序遍历：** ```c++ void postOrderTraversal(Node* node) { if (node == NULL) return; postOrderTraversal(node->left); postOrderTraversal(node->right); cout << node->name << " " << node->number << " " << node->score << endl; } ``` - **非递归先序遍历：** 使用栈辅助完成非递归先序遍历。 ```c++ void preOrderTraversalNonRecursive(Node* root) { if (root == NULL) return; stack<Node*> s; s.push(root); while (!s.empty()) { Node* node = s.top(); s.pop(); cout << node->name << " " << node->number << " " << node->score << endl; if (node->right) s.push(node->right); if (node->left) s.push(node->left); } } ``` - **广度优先遍历：** 利用队列实现广度优先遍历。 ```c++ void levelOrderTraversal(Node* root) { if (root == NULL) return; queue<Node*> q; q.push(root); while (!q.empty()) { Node* node = q.front(); q.pop(); cout << node->name << " " << node->number << " " << node->score << endl; if (node->left) q.push(node->left); if (node->right) q.push(node->right); } } ``` #### 五、实验总结 通过本次实验，我们深入学习了二叉树的基本概念、构建方法以及遍历算法。实验过程中，我们首先定义了二叉树节点结构，并使用给定的学生信息列表构建了一棵完全二叉树。随后，实现了三种不同的遍历算法：递归后序遍历、非递归先序遍历和广度优先遍历。这些操作不仅加深了我们对二叉树数据结构的理解，还锻炼了我们的编程能力。 此外，在实验报告中，我们也注重了文档说明的撰写，以确保程序具有良好的可读性和可维护性。通过这次实验，我们不仅掌握了二叉树的相关知识点，还提高了实际问题解决的能力。