[转]js将扁平结构数据转换为树形结构
2023-09-11 14:16:15 时间
原文地址:https://segmentfault.com/a/1190000020732216
概述
最近项目又频繁需要对扁平结构进行树形转换,这个算法从我最早接触的时候使用了递归,到现在的单次循环完成,简单记录一下算法的演变
递归实现
function transformTree (list) {
const tree = []
for (let i = 0, len = list.length; i < len; i++) {
if (!list[i].pid) {
const item = queryChildren(list[i], list)
tree.push(item)
}
}
return tree
}
function queryChildren (parent, list) {
const children = []
for (let i = 0, len = list.length; i < len; i++) {
if (list[i].pid === parent.id) {
const item = queryChildren(list[i], list)
children.push(item)
}
}
if (children.length) {
parent.children = children
}
return parent
}
尽管后续对上面的算法进行了很多优化,但是仍未离开递归,递归可能遇到的问题还是会有可能遇到
循环实现
随着进化,循环代替递归是必然的结果~
两次循环
开始使用循环实现时,使用了两次循环完成转换,先进行一次循环将数据转换成 map 结构,使其能通过 id 快速查询
function transformTree (list) {
const tree = []
const record = {}
const length = list.length
for (let i = 0; i < length; i++) {
const item = list[i]
item.children = [] // 重置 children
record[item.id] = item
}
for (let i = 0; i < length; i++) {
const item = list[i]
if (item.pid) {
if (record[item.pid]) {
record[item.pid].children.push(item)
}
} else {
tree.push(item)
}
}
return tree
}
上面的算法相较于递归的实现,不存在栈溢出的问题,而且是线性复杂度,效率已经提高了许多
一次循环
再进行一定的优化,最后变成一次循环完成树形构建
function transformTree (list) {
const tree = []
const record = {}
for (let i = 0, len = list.length; i < len; i++) {
const item = list[i]
const id = item.id
if (record[id]) {
item.children = record[id]
} else {
item.children = record[id] = []
}
if (item.pid) {
if (!record[item.pid]) {
record[item.pid] = []
}
record[item.pid].push(item)
} else {
tree.push(item)
}
}
}
使用对象变量的特性,使用 map 结构直接指向 children 数组,在循环中初始化的同时还能快速查找插入相应的 children 里,使其在一次循环内完成构建,最后附上完整版~
function transformTree (list, options = {}) {
const {
keyField = 'id',
childField = 'children',
parentField = 'parent'
} = options
const tree = []
const record = {}
for (let i = 0, len = list.length; i < len; i++) {
const item = list[i]
const id = item[keyField]
if (!id) {
continue
}
if (record[id]) {
item[childField] = record[id]
} else {
item[childField] = record[id] = []
}
if (item[parentField]) {
const parentId = item[parentField]
if (!record[parentId]) {
record[parentId] = []
}
record[parentId].push(item)
} else {
tree.push(item)
}
}
return tree
}
结语
算是对树形算法的一个简单记录,这种类型的算法在项目中的使用挺多的,但是很多都是写一次就不再碰过(而且很多库都有),回顾一下防止忘记~
相关文章
- JS框架_(JQuery.js)高德地图api
- JS框架_(JQbar.js)柱状图动态百分比进度条特效
- JS框架_(Laydate.js)简单实现日期日历
- JS框架_(Bootstrap.js)实现简单的轮播图
- js中json对象和字符串的转换
- JS实现——用3L和5L量出4L的水
- three.js之让物体动起来方式(二)移动物体
- js showOpenFilePicker showSaveFilePicker showDirectoryPicker API
- js题目小记
- [Tools] Batch Create Markdown Files from a Template with Node.js and Mustache
- ssr.js数据模拟工具
- 使用showdown.js将Markdown文档转换为HTML
- Atitti 跨语言异常的转换抛出 java js
- js 二进制 十进制 十六进制 buffer 字节数组 字符串 相互转换
- js解析json,js转换json成map,获取map的key,value
- js将日期格式转换为YYYY-MM-DD HH:MM:SS
- js-jquery-SweetAlert2【二】配置与方法
- 【JS高级】js之闭包对象_04
- 【JS高级】js之函数、重载、匿名函数、作用域及作用域链_03
- JS字符串和数组之间的转换
- 2023前端面试重点知识点总结【详细】css+js+vue+react+小程序+性能优化等等