二叉树（二）
二叉树遍历是一种重要的操作，它在许多应用场景中被广泛使用。以下是一些常见的应用场景：
查找和搜索：二叉树遍历可以用于查找特定元素或者进行搜索操作。通过遍历整棵树，可以找到目标元素并进行相应的处理。例如，在二叉搜索树中查找某个特定值，或者在字典树中搜索以某个前缀开头的单词。
排序和输出：二叉树的中序遍历可以按照升序输出树中的节点值，从而实现对树中元素的排序功能。这在需要对树中元素进行排序或者输出有序结果的情况下非常有用。
表达式求值：二叉树遍历可以用于对表达式进行求值。通过构建表达式树，并对其进行先序、中序或后序遍历，可以按照特定的顺序计算表达式的值。
图遍历：二叉树可以看作一种特殊的图结构，因此二叉树遍历也可以用于图的遍历。例如，通过深度优先搜索（DFS）或广度优先搜索（BFS）遍历二叉树，可以访问所有的节点，实现对图的遍历和搜索。
解析和编译：在计算机科学中，二叉树遍历常用于语法分析和编译过程中。通过构建语法树或抽象语法树，并进行遍历操作，可以对代码进行解析、优化和生成相应的目标代码。
路径查找和最优解决方案：通过遍历二叉树，可以寻找特定路径或者最优解决方案。例如，在二叉树中查找从根节点到叶子节点的路径，或者在二叉堆中找到具有最小或最大值的元素。
这些只是二叉树遍历的一些常见应用场景，实际上，二叉树遍历在各种数据结构和算法中都发挥着重要的作用，包括图算法、搜索算法、动态规划等。
先序遍历
先序遍历动态图
练习：
中序遍历
中序遍历动态图
选择练习
后序遍历
后序遍历动态图
练习
前中后序遍历代码实现
前序遍历
【算法分析】 前序遍历： 输出当前结点的值 递归去处理左子树 递归去处理右子树 【参考代码】 #include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 9; int a[maxn]; // 存放元素的数组 int n; // 元素数量 // 深度优先搜索函数 void dfs(int x) { cout << a[x] << " "; // 输出当前节点的值 if (2 * x <= n) dfs(2 * x); // 如果存在左子节点，则递归调用dfs函数 if (2 * x + 1 <= n) dfs(2 * x + 1); // 如果存在右子节点，则递归调用dfs函数 } int main() { cin >> n; // 输入元素数量 for (int i = 1; i <= n; i++) cin >> a[i]; // 输入每个元素的值 dfs(1); // 从根节点开始进行深度优先搜索 return 0; } 执行流程： 定义了常量maxn表示最大的数组大小。 声明了一个整型数组a，用于存放元素。数组大小为maxn。 声明了一个整型变量n，用于记录输入的元素数量。 定义了一个深度优先搜索函数dfs，用于遍历二叉树。该函数接受一个整数参数x，表示当前节点的索引。 在dfs函数中，首先输出当前节点的值a[x]。 然后判断当前节点是否有左子节点（即2*x <= n），如果有，则递归调用dfs函数，传入左子节点的索引（即2*x）。 接着判断当前节点是否有右子节点（即2*x + 1 <= n），如果有，则递归调用dfs函数，传入右子节点的索引（即2*x + 1）。 在main函数中，首先输入元素数量n。 使用循环从1到n依次输入每个元素的值，存放在数组a中。 调用dfs(1)，从根节点开始进行深度优先搜索。 遍历完成后，程序结束。
中序遍历
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 9; int a[maxn]; // 存放元素的数组 int n; // 元素数量 // 深度优先搜索函数 void dfs(int x) { if (2 * x <= n) dfs(2 * x); // 如果存在左子节点，则递归调用dfs函数 cout << a[x] << " "; // 输出当前节点的值 if (2 * x + 1 <= n) dfs(2 * x + 1); // 如果存在右子节点，则递归调用dfs函数 } int main() { cin >> n; // 输入元素数量 for (int i = 1; i <= n; i++) cin >> a[i]; // 输入每个元素的值 dfs(1); // 从根节点开始进行深度优先搜索 return 0; } 执行流程： 定义了常量 maxn 表示最大的数组大小。 声明了一个整型数组 a，用于存放元素。数组大小为 maxn。 声明了一个整型变量 n，用于记录输入的元素数量。 定义了一个深度优先搜索函数 dfs，用于遍历二叉树。该函数接受一个整数参数 x，表示当前节点的索引。 在 dfs 函数中，首先判断当前节点是否有左子节点（即 2*x <= n），如果有，则递归调用 dfs 函数，传入左子节点的索引（即 2*x）。 接着输出当前节点的值 a[x]。 然后再判断当前节点是否有右子节点（即 2*x + 1 <= n），如果有，则递归调用 dfs 函数，传入右子节点的索引（即 2*x + 1）。 在 main 函数中，首先输入元素数量 n。 使用循环从 1 到 n 依次输入每个元素的值，存放在数组 a 中。 调用 dfs(1)，从根节点开始进行深度优先搜索。 当执行到 dfs(x) 时，会先递归访问左子节点 dfs(2*x)，然后输出当前节点 a[x] 的值，最后递归访问右子节点 dfs(2*x+1)。 遍历完成后，程序结束。
后序遍历
【算法分析】 后序遍历： 递归去处理左子树 递归去处理右子树 输出当前结点的值 #include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 9; int a[maxn]; // 存放元素的数组 int n; // 元素数量 // 深度优先搜索函数 void dfs(int x) { if (2 * x <= n) dfs(2 * x); // 如果存在左子节点，则递归调用dfs函数 if (2 * x + 1 <= n) dfs(2 * x + 1); // 如果存在右子节点，则递归调用dfs函数 cout << a[x] << " "; // 输出当前节点的值 } int main() { cin >> n; // 输入元素数量 for (int i = 1; i <= n; i++) cin >> a[i]; // 输入每个元素的值 dfs(1); // 从根节点开始进行深度优先搜索 return 0; } 执行流程： 定义了常量 maxn 表示最大的数组大小。 声明了一个整型数组 a，用于存放元素。数组大小为 maxn。 声明了一个整型变量 n，用于记录输入的元素数量。 定义了一个深度优先搜索函数 dfs，用于遍历二叉树。该函数接受一个整数参数 x，表示当前节点的索引。 在 dfs 函数中，首先判断当前节点是否有左子节点（即 2*x <= n），如果有，则递归调用 dfs 函数，传入左子节点的索引（即 2*x）。 接着判断当前节点是否有右子节点（即 2*x + 1 <= n），如果有，则递归调用 dfs 函数，传入右子节点的索引（即 2*x + 1）。 最后输出当前节点的值 a[x]。 在 main 函数中，首先输入元素数量 n。 使用循环从 1 到 n 依次输入每个元素的值，存放在数组 a 中。 调用 dfs(1)，从根节点开始进行深度优先搜索。 当执行到 dfs(x) 时，会先递归访问左子节点 dfs(2*x)，然后递归访问右子节点 dfs(2*x+1)，最后输出当前节点 a[x] 的值。 遍历完成后，程序结束。
层次遍历
本节课作业讲解分析：
链接：https://pan.baidu.com/s/1gRFdJLPZAgvIPpD7P74D2A?pwd=zll9
提取码：zll9