最近要做一个节点树的遍历,记录下两种遍历算法。这两种遍历针对普通的树结构,非二叉树。看懂了,非常简单。
深度优先遍历(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))
对于算法来说 无非就是时间换空间 空间换时间
总结:
- 深度优先不需要记住所有的节点, 所以占用空间小, 而广度优先需要先记录所有的节点占用空间大
- 深度优先有回溯的操作(没有路走了需要回头)所以相对而言时间会长一点
- 深度优先采用的是堆栈的形式, 即先进后出;广度优先则采用的是队列的形式, 即先进先出
使用:所以对于深度优先和广度优先,计算出来的结果是完全不一样的,实际运用可以根据需要进行选择。如果对顺序有要求的,可能需要按DFS来计算,如果对于顺序没有要求的,可以采用BFS