深度优先和宽度优先的区别、前(先)序遍历和中序遍历以及后序遍历的使用

深度优先搜索属于图算法的一种

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件)

过程：是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次

深度优先遍历图的方法是，从图中某顶点v出发：

如下图：

从根节点1开始遍历，遍历过程：1->2->5->9
过程已经走到底，然后就从9开始回退到上一个节点5，5没有除了9以外的节点，再次回退到2,2没有除了5以外的节点。回退到1，1有除了2以外的节点3和4，这时再执行深度优先，步骤为：1->3->6->10
同理，走到10已经是到底了，开始回退，直到回退到3，发现3有除了6以外的子节点，这时回去遍历7
同理，7已经到底了，回退到1节点，继续进行遍历，执行步骤为1->4->8
由上可知，完整的节点遍历属性如下：1->2->5->9->3->6->10->7->4->8

由数的遍历可以知道：前序遍历、中序遍历和后序遍历都属于深度优先遍历

说明：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。

简：从根开始，先左后右

前(先)序遍历：1–>2–>4–>7–>5–>8–>9–>3–>6–>10–>11

说明：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。

简：从底向上，先左后右

中序遍历：4–>7–>2–>8–>5–>9–>1–>3–>10–>6–>11

说明：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。

简：从底先上，先左后右，最后根

后序遍历：7 --> 4 --> 8 --> 9 --> 5 --> 2 --> 10 --> 11 --> 6 --> 3 --> 1

根据后序遍历的特点可以知道：根节点在结尾
根据前序遍历的特点可以知道：根节点在开头
根据中序遍历的特点可以知道：通过前序遍历和中序遍历可以知道根节点后，便可以清楚根节点的左边是左子树，根节点的右边是右子树

宽度优先搜索（又称广度优先搜索，又叫层次遍历）是最简便的图的搜索算法之一，

又叫BFS，属于一种盲目搜寻法

目的：是系统地展开并检查图中的所有节点，以找寻结果。

换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

说明：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。

宽度优先：1–>2–>3–>4–>5–>6–>7–>8–>9–>10–>11

深度优先搜索用栈（stack）来实现
广度优先搜索使用队列（queue）来实现
深度优先遍历：对任何一个分支都深入到不能再深入为止，每个节点只能访问一次。
二叉树的深度优先分为：先序遍历、中序遍历、后序遍历。具体介绍见上面的说明
宽度优先遍历：层次遍历，从上往下对每一层进行遍历，在每一层中，从左往右(也可以从右往左)访问结点，一层一层的进行点，直到没有结点为止
深度优先搜素算法：不全部保留结点，占用空间少；有入栈、出栈操作，运行速度慢。
广度优先搜索算法：保留全部结点，占用空间大； 无入栈、出栈操作，运行速度快。

版权声明：本文为CSDN博主「?abc!」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/yyuggjggg/article/details/120796567