后序遍历是怎么遍历的

在计算机科学领域中，遍历树是一项常见任务。有很多不同的方法可以遍历树，并且每种遍历顺序都具有不同的优点和缺点。后序遍历是一种非常有用的遍历顺序。本文将从概念、实现和应用三个方面，分析后序遍历的基础知识，以及它在实际应用中的一些常见用途。

一、概念

在后序遍历中，我们首先访问根节点的左子树，然后访问右子树，最后再遍历根节点。这意味着我们先进入最左侧的节点，逐步向右遍历，知道遍历完右子树，然后才返回访问根节点。这种遍历方式也可以表示为 左-右-根 的顺序。

二、实现

实现后序遍历有多种方法，其中一种是递归。使用递归，我们可以从根节点开始开始，递归遍历左子树，然后循环回到根节点，递归遍历右子树。“左”和“右”子树的遍历顺序与根节点遍历相同。最后记得在访问完右子树后，再来遍历根节点，才算完成后序遍历。

另一种方法是使用栈来实现后序遍历。在这种情况下，我们首先将根节点压入堆栈中，然后持续执行以下操作：

1.从堆栈中弹出一个节点

2.将其左右子节点依次入栈（右节点先入栈，左节点后入栈）

3.将弹出的节点存入“已完成”的列表中

我们不断重复这个过程，直到栈变空。此时，“已完成”列表按照后序遍历的顺序储存了所有已访问节点。

三、应用

后序遍历在树结构中有多种应用。其中一个主要应用是用来求表达式的值。当我们将一个表达式表示为树结构时，我们可以使用后序遍历算法来计算表达式的值。从根节点开始，我们递归地遍历整个树的左子树，然后右子树，最后返回根节点，并利用左子树、右子树计算根的值。

二叉搜索树（BST）的某些操作，如插入、删除和查找，也可以使用后序遍历算法来实现。其他算法，如计算树的深度和宽度，以及判断树结构是否对称等问题也可以使用后序遍历算法解决。

总之，后序遍历是一种非常有用的树遍历算法，可以帮助我们更好地理解树结构的性质并解决实际问题。