美文网首页
实现 convert 方法,把原始 list 转换成树形结构,要

实现 convert 方法,把原始 list 转换成树形结构,要

作者: peerben | 来源:发表于2019-07-06 14:20 被阅读0次

    以下数据结构中,id 代表部门编号,name 是部门名称,parentId 是父部门编号,为 0 代表一级部门,现在要求实现一个 convert 方法,把原始 list 转换成树形结构,parentId 为多少就挂载在该 id 的属性 children 数组下,结构如下:

    // 原始 list 如下

    let list =[
        {id:1,name:'部门A',parentId:0},
        {id:2,name:'部门B',parentId:0},
        {id:3,name:'部门C',parentId:1},
        {id:4,name:'部门D',parentId:1},
        {id:5,name:'部门E',parentId:2},
        {id:6,name:'部门F',parentId:3},
        {id:7,name:'部门G',parentId:2},
        {id:8,name:'部门H',parentId:4}
    ];
    const result = convert(list, ...);
    

    // 转换后的结果如下

    let result = [
        {
          id: 1,
          name: '部门A',
          parentId: 0,
          children: [
            {
              id: 3,
              name: '部门C',
              parentId: 1,
              children: [
                {
                  id: 6,
                  name: '部门F',
                  parentId: 3
                }, {
                  id: 16,
                  name: '部门L',
                  parentId: 3
                }
              ]
            },
            {
              id: 4,
              name: '部门D',
              parentId: 1,
              children: [
                {
                  id: 8,
                  name: '部门H',
                  parentId: 4
                }
              ]
            }
          ]
        },
      ···
    ];
    

    实现了两种解法, 明显第二种更简单, 时间复杂度更低

    export {}
    let list =[
      {id:1,name:'部门A',parentId:0},
      {id:2,name:'部门B',parentId:0},
      {id:3,name:'部门C',parentId:1},
      {id:4,name:'部门D',parentId:1},
      {id:5,name:'部门E',parentId:2},
      {id:6,name:'部门F',parentId:3},
      {id:7,name:'部门G',parentId:2},
      {id:8,name:'部门H',parentId:4}
    ];
    
    interface Dep {
      id: number,
      name: string,
      parentId: number,
      children?: Array<Dep>
    };
    
    function deepCompose(rawList: Array<Dep>, comList: Array<Dep>) {
      const depList = rawList.slice();
      while (depList.length > 0) {
        const node = depList.shift();
    
        // append child nodes
        const children = comList.filter(d => d.parentId === node.id);
        if (children.length === 0) continue;
    
        node.children = children;
    
        deepCompose(children, comList);
      }
    }
    
    function composeTree(depList: Dep[]) {
      // first sort by parentId asc
      depList.sort((a, b) => a.parentId - b.parentId);
    
      // filter head
      const [{ parentId }] = depList;
      let rootDepList = depList.filter(dep => dep.parentId === parentId);
      
      deepCompose(rootDepList, depList);
    
      return rootDepList;
    }
    
    const depTree = composeTree(list);
    console.log(`${JSON.stringify(depTree)}`);
    
    export {}
    
    let list =[
      {id:1,name:'部门A',parentId:0},
      {id:2,name:'部门B',parentId:0},
      {id:3,name:'部门C',parentId:1},
      {id:4,name:'部门D',parentId:1},
      {id:5,name:'部门E',parentId:2},
      {id:6,name:'部门F',parentId:3},
      {id:7,name:'部门G',parentId:2},
      {id:8,name:'部门H',parentId:4}
    ];
    
    interface Dep {
      id: number,
      name: string,
      parentId: number,
      children?: Array<Dep>
    };
    
    function composeTree(depList: Array<Dep>) {
      const depMap = new Map();
      depList.forEach(d => depMap.set(d.id, d));
    
      for (const d of depList) {
        const parentId = d.parentId;
        if (depMap.has(parentId)) {
          const parentDep = depMap.get(parentId);
          parentDep.children = parentDep.children || [];
          parentDep.children.push(d);
        }
      }
    
      // filter head list
      depList.sort((a, b) => a.parentId - b.parentId);
      const [{ parentId }] = depList;
      const rootDepList = depList.filter(dep => dep.parentId === parentId);
    
      return rootDepList;
    }
    
    const res = composeTree(list);
    console.log(`${JSON.stringify(res)}`);
    

    相关文章

      网友评论

          本文标题:实现 convert 方法,把原始 list 转换成树形结构,要

          本文链接:https://www.haomeiwen.com/subject/riuphctx.html