树是一种很常见的数据结构，我们每天浏览的HTML网页就是树形结构的。树的遍历是树的最基本的操作之一，通常实现的方式有两种，深度优先遍历（DFS）和广度优先遍历（BFS）。
深度优先遍历，是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。它可以简单地使用递归来实现，为了方便起见我们以遍历DOM树为例实现一个DFS，这里就以简书的搜索框为遍历的对象吧！它的结构大家可以用F12检查元素看到，结构如下所示
<li class="search">
<form target="_blank" action="/search" accept-charset="UTF-8" method="get">
<input name="utf8" type="hidden" value="✓">
<input type="text" name="q" id="q" value="" placeholder="搜索" class="search-input">
<a class="search-btn" href="javascript:void(null)" style="background-color: rgb(150, 150, 150); border-radius: 50%; color: rgb(255, 255, 255) !important;">
<i class="iconfont ic-search"></i>
</a>
</form>
</li>
深度优先遍历
深度优先遍历的实现非常简单
function DFS(dom,callback){
for(var i=0;i<dom.children.length;i++) {
DFS(dom.children[i],callback)
}
callback(dom)
}
DFS(document.querySelector('.search'),function(dom){
console.log(dom.nodeName)
})
大家可以直接把上面的代码复制到F12之后的Console就能看到遍历结果了，结果为
INPUT * 2
I
A
FORM
LI
符合深度优先遍历里后序遍历的定义。深度优先遍历还有其他遍历方式，前序和中序，区别仅仅是遍历时访问对象的时机，遍历的搜索路径没有变化。对应到实现上，也就仅仅是改变callback函数的位置。
function DFS(dom,callback){
// callback 在此为前序
for(var i=0;i<dom.children.length;i++) {
DFS(dom.children[i],callback)
// callback 在此为中序
}
callback(dom) // callback 在此为后序
}
广度优先遍历
广度优先遍历，是从根结点开始沿着树的宽度搜索遍历。它需要借助先进先出（FIFO）的队列来实现，每次把队列中队首元素取出并访问它，之后把它的子节点全部插入到队尾，循环下去直到队列为空。
function BFS(dom,callback) {
var queue = [dom] // 一开始只有根元素
function walk(dom){
callback(dom) // 访问遍历到的元素
for(var i=0;i<dom.children.length;i++) {
queue.push(dom.children[i]) // 把子元素推入队尾
}
}
while(item = queue.shift()){ // 直到队列为空
walk(item)
}
}
BFS(document.querySelector('.search'),function(dom){
console.log(dom.nodeName)
})
遍历的结果如下，也符合广度优先遍历的定义。
LI
FORM
INPUT * 2
A
I
setTimeout？
看到这里你可能会觉得，好像和setTimeout完全没有半毛钱关系。。。别急，我们稍微把深度优先搜索的代码改一下，就可以实现广度优先搜索了！
function BFS(dom,callback) {
for(var i=0;i<dom.children.length;i++) {
setTimeout(function(){
BFS(dom.children[this],callback)
}.bind(i),0)
}
callback(dom)
}
BFS(document.querySelector('.search'),function(dom){
console.log(dom.nodeName)
})
遍历的结果和广度优先搜索的一致，在命令行输出中可能会多一个undefined，这个是函数BFS执行后表达式的返回结果，不影响树的遍历
LI
FORM
undefined
INPUT * 2
A
I
Why?
是不是非常神奇！我们仅仅加了两行代码，就把一个DFS搜索转变成了BFS搜索。
要解释这个问题，我们得了解Javascript的事件执行机制。Javascript采用的是在UI开发中广泛使用的事件循环机制Event Loop。所有的异步代码，包括点击事件、setTimeout延迟、Ajax请求等等，它们的回调都会被加入到一个统一的事件队列Queue中。
当前函数栈Stack为空时（可以理解为当前没有函数正在执行），Javascript运行时会从Queue中取出队首元素
- 如果
Queue不为空，取出该函数，把它加入函数栈中去执行 - 如果
Queue为空，则等待事件的到来
上面的过程会一致循环下去。为了方便理解，附上MDN上的图和代码~
while(queue.waitForMessage()){
queue.processNextMessage();
}
我们通过setTimeout修改DFS为BFS，就是借助了Javascript的事件队列，把子元素的访问全部加入到事件队列中，当前函数执行完之后（访问根元素），再执行事件队列中的函数（访问子元素）。整个流程和DFS的算法流程一致。
同时，可能你也注意到我们在DFS的原始实现中，就已经借助到了一个FIFO的队列，这也能从另一个角度说明Javascript的事件执行机制和事件的FIFO队列。
事实上，在任何基于Event Loop事件模型的开发框架中，我们都可以借助其事件队列来“实现”从DFS到BFS的转换。
比如iOS开发中，Cocoa框架也由RunLoop实现了Event Loop，所以我们同样可以在iOS开发中借助GCD的方式实现，只不过是把setTimeout(fn,0)换成DispatchQueue.mian.async就行啦~
