第一题 二叉搜索树的遍历
1.实验题目
2. 实验目的
本实验的主要目的是实现对一组无序整数按顺序插入生成二叉搜索树，并实现其中序遍历和先序遍历的操作。通过本实验，学生能够：
- 理解并实现二叉搜索树的基本操作：插入、遍历。
- 掌握树结构在排序和搜索中的应用。
- 提高递归算法的设计和调试能力。
3. 算法设计
为实现该题目要求的二叉搜索树的构建与遍历，具体的算法步骤如下：
- 二叉搜索树构建：
- 输入数据包含多个整数序列，每个序列中的第一个数字作为树的根节点，随后按顺序插入其余数字到树中。
- 插入操作需要遵循二叉搜索树的性质：左子树节点小于根节点，右子树节点大于根节点。
- 中序遍历：
- 中序遍历（左-根-右）是二叉搜索树的一种遍历方式，遍历时节点的值会按升序输出。
- 先序遍历：
- 先序遍历（根-左-右）是另一种遍历方式，遍历时节点的值会按照根节点优先的顺序输出。
- 算法步骤：
- 插入函数：遍历输入数据，按顺序插入每个数字到二叉搜索树中。
- 遍历函数：分别实现中序遍历和先序遍历，递归地输出每个节点的值。
- 时间复杂度：
- 构建二叉搜索树的时间复杂度为 O(m)，其中 m 是输入的数字个数。
- 中序遍历和先序遍历的时间复杂度均为 O(m)，因为每个节点都被访问一次。
- 代码实现：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* insert(TreeNode* root, int x) {
if (root == NULL) {
root = new TreeNode(x);
} else if (x < root->val) {
root->left = insert(root->left, x);
} else {
root->right = insert(root->right, x);
}
return root;
}
void inorder(TreeNode* root) {
if (root == nullptr) {
return;
}
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
void preorder(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
int main() {
int m;
while (cin >> m) {
if (m == 0) break; // 输入结束条件
vector<int> v(m);
for (int i = 0; i < m; i++) {
cin >> v[i];
}
TreeNode* root = NULL;
for (int i = 0; i < m; i++) {
root = insert(root, v[i]);
}
// 中序遍历
inorder(root);
cout << endl;
// 先序遍历
preorder(root);
cout << endl;
}
return 0;
}4. 程序运行与测试
测试用例
为验证程序的正确性，准备了一些测试用例，包括不同规模的输入：
- 输入样例：
- 第一组数据：
9 10 4 16 9 8 15 21 3 12- 第二组数据：
6 20 19 16 15 45 48 - 输出：
- 第一组数据：
3 4 8 9 10 12 15 16 21 10 4 3 9 8 16 15 12 21- 第二组数据：
15 16 19 20 45 48 20 19 16 15 45 48
程序运行
- 程序使用标准输入和输出，能够处理多个测试样例。
- 程序首先构建二叉搜索树，然后进行中序遍历和先序遍历，输出相应的结果。
- 在测试过程中，程序能够正确构建树，并按照要求输出中序和先序遍历结果。
5. 实验总结与心得
通过本次实验，我深入理解了二叉搜索树的基本操作，包括插入、遍历等。实验的关键是理解二叉搜索树的特性，以及如何通过递归实现树的遍历。在实现过程中，我掌握了如何通过递归解决树形结构问题。
在测试中，我发现二叉搜索树的中序遍历能够得到升序排列的结果，而先序遍历则提供了以根节点优先的遍历顺序。通过这次实验，我也提高了对递归算法的理解，并且在实际编程中体会到了递归的强大。
此外，实验中的输入输出格式要求和树的插入顺序让我更加注重细节。在处理多个测试用例时，注意输入的结束标志是非常重要的，否则可能会导致程序死循环或崩溃。
通过本次实验，我对二叉搜索树的构建与遍历有了更深刻的理解，尤其是递归的应用。
第二题 Play with Tree
1.实验题目
2. 实验目的
本实验的主要目的是实现一个函数，用于计算二叉树的大小（节点数）和高度。通过本实验，学生能够：
- 理解二叉树的基本概念和结构。
- 学会递归地遍历二叉树来计算其节点数和树的高度。
- 掌握如何通过递归方法解决树形数据结构中的问题。
3. 算法设计
要实现计算二叉树的大小和高度的功能，我们可以通过递归遍历二叉树来实现。具体步骤如下：
- 树的高度：
- 树的高度定义为从根节点到最远叶子节点的最长路径的节点数。
- 如果树为空，则高度为 0。
- 否则，高度为左子树和右子树高度的较大值加 1。
- 树的大小：
- 树的大小定义为树中节点的数量。
- 如果树为空，则大小为 0。
- 否则，树的大小为左子树和右子树大小的和加上 1（根节点）。
- 递归实现：
- 对于每一个节点，递归地计算其左子树和右子树的大小与高度。
- 然后，合并左右子树的结果，计算当前树的大小和高度。
4. 代码实现
struct Node {
Node *lc, *rc;
char data;
};
void query(const Node *root, int &size, int &height) {
// 如果树为空
if (root == NULL) {
size = 0;
height = 0;
return;
}
// 递归计算左子树的大小和高度
int lsize = 0, lheight = 0;
query(root->lc, lsize, lheight);
// 递归计算右子树的大小和高度
int rsize = 0, rheight = 0;
query(root->rc, rsize, rheight);
// 当前树的大小为左右子树大小之和加上根节点
size = lsize + rsize + 1;
// 当前树的高度为左右子树高度的最大值加 1
height = max(lheight, rheight) + 1;
}5. 程序运行与测试
测试用例
为验证程序的正确性，准备了一些测试用例，包含不同形态的二叉树：
- 输入样例：
树的结构如下：
A / \ B C / \ D E对应的节点指针和数据：
Node A: lc = B, rc = C Node B: lc = D, rc = E Node C: lc = NULL, rc = NULL Node D: lc = NULL, rc = NULL Node E: lc = NULL, rc = NULL - 输出：
- 树的大小（节点数）为 5。
- 树的高度为 3。
程序运行
- 程序使用标准输入和输出，能够正确计算二叉树的大小和高度。
- 对于不同形态的树结构，程序能够递归地计算其大小和高度。
- 在测试过程中，程序能够正确处理空树和单节点树的情况。
6. 实验总结与心得
通过本次实验，我深入理解了如何通过递归方法计算二叉树的大小和高度。实验的核心是递归地遍历树结构，并结合左右子树的结果来计算当前节点的属性。
在实现过程中，我体会到了递归在树形结构问题中的优势。通过递归函数，可以在树的每个节点上进行必要的计算，并将结果传递给父节点，从而实现对整个树的遍历和求解。
此外，本次实验还让我更加熟悉了树的基本操作，尤其是在处理二叉树的问题时，递归是一种简洁且有效的解决方案。
第三题 postorder
1. 实验题目
2. 实验目的
本实验的主要目的是实现通过给定的前序遍历和中序遍历序列，构建二叉树并输出其后序遍历序列。通过本实验，学生能够：
- 理解前序遍历和中序遍历的关系，以及如何利用这两种遍历序列来唯一确定一棵二叉树。
- 掌握树的构建过程以及后序遍历的递归实现。
- 提高算法设计与实现能力，尤其是在树结构相关问题中的应用。
3. 算法设计
为实现根据前序和中序遍历序列构建二叉树并输出后序遍历序列，首先需要理解如何通过前序和中序遍历序列来构建二叉树。构建树的过程包括以下几个关键步骤：
- 构建二叉树的基本思路：
- 前序遍历的第一个节点即为树的根节点。
- 在中序遍历序列中，根节点将树分为左右子树。根节点左边的部分为左子树的中序遍历序列，右边的部分为右子树的中序遍历序列。
- 使用递归方式，逐步构建左右子树，并继续拆分前序和中序遍历序列。
- 后序遍历：
- 后序遍历的顺序为：左子树 -> 右子树 -> 根节点。因此，在构建完成二叉树后，可以通过递归方式进行后序遍历并输出结果。
- 时间复杂度分析：
- 构建树的过程中，每个节点会被访问一次，因此时间复杂度为 O(n)，其中 n 是节点的数量。
- 后序遍历的时间复杂度也是 O(n)，因为每个节点都会被访问一次。
- 代码实现：
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 构建二叉树
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty()) return NULL;
int rootVal = preorder[0];
TreeNode* root = new TreeNode(rootVal);
// 找到根节点在中序遍历中的位置
int pos = 0;
while (inorder[pos] != rootVal) {
pos++;
}
// 左子树的中序遍历是inorder[0...pos-1]，右子树的中序遍历是inorder[pos+1...n-1]
vector<int> leftInorder(inorder.begin(), inorder.begin() + pos);
vector<int> rightInorder(inorder.begin() + pos + 1, inorder.end());
// 左子树的前序遍历是preorder[1...pos]，右子树的前序遍历是preorder[pos+1...n-1]
vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + pos);
vector<int> rightPreorder(preorder.begin() + 1 + pos, preorder.end());
root->left = buildTree(leftPreorder, leftInorder);
root->right = buildTree(rightPreorder, rightInorder);
return root;
}
// 后序遍历并输出
void postOrder(TreeNode* root) {
if (root == NULL) return;
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
int main() {
int n;
cin >> n;
vector<int> preorder(n), inorder(n);
for (int i = 0; i < n; i++) {
cin >> preorder[i];
}
for (int i = 0; i < n; i++) {
cin >> inorder[i];
}
TreeNode* root = buildTree(preorder, inorder);
postOrder(root);
return 0;
}4. 程序运行与测试
测试用例
为了验证程序的正确性，准备了以下测试用例：
- 输入样例：
- n = 10
- 前序遍历：7 2 0 5 8 4 9 6 3 1
- 中序遍历：7 5 8 0 4 2 6 3 9 1
- 输出：
- 后序遍历结果：8 5 4 0 3 6 1 9 2 7
程序运行
- 程序通过标准输入输出。
- 在给定的前序和中序遍历序列下，成功构建了树并输出了正确的后序遍历序列。
- 对于不同规模的树，程序均能够在合理时间内完成树的构建和遍历。
5. 实验总结与心得
通过本次实验，我学会了如何利用前序和中序遍历序列构建一棵二叉树，并通过递归实现了后序遍历。实现过程中，我对树的构建和递归遍历的机制有了更加深入的理解。
本次实验的挑战主要是如何通过递归的方式高效地构建树，并保证树的正确性。通过合理分割前序和中序遍历序列，我能够成功地构建左右子树并继续递归处理。
在时间复杂度方面，由于每个节点被访问一次，因此程序的时间复杂度是 O(n)，可以有效处理最大节点数为 100000 的情况。
总体来说，这次实验让我更加熟悉了二叉树的构建和遍历技巧，并加深了对树形结构操作的理解。