二叉树的三种遍历例题
二叉树是一种非常基础的数据结构，也是算法的重要基础。二叉树的三种遍历方式是前序遍历、中序遍历和后序遍历。这三种遍历方式可以用于二叉树的遍历、寻找二叉树中最大值或最小值、寻找二叉树中某一个节点、实现表达式的计算等。在本文中，我们将从不同的角度，分析这三种遍历方式。
一、三种遍历方式的定义和实现方式
1. 前序遍历：遍历顺序为
2. 中序遍历：遍历顺序为
3. 后序遍历：遍历顺序为
这三种遍历方式的实现，也有多种形式。本文以递归方式为例进行介绍。
1. 前序遍历的递归实现：
```
void preOrder(TreeNode* root) {
if (root == NULL) {
return ;
}
cout << root->val << " "; // 访问根节点
preOrder(root->left); // 遍历左子树
preOrder(root->right); // 遍历右子树
return ;
}
```
2. 中序遍历的递归实现：
```
void inOrder(TreeNode* root) {
if (root == NULL) {
return ;
}
inOrder(root->left); // 遍历左子树
cout << root->val << " "; // 访问根节点
inOrder(root->right); // 遍历右子树
return ;
}
```
3. 后序遍历的递归实现：
```
void postOrder(TreeNode* root) {
if (root == NULL) {
return ;
}
postOrder(root->left); // 遍历左子树
postOrder(root->right); // 遍历右子树
cout << root->val << " "; // 访问根节点
return ;
}
```
二、三种遍历方式的应用
1. 遍历二叉树
三种遍历方式最经典的应用，是遍历二叉树。通过遍历操作，我们可以访问到每一个节点，可以对树进行搜索或者遍历。
2. 寻找二叉树中最大值或最小值
二叉树的中序遍历，可以得到一个有序数组，从而可以寻找到二叉树中最大值或最小值。
3. 寻找二叉树中某一个节点
有时候我们需要查找二叉树中的某一个节点。通过遍历操作，可以找到该节点。具体方法为，在遍历的过程中，对每个节点进行比较，查找出符合要求的节点。
4. 实现表达式的计算
二叉树还可以用于实现表达式的计算。例如，将表达式转化为一棵二叉树，然后通过遍历操作，计算表达式的值。
