树
什么是树?
在生活中,大家对树肯定不陌生,小朋友都知道树不就是一类植物嘛,不管在任何地方都有各种各样的树。但是在计算机科学里面树是什么呢?一种分层数据的抽象模型,在我们前端工作中无处不在。在 JavaScript 中没有树这种数据结构,但是可以通过 Object 和 Array 这两个数据结构构建树。
深度与广度优先遍历
深度优先遍历
尽可能深的搜索树的分支,主要通过递归实现。
口诀:
- 访问根阶段
- 对根节点的 children 每个元素进行深度优先遍历
javascript
function dfs(root) {
console.log(root.value)
root.children.forEach(dfs)
}
function dfs(root) {
console.log(root.value)
root.children.forEach(dfs)
}
广度优先遍历
先访问离根节点最近的节点,主要通过队列实现。
口诀:
- 新建一个队列,把根节点入队
- 把队头出队并访问
- 把队头的 children 元素分别入队
- 重复 2 和 3 步骤,直到队列为空
javascript
function bfs(root) {
const q = [root]
while (q.length) {
const n = q.shift()
console.log(n)
n.children.forEach((child) => {
q.push(child)
})
}
}
function bfs(root) {
const q = [root]
while (q.length) {
const n = q.shift()
console.log(n)
n.children.forEach((child) => {
q.push(child)
})
}
}
常用操作
- 深度优先遍历
- 广度优先遍历
应用场景
- DOM 树
- 级联选择
- 树形控件
- 组织架构图