C++U5-09-二叉树2

二叉树（二）

二叉树遍历是一种重要的操作，它在许多应用场景中被广泛使用。以下是一些常见的应用场景：

查找和搜索：二叉树遍历可以用于查找特定元素或者进行搜索操作。通过遍历整棵树，可以找到目标元素并进行相应的处理。例如，在二叉搜索树中查找某个特定值，或者在字典树中搜索以某个前缀开头的单词。

排序和输出：二叉树的中序遍历可以按照升序输出树中的节点值，从而实现对树中元素的排序功能。这在需要对树中元素进行排序或者输出有序结果的情况下非常有用。

表达式求值：二叉树遍历可以用于对表达式进行求值。通过构建表达式树，并对其进行先序、中序或后序遍历，可以按照特定的顺序计算表达式的值。

图遍历：二叉树可以看作一种特殊的图结构，因此二叉树遍历也可以用于图的遍历。例如，通过深度优先搜索（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