线性结构与树形结构相互转换(ES6实现)

前言

当树形结构的层级越来越深时,操作某一节点会变得越来越费劲,维护成本不断增加。所以线性结构与树形的相互转换变得异常重要!

首先,我们约定树形结构如下:

node = {
  id: number,  // 数值<br />  parentId: number,  // 数值
  name: string,<br />  children: [] || null,  // 用数组的方式保存子节点,适合更多业务场景  
}

线性结构:

list = [
   { id: number, parentId: number, name: string }, 
   { id: number, parentId: number, name: string },
];

特殊情况

上面的树形结构并不是很完美,当遇到菜单或者分类等业务场景时,每个顶级节点的parentId约定为0,当存在多个顶级节点,显得不是一个完整的树。所以在这类特殊情况下,我们需要构造一个顶级节点。将菜单或者分类的原有顶级节点存储至该节点的children中。 所以最后约定顶级节点如下。

root = null || {
  id: 0,
  parentId: null,
  children: [node1, node2, ...],  
}

线性结构与树形结构相互转换

线性转树形:

function listConvertTree(list) {
  let root = null;
  if (list && list.length) {
    root = { id: 0, parentId: null, children: [] };
    const group = {};
    for (let index = 0; index < list.length; index += 1) {
      if (list[index].parentId !== null && list[index].parentId !== undefined) {
        if (!group[list[index].parentId]) {
          group[list[index].parentId] = [];
        }
        group[list[index].parentId].push(list[index]);
      }
    }
    const queue = [];
    queue.push(root);
    while (queue.length) {
      const node = queue.shift();
      node.children = group[node.id] && group[node.id].length ? group[node.id] : null;
      if (node.children) {
        queue.push(...node.children);
      }
    }
  }
  return root;
}

树形转线性:

function treeConvertList(root) {
  const list = [];
  if (root) {
    const Root = JSON.parse(JSON.stringify(root));
    const queue = [];
    queue.push(Root);
    while (queue.length) {
      const node = queue.shift();
      if (node.children && node.children.length) {
        queue.push(...node.children);
      }
      delete node.children;
      if (node.parentId !== null && node.parentId !== undefined) {
        list.push(node);
      }
    }
  }
  return list;
}

相关推荐