学过网站设计的小伙伴们：二叉树结构设计

　　学过网站设计的小伙伴们：二叉树结构设计

　　研究过网站设计的人都知道网站通常是分层设计的。顶层是顶级域名，后面是子域名，子域名下面还有子域名等等，每个子域也可能有多个同级域名，URL之间可能有链接，形成一个复杂的网络。

　　网站的网址很多的时候，一定要好好设计好网址，否则在后期的理解、维护或者开发过程中会很混乱。了解了以上网页结构设计后，现在正式介绍网络爬虫中的深度优先算法。

　　上图是一个二叉树结构。通过遍历这棵二叉树，我们可以比较爬取网页，加深对爬取策略的理解。深度优先算法的主要思想是先从顶级域名A开始，然后从中提取两个链接B和C。抓取链接B后，下一个要抓取的链接是D或E，而不是抓取。抓取链接B后，立即抓取链接C，抓取链接D后，发现链接D中的所有URL都被访问过。在此之前，我们已经建立了一个访问过的URL列表，专门用来存储访问过的URL。当链接 D 被完全抓取后，接下来会抓取链接 E。链接E爬取完成后，链接C不会被爬取，而是继续往下爬爬爬取链接I。 原理是链接会一步一步往下爬，只要下有子链接链接，并且子链接没有被访问过，这就是深度优先算法的主要思想。深度优先算法是让爬虫一步一步往下爬，然后一步一步往后退，以深度优先。理解了深度优先算法后，再看上图，可以得到二叉树呈现的爬虫爬取链接顺序如下：A、B、D、E、I、C、F、G、H（假设此处左侧的链接）将首先被抓取）。其实我们在做网络爬虫的时候，经常会用到这个算法来实现。其实我们常用的Scrapy爬虫框架默认也是用这个算法实现的。由以上理解，我们可以认为深度优先算法本质上是通过递归实现的。

　　下图展示了深度优先算法的代码实现过程。

　　深度优先的过程实际上是以递归的方式实现的。看上图中的代码，先定义一个函数来实现深度优先处理，然后传入节点参数。如果节点不为空，则将其打印出来。您可以将其与二叉树中的顶点 A 进行比较。节点打印后，检查是否有左节点（链接B）和右节点（链接C）。如果左节点不为空，则返回，并调用深度优先函数本身再次递归得到一个新的左节点（链接D）和右节点（链接E），以此类推，不会停止直到遍历完所有节点或达到既定条件。右节点的实现过程也一样，不再赘述。

　　深度优先过程以递归方式实现。当递归继续而不跳出递归或递归过深时，容易发生栈溢出，实际应用过程中要注意这一点。

　　深度优先算法和广度优先算法是数据结构中非常重要的算法结构，也是非常常用的算法，也是面试过程中非常常见的面试题，所以推荐大家需要掌握，下一篇文章我们将介绍广度优先算法，敬请期待。

　　对网络爬虫中深度优先算法的简单介绍到此结束。你们做对了吗？