二叉树是一种重要的非线性数据结构，它由结点和边组成，其中结点存储数据元素，边连接结点。二叉树的遍历是指按照某种顺序访问每个结点。有三种常见的遍历次序：先序遍历、中序遍历和后序遍历。

先序遍历

先序遍历按照根结点、左子树、右子树的顺序访问结点。具体步骤如下：

1. 访问根结点。

2. 先序遍历左子树。

3. 先序遍历右子树。

例如，对于二叉树 A-B-C-D-E-F，先序遍历的顺序为 A-B-D-E-C-F。

中序遍历

中序遍历按照左子树、根结点、右子树的顺序访问结点。具体步骤如下：

1. 中序遍历左子树。

2. 访问根结点。

3. 中序遍历右子树。

对于二叉树 A-B-C-D-E-F，中序遍历的顺序为 D-B-E-A-C-F。

后序遍历

后序遍历按照左子树、右子树、根结点的顺序访问结点。具体步骤如下：

1. 后序遍历左子树。

2. 后序遍历右子树。

3. 访问根结点。

对于二叉树 A-B-C-D-E-F，后序遍历的顺序为 D-E-B-F-C-A。

非递归遍历

非递归遍历不使用递归调用，而是使用栈或队列来实现遍历。

前序遍历非递归算法

1. 初始化一个栈，将根结点压入栈中。

2. 只要栈不为空，就弹出栈顶元素，并访问该结点。

3. 如果栈顶元素有右子树，则将右子树压入栈中。

4. 如果栈顶元素有左子树，则将左子树压入栈中。

中序遍历非递归算法

1. 初始化一个栈，将根结点压入栈中。

2. 只要栈不为空，就弹出栈顶元素，并访问该结点。

3. 如果栈顶元素有右子树，则将右子树压入栈中。

4. 如果栈顶元素有左子树，则将左子树压入栈中，并继续弹出栈顶元素，直到栈顶元素没有左子树为止。

后序遍历非递归算法

1. 初始化两个栈，分别名为 S1 和 S2，将根结点压入 S1 中。

2. 只要 S1 不为空，就弹出 S1 栈顶元素，并压入 S2 中。

3. 如果栈顶元素有左子树，则将左子树压入 S1 中。

4. 如果栈顶元素有右子树，则将右子树压入 S1 中。

5. 当 S1 为空时，访问 S2 中的结点，出栈的顺序即为后序遍历的顺序。

深度优先搜索

深度优先搜索（DFS）是一种遍历二叉树的技术，它沿着每条路径不断向下遍历，直到达到叶结点，然后回溯到上一层，再沿着另一条路径继续向下遍历。先序遍历和后序遍历都是 DFS 遍历算法。

广度优先搜索

广度优先搜索（BFS）是一种遍历二叉树的技术，它按照层级顺序访问结点，即先访问根结点，然后访问根结点的子结点，再访问子结点的子结点，依此类推。中序遍历是一种 BFS 遍历算法。

应用

二叉树遍历在计算机科学中有着广泛的应用，例如：

表达式求值：先序遍历可以用来计算二叉表达式树的值。

文件系统遍历：文件系统可以表示为二叉树，深度优先搜索可以用来遍历文件系统。

图的深度优先搜索：图可以表示为二叉树，深度优先搜索可以用来遍历图。

二叉搜索树查找：二叉搜索树是用来查找和插入元素的一种特殊二叉树，中序遍历可以用来查找元素。

效率分析

时间复杂度：先序遍历、中序遍历和后序遍历的时间复杂度均为 O(n)，其中 n 为二叉树中结点的数量。

空间复杂度：非递归遍历的空间复杂度为 O(h)，其中 h 为二叉树的高度。递归遍历的空间复杂度为 O(n)。

扩展阅读

Morris 遍历

Morris 遍历是一种非递归的中序遍历算法，它不需要使用栈或队列，空间复杂度为 O(1)。

可见性遍历

可见性遍历是一种可以动态调整遍历顺序的遍历算法，它根据遍历过程中的可见信息来决定下一步访问哪一个结点。

逐层遍历

逐层遍历按照二叉树的层级顺序访问结点，即先访问根结点，然后访问根结点的子结点，再访问子结点的子结点，依此类推。

广度优先搜索与深度优先搜索

广度优先搜索和深度优先搜索是两种不同的遍历算法，它们有不同的时间复杂度和空间复杂度，适用于不同的应用场景。

二叉树遍历的变种

除了先序、中序和后序遍历外，还有许多二叉树遍历的变种，例如：

层次遍历：按照二叉树的层级顺序访问结点。

之字形遍历：按照之字形顺序访问结点。

对称遍历：按照二叉树的对称顺序访问结点。

锯齿形遍历：按照锯齿形顺序访问结点。