JS树形转扁平数据算法：递归、双循环与单循环优化详解

递归实现方案

通过递归方式遍历树形数组，当检测到包含 children 属性的对象时，再次调用递归函数处理其子节点。每次遍历到的节点数据被存入预先声明的数组中，待所有递归调用结束后，该数组即为所需的扁平数据结果。


let res = []
const fn = (source)=>{
 source.forEach(el=>{
  res.push(el)
  el.children && el.children.length>0 ? fn(el.children) : ""
 })
}

示例 1


let res = []  // 用于存储递归结果（扁平数据）
// 递归函数
const fn = (source)=>{
 source.forEach(el=>{
  res.push(el)
  el.children && el.children.length>0 ? fn(el.children) : ""  // 子级递归
 })
}
 
// 树形数据
const arr = [
 { id: "1", rank: 1 },
 { id: "2", rank: 1,
  children:[ 
   { id: "2.1", rank: 2 },
   { id: "2.2", rank: 2 } 
  ] 
 },
 { id: "3", rank:1,
  children:[ 
   { id: "3.1", rank:2, 
    children: [ 
     { id:'3.1.1', rank:3,
      children:[ 
       { id: "3.1.1.1", rank: 4, 
        children:[
         { id: "3.1.1.1.1", rank: 5 }
        ] 
       } 
      ] 
     } 
    ] 
   } 
  ] 
 }
]
 
fn(arr)    // 执行递归函数
console.log(res) // 查看结果

结果：

递归实现方案

查看源码

若需将扁平数据还原为树形结构，可参考文章：js实现无限层级树形数据结构（创新算法）。

js将扁平结构数据转换为树形结构

递归实现

循环实现方案


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 实现树形数据转成扁平数据的方法示例介绍完毕。如需了解更多相关内容，请搜索本站历史文章或继续浏览下方推荐内容。感谢大家的支持！

JavaScript 实现树形数据转扁平数据：从递归到一次循环的演进

递归实现方案

循环实现方案

两次循环优化

一次循环终极优化

实用工具推荐