前面的文章我们讲了二叉搜索树的插入和搜索的基础，今天这篇文章我们讲二叉搜索树中一个非常关键的概念：遍历。遍历，顾名思义，就是把所有的节点都要过一遍。那怎么去过呢，是先横后纵，还是先纵后横呢。在二叉搜索树中，遍历的方式大致分为两种，一种是深度优先遍历，一种是广度优先遍历。这里面以深度优先的遍历最为常用，而且深度优先遍历中，还会分出三种不同的遍历方法。下面，我们就从深度优先遍历开始介绍。

深度优先遍历

对于深度优先遍历来说，最关键的就是遍历的时候先要把当前节点的左子树遍历完，然后再把当前节点的右子树遍历完。在遍历左右子树的时候，当前节点的遍历顺序，决定了当前二叉搜索树中所有节点的打印顺序。而且，同样是根据当前节点的遍历顺序，我们把深度优先遍历分为三种：前序遍历、中序遍历，以及后序遍历。

具体示意图如下：

深度优先遍历示意图

如上图所示，我们在当前节点41的左下、中下，以及右下又分别放置了三个空心小圆点。我们可以这样规定：当我们想根据深度优先算法遍历该二叉搜索树时，这三个空心小圆点一旦被访问，就要被填充。因此，当我们在填充左下这个小圆点之前，遍历当前节点，那就是前序遍历；当我们在填充中下这个小圆点之前，遍历当前节点，那就是中序遍历；当我们在填充右下这个小圆点之前，遍历当前节点，那就是后序遍历。

结合这三个辅助的小圆点，我们可以更好的认识这三种深度优先遍历算法。下图就是结合着三个小圆点，将一棵二叉搜索树按照前序遍历的方式，进行了所有节点的遍历。

前序遍历示意图

有了前序遍历示意图，希望你能够根据该示意图将二叉搜索树的中序遍历和后序遍历画出来。那这三种深度优先的遍历算法有什么用呢？

对于前序遍历来说，当我们想要打印一个树形结构时，比如打印某个文件夹的目录结构，前序遍历是不二之选；

对于中序遍历来说，因为打印出来具有从小到大的顺序，所以使用场景就不用多说了；

对于后序遍历来说，当想进行破坏性操作时，可以使用该遍历算法。因为后序遍历是把左右子树都遍历完成之后，才会遍历当前节点，所以如果我们想释放一棵二叉搜索树的所有空间，肯定要把当前节点的左右子树都释放完，才能释放当前节点。

广度优先遍历

广度优先遍历在二叉搜索树中又叫层序遍历。对于二叉搜索树中，层序遍历使用的并不多。之所以要介绍广度优先遍历，是因为广度优先遍历是一个非常重要的概念。广度优先遍历在我们后续介绍图的时候，将会是一个非常重要的遍历方法。

那在二叉搜索树中，该如何实现广度优先遍历呢？我们需要借助一个先进先出的队列来辅助实现，下面是我们实现的具体示意图：

广度优先遍历示意图

如上图所示，对于广度优先遍历算法来说，有这个先进先出队列的辅助非常重要。我们第一步是把该二叉搜索树的根节点放到队列中，后面即为访问先进先出队列的过程。当先进先出队列不为空的时候，我们就弹出该队列中的第一个元素，弹出这个元素的时候，要检查该元素有没有对应的左右孩子节点，如果有则要将该左右孩子节点分别放入队列，如果没有，则访问下一个节点，依次类推。

好了，这就是我们介绍的二叉搜索树的两种遍历方法，相比较而言，深度优先遍历更为常用，但这并不是说广度优先算法不重要。后面在介绍图的时候你会发现，广度优先算法同样非常重要。

我是徐建航，这是我写的第73篇文章，欢迎你加入007社群，七天写一篇，一起写七年，七年之后一起去南极。