二叉树(二)
二叉树遍历是一种重要的操作,它在许多应用场景中被广泛使用。以下是一些常见的应用场景: 查找和搜索:二叉树遍历可以用于查找特定元素或者进行搜索操作。通过遍历整棵树,可以找到目标元素并进行相应的处理。例如,在二叉搜索树中查找某个特定值,或者在字典树中搜索以某个前缀开头的单词。 排序和输出:二叉树的中序遍历可以按照升序输出树中的节点值,从而实现对树中元素的排序功能。这在需要对树中元素进行排序或者输出有序结果的情况下非常有用。 表达式求值:二叉树遍历可以用于对表达式进行求值。通过构建表达式树,并对其进行先序、中序或后序遍历,可以按照特定的顺序计算表达式的值。 图遍历:二叉树可以看作一种特殊的图结构,因此二叉树遍历也可以用于图的遍历。例如,通过深度优先搜索(DFS)或广度优先搜索(BFS)遍历二叉树,可以访问所有的节点,实现对图的遍历和搜索。 解析和编译:在计算机科学中,二叉树遍历常用于语法分析和编译过程中。通过构建语法树或抽象语法树,并进行遍历操作,可以对代码进行解析、优化和生成相应的目标代码。 路径查找和最优解决方案:通过遍历二叉树,可以寻找特定路径或者最优解决方案。例如,在二叉树中查找从根节点到叶子节点的路径,或者在二叉堆中找到具有最小或最大值的元素。 这些只是二叉树遍历的一些常见应用场景,实际上,二叉树遍历在各种数据结构和算法中都发挥着重要的作用,包括图算法、搜索算法、动态规划等。
先序遍历
先序遍历动态图
练习:
中序遍历
中序遍历动态图
选择练习
后序遍历
后序遍历动态图
练习
前中后序遍历代码实现
前序遍历
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
【算法分析】 前序遍历: 输出当前结点的值 递归去处理左子树 递归去处理右子树 【参考代码】 #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),从根节点开始进行深度优先搜索。 遍历完成后,程序结束。View Code
中序遍历
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#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)。 遍历完成后,程序结束。View Code
后序遍历
【算法分析】 后序遍历: 递归去处理左子树 递归去处理右子树 输出当前结点的值 #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
标签:遍历,U5,09,dfs,int,二叉树,元素,节点 From: https://www.cnblogs.com/jayxuan/p/17894324.html