数据结构深度搜索与广度搜索的概念

————————————本文旨在交流计算机知识，欢迎指正！———————————— 上一章节我们系统介绍了树的存储结构与基本概念，这一章，我们将详细介绍一下——树的基本应用。首先，笔者会介绍树的基本遍历模式，其次，我会详细讲解深度优先搜索和广度优先搜索的概念。 首先，我们来介绍一下树的几种遍历形式：

• 先序遍历
• 中序遍历
• 后序遍历

关于这三种遍历我们会讲两种方法来介绍推理方式： 方法一：无脑法 此方法是最接近于计算机运行本身的，比较冗杂。对于如图所示的树，我将基于它给出做法：

我们可以很轻易的写出这棵树在计算机里的搜索过程（方法：从根节点向下遍历，先左后右，若是遇到空则再重复一遍上一个节点）：ABBCDDDCCBAEEFGHHHGKKKGFFEA。

我们可以发现——不管是怎样的树，按照这种规律遍历，每个独立的节点都一定会出现三次而所谓先序遍历则是：保留第一次出现的数字——ABCDEFGHK

中序遍历则是：保留第二次出现的数字——BDCAEHGKF

后序遍历则是：保留第三次出现的数字——DCBHKGFEA

依此，我们可以实现对二叉树的先中后三序遍历。

方法二：归纳法 此方法是基于找规律的逻辑归纳法，在写树的代码的时候非常实用。

我们可以很轻易的写出这棵树在计算机里的搜索过程（方法：从根节点向下遍历，先左后右，若是遇到空则再重复一遍上一个节点）：ABBCDDDCCBAEEFGHHHGKKKGFFEA。

先序遍历：先序遍历利用先左子树后右子树的顺序从根节点开始先把根节点的左边一直遍历到底再开始遍历右子树。

中序遍历：一个“V”原则，从底部开始，遵循V的形状——左下，中上，右下 的路径遍历，若是中间经过的节点有子树，则再次重复一遍V的过程在子树上。

后序遍历：从下到上先左后右，根的左子树每层遍历完成后向上一层遍历但不遍历根节点，然后同理遍历根右边子树，最后遍历根节点。

我们可以发现： 先序遍历和后序遍历可以确定根节点，中序遍历可以确认左子树和右子树，知其二（先＋中或后＋中）可推断其树： 好了，讲述完成了遍历过程后，我们来讲解一下代码的逻辑过程： 好了，介绍完基本遍历的思路过程之后，我们来正式的介绍深度优先搜索和广度优先搜索的概念。那么， 我们先从深度优先搜索开始： 深度优先搜索的思路形象的表述是：“一条路走到黑，不撞南墙不回头”。每次遍历（先序）走到叶子结点才回头，走另一条道路。 注意：

• 注意枚举的顺序，要做到对每个点都依次枚举到。
• 注意输出方案时 return 的位置。
• 要从数据存入的第一个点开始依次搜（比如数组从 1 开始存，那么 dfs(1) ）。
• 迷宫问题的方向数组别写错
• dfs​ 前可以预处理
• 如果是寻找最短路径多数使用bfs（广度优先搜索）而非dfs（深度优先搜索），不过二十以内的步数也能用dfs，如果数量再多而不想超时就用记忆化。

下面我们来说说bfs吧，bfs（广度优先搜索）就像辐射雷达一样一圈圈一层层的前进，找到了最短层（最短路径）就返回，利用queue队列实现 。

整体思路#

其思路为从图上一个节点出发，访问先访问其直接相连的子节点，若子节点不符合，再问其子节点的子节点，按级别顺序(一层一层)依次访问，直到访问到目标节点。

步骤#

• 起始：将起点（源点，树的根节点）放入队列中
• 扩散：从队列中取出队头的结点**，将它的相邻结点放入队列，不断重复这一步
• 终止：当队列为空时，说明我们遍历了所有的能到的结点，整个图能到的点都被搜索了一遍

好了，如上已经讲解完毕深度优先搜索的思路与和广度优先搜索的思路，希望对你有所帮助！