定义一颗树,JS中常见的树形数据结构如下,children属性对应的是子树
let tree = [
{
id: '1',
name: '节点1',
children: [
{
id: '1-1',
name: '节点1-1'
}
]
},
{
id: '2',
name: '节点2',
children: [
{
id: '2-1',
name: '节点2-1'
},
{
id: '2-2',
name: '节点2-2',
children: [
{
id: '2-2-1',
name: '节点2-2-1'
}
]
}
]
},
{
id: '3',
name: '节点3'
}
]
二、深度优先遍历(DFS)
1、递归实现
function treeIterator(tree, func) {
tree.forEach((node) =>{
func(node)
node.children &&treeIterator(node.children, func)
})
}
实现逻辑简述:定义treeIterator函数,传入tree(树)和func(回调函数)两个参数,遍历tree数组,执行回调函数,如果当前节点存在children,则递归调用。
函数调用验证:调用treeIterator函数,传入上文定义好的树结构数组,打印出每个节点的name值。
treeIterator(tree, (node) =>{
console.log(node.name)
})
控制台打印结果如下:
2、循环实现
function treeIterator(tree, func) {
let node, curTree = [...tree]
while ((node = curTree.shift())) {
func(node)
node.children &&curTree.unshift(...node.children)
}
}
实现逻辑简述:
(1)定义node作为当前节点,curTree为传入的树(不影响原数组tree);
(2)执行while循环,curTree数组第一个元素从其中删除,并返回第一个元素赋值给node;
(3)①执行回调函数;②如果当前节点存在子树,则追加到curTree数组的开头,继续执行循环,直到curTree没有元素为止。
函数调用验证:参考上述递归实现验证,方式和结果一致。
三、广度优先遍历(BFS)
function treeIterator(tree, func) {
let node, curTree = [...tree]
while ((node = curTree.shift())) {
func(node)
node.children &&curTree.push(...node.children)
}
}
实现逻辑简述:和上述深度优先遍历的循环实现差不多。区别在于如果当前节点存在子树,则追加到list数组的末尾。
做管理后台遇到了一个需求,是要再table里显示路径的名字
如上图所示,但是后端的哥们只返回了每一级的name ,并没有路径。前端能解决的事情就不麻烦后端了,只能用递归解决了:
一、获取每一级中的路径 path
如下图可以看到 pathName 就是把路径拼接起来了,该方法同样适用于树状结构添加任意属性字段。
还有其他几种树状结构常用的递归操作 可以参考该博主文章
https://blog.csdn.net/m0_38134431/article/details/108453055
在实际的工作和业务需求中,我们经常会碰到树形数据结构,比如公司组织架构、组织层级、省市县或者事物的分类等等数据。那么在JavaScript中如何将数组转为树形结构和树形结构转为数组,本文就详细的来探究一下。
先来看看给出了一组怎样的数据,转换为怎样的树形结构。
后台接口返回或者面试官给你的数据:
期望的处理后的数据:
如果后台给了一个这样的数据说让前端自己去转换为树形结构或者面试官给你一组这样的数据让你手写一个转换方法,你会怎么处理?
1、递归实现
2、Map对象实现
3、filter实现
这种方法很有意思,可能大多数人想不到,也是从大佬处学到的(读书人的是怎么能叫抄呢,应该叫“窃”)。
1、reduce取树行数据的所有子集
2、递归实现
3、广度优先遍历法