用 js 描述树
let tree = [ { label:'a', children:[ { label:'b', children:[ { label:'d' }, { label:'e' } ] }, { label:'c', children:[ { label:'f' } ] } ] } ]
- 使用数组是因为树的节点有顺序
深度优先遍历
从根节点出发，优先遍历最深的节点
遍历顺序为 abdecf
function DFS(tree) { tree.forEach((node) => { console.log(node.label); node.children && DFS(node.children); }); }
- DFS 是 Depth-First-Search 深度优先搜索的简写
广度优先遍历
从根节点出发，从上往下对每一层从左到右依次访问
遍历顺序为 abcdef
function BFS(tree) { let queue = tree; for (let i = 0; i < queue.length; i++) { console.log(queue[i].label); if (queue[i].children) { queue = queue.concat(queue[i].children); } } }
- BFS 是 Breadth First Search 宽度优先搜索的简写
- 此处算法使用队列实现（先进先出），每发现节点有子节点，则将子节点添加到队列尾部
