二叉树的构建及遍历
一、课上练习
编程练习
- 二叉树构建与遍历：L3231
二、知识总结
✨ 二叉树的构建
使用链表构建二叉树是一种常见的数据结构实现方式，特别是在使用编程语言如 C 或 C++ 这样不自带特定树结构的环境中。在这种情况下，每个节点由一个结构（或对象）表示，该结构包含节点的值及指向其左子节点和右子节点的指针。
定义节点结构
首先，你需要定义一个树节点的数据结构。通常，这个结构会包括至少三个元素：节点存储的数据，指向左子节点的指针，以及指向右子节点的指针。在 C++ 中，你可以这样定义：
1struct TreeNode {
2 int value; // 节点存储的数据
3 TreeNode *left; // 指向左子节点的指针
4 TreeNode *right; // 指向右子节点的指针
5 TreeNode(int x) : value(x), left(nullptr), right(nullptr) {} // 构造函数
6};构建方式
二叉树可以通过多种方式构建，如通过用户输入、从数组构建、从文件读取等。以下是一些基本方法：
方式一：手动构建
你可以手动创建每个节点并连接它们，尤其是在测试或教学示例中：
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);这段代码创建了一个具有五个节点的二叉树。
方式二：从数组构建
对于特定的二叉树类型，如完全二叉树，可以从数组直接构建。每个节点 i 的左子节点位于 2i + 1，右子节点位于 2i + 2，其中 i 是数组中的索引：
1TreeNode* buildTree(vector<int>& nums, int i) {
2 if (i >= nums.size()) return nullptr;
3 TreeNode* node = new TreeNode(nums[i]);
4 node->left = buildTree(nums, 2*i + 1);
5 node->right = buildTree(nums, 2*i + 2);
6 return node;
7}
8vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
9TreeNode* root = buildTree(nums, 0);这个函数递归地创建树节点，有效地将数组转换为二叉树结构。
方式三：使用插入操作构建二叉搜索树（BST）
对于二叉搜索树，可以通过插入操作构建树：
1TreeNode* insertIntoBST(TreeNode* root, int val) {
2 if (root == nullptr) return new TreeNode(val);
3 if (val < root->value)
4 root->left = insertIntoBST(root->left, val);
5 else
6 root->right = insertIntoBST(root->right, val);
7 return root;
8}
9TreeNode* root = nullptr;
10vector<int> values = {5, 3, 8, 1, 4, 7, 9};
11for (int val : values) {
12 root = insertIntoBST(root, val);
13}这段代码逐个插入元素，构建了一个二叉搜索树。
注意事项
构建和操作二叉树时需要注意内存管理，确保所有创建的节点最终都被适当地释放，特别是在使用 C++ 等需要手动管理内存的语言中。在实际应用中，你可能还需要考虑异常安全和错误处理，确保程序的健壮性和稳定性。
✨ 二叉树的遍历
二叉树的遍历是指按照某种访问顺序逐个访问树中的每个节点的过程。对于二叉树，主要有三种深度优先遍历方法：先序遍历、中序遍历和后序遍历。这些遍历方法的差异在于访问根节点的时序相对于其左右子节点的不同。
先序遍历（Pre-order Traversal）
在先序遍历中，我们首先访问根节点，然后递归地对左子树进行先序遍历，接着对右子树进行先序遍历。这种遍历方法在复制树结构或打印一个结构化的文档时非常有用。
遍历顺序：根 -> 左 -> 右
1struct TreeNode {
2 int value;
3 TreeNode *left;
4 TreeNode *right;
5 TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
6};
7
8void preorderTraversal(TreeNode* root) {
9 if (root == nullptr) return;
10 cout << root->value << " "; // 访问根节点
11 preorderTraversal(root->left); // 访问左子树
12 preorderTraversal(root->right); // 访问右子树
13}中序遍历（In-order Traversal）
中序遍历首先递归地访问左子树，然后访问根节点，最后递归地访问右子树。这种方法特别适用于二叉搜索树（BST），因为它可以按升序访问所有节点，从而获取有序的数据。
遍历顺序：左 -> 根 -> 右
1void inorderTraversal(TreeNode* root) {
2 if (root == nullptr) return;
3 inorderTraversal(root->left); // 访问左子树
4 cout << root->value << " "; // 访问根节点
5 inorderTraversal(root->right); // 访问右子树
6}后序遍历（Post-order Traversal）
后序遍历首先递归地访问左子树，然后是右子树，最后是根节点。这种遍历方法用于先处理子节点再处理父节点的场景，例如在计算机图形学中计算给定图形的面积或在删除树时释放资源。
遍历顺序：左 -> 右 -> 根
1void postorderTraversal(TreeNode* root) {
2 if (root == nullptr) return;
3 postorderTraversal(root->left); // 访问左子树
4 postorderTraversal(root->right); // 访问右子树
5 cout << root->value << " "; // 访问根节点
6}非递归实现
尽管递归是实现树遍历的直接和清晰的方法，但在深度很大的树上可能会导致栈溢出。因此，也可以使用栈来实现非递归的树遍历，特别是在限制递归深度的环境中。
应用场景
不同遍历方式有不同的应用：
- 先序遍历：用于打印树的结构，复制树。
- 中序遍历：在二叉搜索树中获取有序序列，进行排序操作。
- 后序遍历：在删除或释放给定树的资源时非常有用，首先处理子节点。
这些遍历技术是理解和操作树结构的基础，广泛应用于算法设计和数据结构优化中。
✨ 执行示例
下面用一棵具体的二叉树，展示三种遍历方式的完整递归执行过程。
示例树：
1
/ \
2 3
/ \ \
4 5 6先序遍历执行过程（根 -> 左 -> 右）
| 步骤 | 当前函数调用 | 操作 | 输出序列 |
|---|---|---|---|
| 1 | preOrder(1) | 访问根节点 1 | 1 |
| 2 | preOrder(2) | 访问根节点 2 | 1, 2 |
| 3 | preOrder(4) | 访问根节点 4 | 1, 2, 4 |
| 4 | preOrder(NULL) | 4 的左子树为空，返回 | 1, 2, 4 |
| 5 | preOrder(NULL) | 4 的右子树为空，返回 | 1, 2, 4 |
| 6 | preOrder(5) | 访问根节点 5 | 1, 2, 4, 5 |
| 7 | preOrder(NULL) | 5 的左子树为空，返回 | 1, 2, 4, 5 |
| 8 | preOrder(NULL) | 5 的右子树为空，返回 | 1, 2, 4, 5 |
| 9 | preOrder(3) | 访问根节点 3 | 1, 2, 4, 5, 3 |
| 10 | preOrder(NULL) | 3 的左子树为空，返回 | 1, 2, 4, 5, 3 |
| 11 | preOrder(6) | 访问根节点 6 | 1, 2, 4, 5, 3, 6 |
先序遍历结果：1 2 4 5 3 6
中序遍历执行过程（左 -> 根 -> 右）
递归会一直向左深入，直到遇到空节点才开始"回收"访问：
- 进入 1 -> 进入 2 -> 进入 4 -> 进入 NULL（返回）
- 访问 4 -> 进入 NULL（返回）-> 回到 2
- 访问 2 -> 进入 5 -> 进入 NULL（返回）-> 访问 5 -> 进入 NULL（返回）-> 回到 1
- 访问 1 -> 进入 3 -> 进入 NULL（返回）-> 访问 3 -> 进入 6 -> ...-> 访问 6
中序遍历结果：4 2 5 1 3 6
后序遍历执行过程（左 -> 右 -> 根）
后序遍历总是最后才访问根节点：
- 先处理完左子树（4, 5, 2 的左右子树）
- 再处理完右子树（6, 3 的左右子树）
- 最后访问根节点
后序遍历结果：4 5 2 6 3 1
✨ 解题步骤详解
以"二叉树构建与遍历"为例，介绍如何根据规则构建二叉树并遍历：
问题： 给定参数 n, a, b，从根节点 1 开始，每个值为 x 的节点的左子节点值为 x2+a，右子节点值为 x2+b，当节点值大于 n 时停止。输出三种遍历结果。
解题步骤：
- 递归构建：从根节点值 1 开始，递归创建左子节点（值 = x2+a）和右子节点（值 = x2+b）。
- 终止条件：当 x > n 时，仍创建该节点但不再继续往下创建子节点。
- 三种遍历：分别用先序、中序、后序遍历函数遍历建好的树，将结果存入 vector 输出。
关键点： 理解递归的两个要素——递归体（如何将问题分解为子问题）和递归出口（何时停止递归）。
✨ 常见错误
- 递归出口忘记判断空指针：遍历函数的第一行必须检查
if (root == nullptr) return;，否则访问空指针会导致程序崩溃。 - 混淆三种遍历的访问顺序：先序是"根左右"，中序是"左根右"，后序是"左右根"。只有"访问根节点"的时机不同，递归结构完全相同。
- 构建树时内存泄漏：使用 new 创建的节点，如果不再需要应当递归 delete。在竞赛中可以忽略，但在工程中很重要。
- 从数组构建时索引计算错误：注意索引从 0 开始和从 1 开始时，左右子节点的计算公式不同。
✨ 代码实现
下面的代码展示了二叉树的构建及三种遍历方式的完整实现：
1#include<iostream>
2#include<vector>
3using namespace std;
4
5// 定义树的节点结构
6struct Node {
7 int value; // 节点的值
8 Node *leftChild; // 左子节点
9 Node *rightChild; // 右子节点
10};
11
12// 递归创建树
13Node *createTree(int x, int n, int a, int b) {
14 Node *node = new Node; // 创建新节点
15 node->value = x; // 设置节点的值
16 node->leftChild = NULL; // 初始化左子节点为空
17 node->rightChild = NULL; // 初始化右子节点为空
18 if (x > n) { // 终止条件，当x大于n时停止创建
19 return node;
20 }
21 // 递归创建左子节点
22 node->leftChild = createTree(x * 2 + a, n, a, b);
23 // 递归创建右子节点
24 node->rightChild = createTree(x * 2 + b, n, a, b);
25 return node; // 返回树的根节点
26}
27
28// 前序遍历
29void preOrder(Node *node, vector<int> &result) {
30 if (!node) { // 如果节点为空，返回
31 return;
32 }
33 result.push_back(node->value); // 访问节点
34 preOrder(node->leftChild, result); // 遍历左子树
35 preOrder(node->rightChild, result); // 遍历右子树
36}
37
38// 中序遍历
39void inOrder(Node *node, vector<int> &result) {
40 if (!node) { // 如果节点为空，返回
41 return;
42 }
43 inOrder(node->leftChild, result); // 遍历左子树
44 result.push_back(node->value); // 访问节点
45 inOrder(node->rightChild, result); // 遍历右子树
46}
47
48// 后序遍历
49void postOrder(Node *node, vector<int> &result) {
50 if (!node) { // 如果节点为空，返回
51 return;
52 }
53 postOrder(node->leftChild, result); // 遍历左子树
54 postOrder(node->rightChild, result); // 遍历右子树
55 result.push_back(node->value); // 访问节点
56}
57
58// 打印遍历结果
59void print(const vector<int> &result) {
60 for (int i = 0; i < result.size(); i++) {
61 cout << result[i] << (i + 1 == result.size() ? '\n' : ' ');
62 }
63}
64
65int main() {
66 int n = 0, a = 0, b = 0;
67 cin >> n >> a >> b; // 读取参数
68 // 创建树
69 Node *root = createTree(1, n, a, b);
70 // 执行前序遍历
71 vector<int> preOrderResult;
72 preOrder(root, preOrderResult);
73 print(preOrderResult);
74 // 执行中序遍历
75 vector<int> inOrderResult;
76 inOrder(root, inOrderResult);
77 print(inOrderResult);
78 // 执行后序遍历
79 vector<int> postOrderResult;
80 postOrder(root, postOrderResult);
81 print(postOrderResult);
82
83 return 0;
84}三、课后练习
编程练习
- 找树根和孩子：L3232