本文介绍JavaScript中树结构的概念、术语及模拟方法，重点解析深度优先（DFS）与广度优先（BFS）两种核心遍历算法。通过代码示例展示如何利用对象和数组构建树，并详细阐述DFS的递归实现与BFS的队列实现思路，帮助前端开发者掌握常见树形数据结构的处理技巧。
树的基本概念
在现实生活中，无论是柳树、杨树还是桃树，树木随处可见。在计算机科学领域，树是一种用于表示分层结构的抽象数据模型。
具体结构可参考下图所示。
树结构在实际应用中十分广泛，例如公司的组织架构就可以用树形图来表示，如图所示。
除了组织架构，族谱关系、行政区划（如省、市）等层级信息同样可以使用树结构进行建模。
树的相关术语定义
树结构包含多个专业术语，具体定义如下图所示。
- 树：由n（n≥0）个节点构成的有限集合。当
n=0时，该集合被称为空树。 - 节点的度：指节点拥有的子树数量。例如，B节点的度为2，A节点的度为3。
- 树的度：树中所有节点的最大度数。以上图为例，该树的度为3。
- 叶子节点：度为0的节点，也称为叶节点。
- 子节点：参考上图中的定义。
- 兄弟节点：参考上图中的定义。
- 根节点：参考上图中的定义。
- 树的深度：树中所有结点的最大层次数。以上图为例，树的深度为3。
- 节点的层次：例如E节点的层次为3。节点层次等于父节点层次加1，根节点的层次定义为1。
- 路径：从一个节点到另一个节点的通道，例如A到H的路径为
A D H。 - 路径长度：从一个节点到另一个节点的距离，例如A到H的路径长度为3。
JavaScript中的树结构实现
树结构是前端开发中最常见的数据结构之一，广泛应用于DOM树、级联选择器、树形组件等场景。
JavaScript原生并未提供专门的树数据结构，但可以通过对象和数组来模拟实现。
参考以下代码示例。
const tree = {
value: 'A',
children: [
{
value: 'B',
children: [
{ value: 'E', children: null },
{ value: 'F', children: null },
],
},
{
value: 'C',
children: [{ value: 'G', children: null }],
},
{
value: 'D',
children: [
{ value: 'H', children: null },
{ value: 'I', children: null },
],
},
],
}广度优先与深度优先遍历算法
深度优先遍历（DFS）
深度优先遍历算法的核心思想是尽可能深地搜索树的分支，其遍历顺序如下图所示。
实现思路如下：
- 首先访问根节点；
- 然后对根节点的
children持续进行深度优先遍历（采用递归方式）；
具体实现代码如下：
function dfs(root) {
console.log(root.value)
root.children && root.children.forEach(dfs) // 与下面一致
// if (root.children) {
// root.children.forEach(child => {
// dfs(child)
// })
// }
}
dfs(tree) // 这个tree就是前面定义的那个树
/* 结果
A
B
E
F
C
G
D
H
I
*/运行结果与图示顺序一致，表明算法逻辑正确。
广度优先遍历（BFS）
广度优先遍历的核心思想是依次访问距离根节点较近的节点，其遍历顺序如下图所示。
实现思路如下：
- 创建一个队列，并将根节点加入队列；
- 将队头元素出队并进行访问；
- 将队头元素的
children依次加入队列； - 重复执行步骤2和3，直到队列为空。
具体实现代码如下：
function bfs(root) {
// 1. 新建队列 跟节点入队
const q = [root]
// 4 重复执行
while (q.length > 0) {
const node = q.shift() // 2 队头出队
console.log(node.value)
// 3 队头 children 依次入队
node.children &&
node.children.forEach(child => {
q.push(child)
})
}
}
bfs(tree)
/* 结果
A
B
C
D
E
F
G
H
I
*/运行结果与图示顺序一致，表明算法逻辑正确。
本文介绍了JavaScript树结构及深度优先算法的相关内容，更多关于JS树结构的知识可参考本站历史文章或继续阅读后续内容，感谢支持。