/ 前端基础

将扁平的数据结构转换成层级的数据结构

因为项目需求,有时候需要把扁平的数据结构变成通过id, pid联结起来的层叠数据结构,因此写了这个函数。


原始格式:

[
  {id: 'node1',pid: 'root',content: 'test'},
  {id: 'node2',pid: 'root',content: 'test'},
  {id: 'node3',pid: 'node1',content: 'test'},
  {id: 'node4',pid: 'node2',content: 'test'},
  {id: 'node5',pid: 'node3',content: 'test'},
  {id: 'node6',pid: 'node1',content: 'test'}
]

目标格式:

[
  {
    id: 'node1',
    pid: 'root',
    content: 'test',
    children: [
      {
        id: 'node3',
        pid: 'node1',
        ccontent: 'test',
        children: [
          {id: 'node5',pid: 'node3',content: 'test'}
        ]
      },
      {id: 'node6',pid: 'node1',content: 'test'}
    ]
  },
  {
    id: 'node2',
    pid: 'root',
    content: 'test',
    children: [
      {id: 'node4',pid: 'node2',content: 'test'}
    ]
  },
]

思路:

  1. 父节点 ? Y --> (挂载点 ? 挂载 : 创建后挂载) : N --> 悬空
  2. 遍历悬空节点重复步骤1
  3. 重复步骤1...直至无悬空节点

难点:

  1. 寻找父节点的位置:父节点,id属性值匹配 --> 建立id值和路径的映射表 --> 挂载的时候更新映射表 (路径的一般形式 2.children.3.children.1)
  2. 对于root的子节点,一开始是没有映射关系的,所以root的子节点直接push,即这样调用 mount(child, root), 路径即是root, 不用查找映射表
  3. 写一个根据路径挂载子节点的函数 foo (child, path)

归纳:

  1. 封装函数的参数 tree (origin, id, pid, root, mountNode) 原始数据,指定id, pid字段, root节点名称, mountNode挂载点名称(比如children)
  2. 迭代tree函数时,映射表不能在迭代作用域内部,所以映射表应该在迭代函数的外部
  3. 要求不能有最终悬空的节点,有的话报错(通过深度控制,超过一定深度后认为原始数据非法)

最终实现:

// 参数说明:原始数据,id字段名,pid字段名,挂载点名,root节点名
function cascadeTree(originAry, id, pid, children, root) {
  id = id || 'id'
  pid = pid || 'pid'
  children = children || 'children'
  root = root || 'root'
  var reflection = {} // 映射表,存储已挂载节点的位置
  var targetPath = null // 存储每次目标挂载点的变量
  var hanging = JSON.parse(JSON.stringify(originAry)) // 深复制
  var output = [] // 最终输出

  var depth = 11 // 控制层数(结构的深度),10层后还没挂载完说明可能有错误的、无法挂载的点,报错

  // 挂载子节点到指定路径的函数
  function mountChild(child, path) {
    // 为 child 添加 children 字段
    child[children] = []

    // 如果是根节点的子节点直接push
    if (path === root) {
      output.push(child)
      reflection[child[id]] = (output.length - 1).toString()
      return
    }

    var break_path = path.split('.')
    var tempNode = null
    while (break_path.length) {
      tempNode = tempNode ? tempNode[break_path[0]] : output[break_path[0]]
      break_path.shift()
    }
    tempNode[children].push(child)
    reflection[child[id]] = path + '.' + children + '.' + ((tempNode[children]).length - 1)
  }
  while (hanging.length) {
    hanging.forEach(function (item, index, array) {
      targetPath = item[pid] === root ? root : reflection[item[pid]]
      if (targetPath) {
        mountChild(item, targetPath)
        hanging.splice(index, 1)
      }
    })
    depth -= 1
    if (depth === 0) {
      hanging.length = 0
      console.error('Error, depth > 10 or some node couldn\'t be mounted.')
      output = false
    }
  }

  return output
}