树的遍历是指按照某种特定的顺序访问树中的每个节点，且每个节点仅被访问一次：
深度优先搜索（DFS）
- 先序遍历：
- 访问根节点。
- 先序遍历左子树。
- 先序遍历右子树。
- 例如，对于二叉树
1(2(4,5),3(6,7))，先序遍历的结果为1 2 4 5 3 6 7。
- 中序遍历：
- 中序遍历左子树。
- 访问根节点。
- 中序遍历右子树。
- 对于上述二叉树，中序遍历的结果为
4 2 5 1 6 3 7。
- 后序遍历：
- 后序遍历左子树。
- 后序遍历右子树。
- 访问根节点。
- 该二叉树的后序遍历结果为
4 5 2 6 7 3 1。
广度优先搜索（BFS）
- 从根节点开始，按照层次依次访问树中的节点。
- 对于二叉树
1(2(4,5),3(6,7))，广度优先遍历的结果为1 2 3 4 5 6 7。
层次遍历
- 与广度优先搜索类似，也是按照层次依次访问节点，但通常使用队列来辅助实现。
- 具体过程为：将根节点入队，然后循环取出队首节点，访问该节点，并将其左右子节点依次入队，直到队列为空。
二叉树的 Morris 遍历
- 一种时间复杂度为 $O(n)$，空间复杂度为 $O(1)$ 的遍历算法。
- 通过利用树的空闲指针，将空间复杂度降低到常数级别。
- 它可以实现先序、中序和后序遍历，具体实现方式略有不同。
线索二叉树遍历
- 对二叉树进行线索化后，可以利用线索进行遍历。
- 线索二叉树通过在节点中增加前驱和后继指针，使得在遍历过程中可以更高效地访问节点。
二叉搜索树的遍历
- 由于二叉搜索树的特殊性质，其遍历结果具有一定的有序性。
- 中序遍历二叉搜索树可以得到一个有序的序列。
不同的遍历算法适用于不同的应用场景。深度优先搜索常用于搜索、路径查找等问题；广度优先搜索则在图的最短路径、层次相关的问题中较为常用；而二叉搜索树的遍历在数据排序、查找等方面有重要应用。
