JS 【详解】树的遍历（含深度优先遍历和广度优先遍历的算法实现）

本文主要是介绍JS 【详解】树的遍历（含深度优先遍历和广度优先遍历的算法实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

用 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 宽度优先搜索的简写
• 此处算法使用队列实现（先进先出），每发现节点有子节点，则将子节点添加到队列尾部

这篇关于JS 【详解】树的遍历（含深度优先遍历和广度优先遍历的算法实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---