数据处理 | Tree2List&&List2Tree

准备工作

典型的数结构

const treeData = [
    {
        id: 'p1',
        title: '浙江',
        children: [
            {
                id: 'p1-1',
                title: '杭州',
                children: [],
            }, {
                id: 'p1-2',
                title: '绍兴',
                children: [],
            }
        ],
    }, {
        id: 'p2',
        title: '江苏',
        children: [
            {
                id: 'p2-1',
                title: '南京',
                children: [],
            }, {
                id: 'p2-2',
                title: '苏州',
                children: [],
            }
        ],
    }
]

平铺list结构

const listData = [
    {id: 'p1', title: '浙江'},
    {id: 'p2', title: '江苏'},
    {id: 'p1-1', pid:'p1', title: '杭州'},
    {id: 'p1-2', pid:'p1', title: '绍兴'},
    {id: 'p2-1', pid:'p2', title: '南京'},
    {id: 'p2-2', pid:'p2', title: '苏州'},
];

List转Tree

递归

function list2tree(listData) {
    let treeData = [];
    for (const node of listData) {
        if (!node.pid) {   // 没有pid，说明是父节点
            let p = {...node};   // 对象的解构
            p.children = getChildren(p.id, listData);
            treeData.push(p);
        }
    }
    
    // 找到子节点
    function getChildren(id, listData) {
        // 过滤出pid === id的所有结果并且存在数组中，把这个数组作为父节点的children
        // 注意：这里不能用find，因为find是返回找到的第一个结果
        return listData.filter((item) => item.pid === id)
    }
    
    return treeData;
}

双层循环

function list2tree(listData) {
  listData.forEach(child => {
    const pid = child.pid
    if(pid) {
      listData.forEach(parent => {
        if(parent.id === pid) {
          parent.children = parent.children || []
          parent.children.push(child)
        }
      })
    }
  })
  return listData.filter(n => !n.pid)
}

使用map

function list2tree(listData) {
    const m = new Map(),
          treeData = [];
    
    for (let i = 0; i < listData.length; i++) {
        m.set(listData[i].id, i);   // 把节点的id存入映射
        listData[i].children = [];
    };
    
    // 再次遍历节点
    for (let i = 0; i < listData.length; i++) {
        const node = listData[i];
        
        // 如果有父节点
        if (node.pid && m.has(node.pid)) {
            listData[m.get(node.pid)].children.push(node);
        } else {  // 如果没有
            treeData.push(node);
        }
    }
    
    return treeData;
}

Tree转List

BFS

function tree2list(treeData) {
    const listData = [];
    const queue = [...treeData];
    
    while (queue.length) {
        const node = queue.shift();   // 取出节点
        const children = node.children;  // 取出节点的子节点
        if (children) {
            queue.push(...children);
        }
        listData.push(node);
    }
    return listData;
}

DFS

function tree2list(treeData) {
    const listData  = [];
    const stack = [...treeData];
    
    while (stack.length) {
        const node = stack.pop();
        const children = node.children;
        
        if (children) {
            stack.push(...children);
        }
        listData.push(node);
    }
    return listData;
}

参考

list和tree的相互转换