最近要做一个节点树的遍历，记录下两种遍历算法。这两种遍历针对普通的树结构，非二叉树。看懂了，非常简单。

深度优先遍历(depthFirstSearch—DFS)

看下面的图比较直观，按照层级一级一级遍历，先一条分支走到底，再回过来按同样的方法查找另外一个分支，一般采用递归方式。

广度优先遍历(broadFirstSearch—BFS)

看下面的图，也是按照层级，一层一层查找，不同的是，从源节点开始，查找子节点，所有的子节点操作完之后，再操作上所有子节点的孙节点。

上代码：

var data3 = [
 {
 name: 'a',
 children: [
 { name: 'b', children: [{ name: 'e' }] },
 { name: 'c', children: [{ name: 'f' }] },
 { name: 'd', children: [{ name: 'g' }] },
 ],
 },
 {
 name: 'a2',
 children: [
 { name: 'b2', children: [{ name: 'e2' }] },
 { name: 'c2', children: [{ name: 'f2' }] },
 { name: 'd2', children: [{ name: 'g2' }] },
 ],
 }
]

// 深度遍历, 使用递归
function getName(data) {
let t1 = +new Date();
 const result = [];
 let index = 0
 data.forEach(item => {
 const map = data => {
 let tempO = {}
 tempO[data.name] = index;
 index ++
 result.push(tempO);
 data.children && data.children.forEach(child => map(child));
 }
 map(item);
 })
console.log(+new Date() - t1);
 return result;
}

// 广度遍历, 创建一个执行队列, 当队列为空的时候则结束
function getName2(data) {
 let t1 = +new Date();
 let result = [];
 let queue = data;
 let index = 0
 while (queue.length > 0) {
 [...queue].forEach(child => {
 queue.shift();
 let temp ={}; temp[child.name] = index;
 result.push(temp);
 index ++
 child.children && (queue.push(...child.children));
 });
 }
 console.log(+new Date() - t1);
 return result;
}

console.log(getName(data3))
console.log(getName2(data3))

对于算法来说 无非就是时间换空间 空间换时间

总结：

1. 深度优先不需要记住所有的节点, 所以占用空间小, 而广度优先需要先记录所有的节点占用空间大
2. 深度优先有回溯的操作(没有路走了需要回头)所以相对而言时间会长一点
3. 深度优先采用的是堆栈的形式, 即先进后出；广度优先则采用的是队列的形式, 即先进先出

使用：所以对于深度优先和广度优先，计算出来的结果是完全不一样的，实际运用可以根据需要进行选择。如果对顺序有要求的，可能需要按DFS来计算，如果对于顺序没有要求的，可以采用BFS