扁平数组和树形结构的相互转换

2023年 7月 25日 767点热度 0人点赞 0条评论

扁平数组转换为树形结构

这个是最常用的，当我们从后台获取一个扁平数组的时候，通常比如用id、pid来标识父子关系，如：

var arr = [{id: 1, pid: '-1'},{id: 11, pid: '1'},{id: 12, pid: '1'}]

用map记录的方法是最常用效果也最好的复杂度是O(nlgn),支持多个根节点:

function listToTree(list) {
    var map = {}, node, tree= [], i;
    for (i = 0; i < list.length; i ++) {
        map[list[i].id] = list[i]; 
        list[i].children = []; 
    }
    for (i = 0; i < list.length; i += 1) {
        node = list[i];
        if (node.pid !== '-1') {
            map[node.pid].children.push(node);
        } else {
            tree.push(node);
        }
    }
    return tree;
}

listToTree(arr); //[{"id":1,"pid":"-1","children":[{"id":11,"pid":"1","children":[]},{"id":12,"pid":"1","children":[]}]}]

但是项目中有个需求，在后台没有返回给带层级信息level的时候，需要用到层级信息，这样转换没法计算出层级，因此就需要用迭代的方法了，默认根节点层级为0，依次递增：


function listToTreeWithLevel(list, parent, level) {
var out = []
for (var node of list) {  
        if (node.pid == parent) {
            node.level = level;
            var children = listToTreeWithLevel(list, node.id, level + 1)
            if (children.length) {
                node.children = children
            }
            out.push(node)
        }
}
return out
}

listToTreeWithLevel(arr, '-1', 0) //[{"id":1,"pid":"-1","children":[{"id":11,"pid":"1","children":[],"level":1},{"id":12,"pid":"1","children":[],"level":1}],"level":0}]

使用for循环(性能比递归好很多,推荐使用)

 // jsonData: 数组对象
    // id: 每条数据的id
    // pid: 每条数据的父节点对应字段
    /*
      [
        {
          name: '测试',
          id: '1001',
          pid: '-1',
        }
      ] 
    */
    jsonToTree(jsonData, id, pid) {
      let result = [],
        temp = {};
      for (let i = 0; i < jsonData.length; i++) {
        temp[jsonData[i][id]] = jsonData[i]; // 以id作为索引存储元素，可以无需遍历直接定位元素
      }
      for (let j = 0; j < jsonData.length; j++) {
        let currentElement = jsonData[j];
        let tempCurrentElementParent = temp[currentElement[pid]]; // 临时变量里面的当前元素的父元素
        if (tempCurrentElementParent) {
          // 如果存在父元素
          if (!tempCurrentElementParent["children"]) {
            // 如果父元素没有chindren键
            tempCurrentElementParent["children"] = []; // 设上父元素的children键
          }
          tempCurrentElementParent["children"].push(currentElement); // 给父元素加上当前元素作为子元素
        } else {
          // 不存在父元素，意味着当前元素是一级元素
          result.push(currentElement);
        }
      }
      return result;
    }

使用递归的方式

translateDataToTree(data) {
    // 没有父节点的数据
    const parent = data.filter(value => value.pid.trim() === '-1'
    || value.pid.trim() === null
    || value.pid.trim() === '');

    // 有父节点的数据
    const child = data.filter(value => value.pid.trim() !== '-1'
    && value.pid.trim() !== null
    && value.pid.trim() !== '');

    // 定义转换方法的具体实现
    const translator = (parents, children) => {
      // 遍历父节点数据
      parents.forEach((item) => {
        // 遍历子节点数据
        children.forEach((current, index) => {
          // 此时找到父节点对应的一个子节点
          // if (current.pid === parent.id) {
          if (current.pid === item.id) {
            // 对子节点数据进行深复制，这里只支持部分类型的数据深复制，
            const temp = JSON.parse(JSON.stringify(children));
            // 让当前子节点从temp中移除，temp作为新的子节点数据，这里是为了让递归时，子节点的遍历次数更少，如果父子关系的层级越多，越有利
            temp.splice(index, 1);
            // 让当前子节点作为唯一的父节点，去递归查找其对应的子节点
            translator([current], temp);
            // 把找到子节点放入父节点的children属性中
            if (typeof item.children !== 'undefined') {
              item.children.push(current);
            } else {
              // eslint-disable-next-line no-param-reassign
              item.children = [current];
            }
          }
        });
      });
    };

    // 调用转换方法
    translator(parent, child);
    // 返回最终的结果
    return parent;
  },

树形结构转换为扁平数组

这个其实就是数据结构中的广度优先遍历：


function treeToList(tree) {
var queen = [];
var out = [];
queen = queen.concat(tree);
while(queen.length) {
  var first = queen.shift();
if (first.children) {
    queen = queen.concat(first.children)
  delete first['children'];
}

out.push(first);
}
return out;
}

var tree = [{"id":1,"pid":"-1","children":[{"id":11,"pid":"1","children":[]},{"id":12,"pid":"1","children":[]}]}];
treeToList(tree) //[{"id":1,"pid":"-1"},{"id":11,"pid":"1"},{"id":12,"pid":"1"}]

树形结构转换平级，不包含父级的数据

treeToList(list) {
let result = [];

function traverse(node) {
  if (!node.children) { // 如果当前节点没有子节点，说明是叶子节点
    const leafNode = {...node}; // 创建一个新对象，避免直接修改原对象
    delete leafNode.children; // 删除children属性
    result.push(leafNode); // 将叶子节点添加到结果数组中
  } else {
    node.children.forEach(child => traverse(child)); // 遍历子节点
  }
}

list.forEach(item => traverse(item));

return result;
}