二叉树的三种遍历例题

二叉树是一种非常基础的数据结构，也是算法的重要基础。二叉树的三种遍历方式是前序遍历、中序遍历和后序遍历。这三种遍历方式可以用于二叉树的遍历、寻找二叉树中最大值或最小值、寻找二叉树中某一个节点、实现表达式的计算等。在本文中，我们将从不同的角度，分析这三种遍历方式。

一、三种遍历方式的定义和实现方式

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. 实现表达式的计算

二叉树还可以用于实现表达式的计算。例如，将表达式转化为一棵二叉树，然后通过遍历操作，计算表达式的值。