DFS与BFS实现,考虑到递归有爆栈的可能,所以,采用循环来做,实现思路都是通过维护一个stack,只是入栈的规则不一样。
以遍历DOM节点为例:
function dfs(node) {
const stack = [node];
const nodes = [];
let tmp;
while (tmp = stack.pop()) {
nodes.push(tmp)
let childs = tmp.children, len = childs.length, i = len - 1;
for (; i > -1; i--) {
stack.push(childs[i])
}
}
return nodes
}
function bfs(node) {
const stack = [node];
const nodes = [];
let tmp;
while (tmp = stack.pop()) {
nodes.push(tmp)
let childs = tmp.children, len = childs.length, i = 0;
for (; i < len; i++) {
stack.unshift(childs[i])
}
}
return nodes
}