关于树形插件展示中数据结构转换的算法

发表日期：2017-06-03

问题背景

在一些目录结构、机构层级等展示的场景中，我们经常会用到一些成熟的树形插件来进行轻松展示，比如ztree等。大多数插件会支持对两种数据源格式的解析，一种是通用的二维数据结构，一种是树状数据结构。对于这两种数据结构的称呼在各插件中可能不尽相同，这里依照二维结构和树状结构来称呼。举例说明如下：

// 二维数据结构
[{
  "id": "001",
  "name": "总部",
  "parentId": "0"
}, {
  "id": "002",
  "name": "二级门店1",
  "parentId": "001"
}, {
  "id": "003",
  "name": "三级门店",
  "parentId": "002"
}, {
  "id": "004",
  "name": "二级门店2",
  "parentId": "001"
}]

// 树状数据结构
[{
    "id": "001",
    "name": "总部",
    "parentId": "0",
    "children": [{
      "id": "002",
      "name": "二级门店1",
      "parentId": "001",
      "children": [{
        "id": "003",
        "name": "三级门店",
        "parentId": "002",
        "children": []
      }]
    }, {
      "id": "004",
      "name": "二级门店2",
      "parentId": "001",
      "children": []
    }]
}]

但在某些插件中，或在某些特殊场景中，我们有两种数据结构之间相互转换的需求，需要自己写一个辅助函数来完成。这里就提供两个这样的工具函数来完成数据结构的转换。

Note: 要说明的是，工具函数没有经过大数据量转换测试，所以对有实时性、大量源数据转换需求的同学而言，请自行测试分析，可采取前置或异步等方案处理。由于自身技术水平的局限性，算法本身会有性能优化的空间，若有更优处理算法，还望交流分享，谢谢！

解决方案

我们来分开介绍两种数据结构之间的转换算法，每个小结中我会先贴出整个函数的代码清单，以便大家复制粘贴，然后会简要说明其中大概的逻辑思路。

二维数据结构 => 树状数据结构

/**
 * 将通用的二维数据结构转换为树状数据结构
 * @param  {String} rootParentIdValue 表示根节点的父类id值
 * @param  {String} parentIdName      表示父类id的节点名称
 * @param  {String} nodeIdName        表示二维结构中，每个对象主键的名称
 * @param  {Array} listData           为二维结构的数据
 * @return {Array}                    转换后的tree结构数据
 */
function listToTree(rootParentIdValue, parentIdName, nodeIdName, listData) {
  if (listData instanceof Array && listData.length > 0 && listData[0][parentIdName]) {
    var rootList = [],
        nodeList = []
      
    listData.forEach(function(node, index) {
      if (node[parentIdName] == rootParentIdValue) {
        rootList.push(node);
      } else {
        nodeList.push(node);
      }
    });

    if (nodeList.length > 0 && rootList.length > 0) {
      childrenNodeAdd(rootList, nodeList);
      return rootList;
    } else if (rootList.length > 0) {
      throw new Error("没有对应的子节点集合");
    } else {
      throw new Error("没有对应的父类节点集合");
    }

    function childrenNodeAdd(rootNodeList, childrenList) {
      if (childrenList.length > 0) { 
        rootNodeList.forEach(function(rootNode) {
          rootNode["children"] = [];
          var childrenNodeList = childrenList.slice(0); 
          childrenList.forEach(function(childrenNode, childrenIndex) {
            if (parentIdName in childrenNode && rootNode[nodeIdName] == childrenNode[parentIdName]) {
              rootNode["children"].push(childrenNode);
              childrenNodeList.splice(childrenIndex, 1);
            }
          });
          childrenNodeAdd(rootNode["children"], childrenNodeList);
        });
      }
    }
    
  } else {
    throw new Error("格式不正确，无法转换");
  }
}

此函数可通过listToTree("0", "parentId", "id", sourceData)调用测试，sourceData为文章开头给出的二维数据结构举例。

下面简要介绍一下其中逻辑，第10行是简要验证一下入参数据的合法性，然后声明了rootList和nodeList两个变量。其中rootList为顶级根节点，nodeList为其他子节点集合，第14行到20行的循环便是为两个变量赋值，之后根据两个变量的值进一步判断数据的合法性。在验证之后调用childrenNodeAdd这个内部函数，此函数之后将会被递归调用，为每一个节点添加指定名称为“children”的子节点数组。两个入参分别是rootNodeList和childrenList，代表父节点集合，和其之后的所有子节点集合。在23行第一次调用时，传入的便是顶级根节点和其之后的所有子孙节点。下面看这段带有详细注解的代码片段：

function childrenNodeAdd(rootNodeList, childrenList) {
      if (childrenList.length > 0) { //  如果没有子节点了就结束递归
        //遍历父节点集合，在子节点中查找其自身的子节点，并添加到对应的子节点数组中
        rootNodeList.forEach(function(rootNode) {
          rootNode["children"] = [];
          var childrenNodeList = childrenList.slice(0); //复制一个子节点数据，用于存放剩余的子节点
          //遍历所有子节点
          childrenList.forEach(function(childrenNode, childrenIndex) {
            if (parentIdName in childrenNode && rootNode[nodeIdName] == childrenNode[parentIdName]) { //根节点的id 等于子节点的父类id
              rootNode["children"].push(childrenNode); //添加对应节点归为子节点
              childrenNodeList.splice(childrenIndex, 1);//在剩余子节点中剔除已经分配过的子节点
            }
          });
          childrenNodeAdd(rootNode["children"], childrenNodeList); //剩余子节点继续递归执行，每次递归一次就表示节点增加一级。
        });
      }
    }

树状数据结构 => 二维数据结构

/**
 * 将树状数据结构转换为二维数据结构
 * @param  {String} childrenName 树状结构中子节点名称
 * @param  {Array} treeData     树状结构数据
 * @return {Array}              转换后的通用二维结构数据
 */
function treeToList(childrenName, treeData) {
  var listData = [];
  transferTreeData(treeData);
  function transferTreeData (sourceData) {
     sourceData.forEach( function(node, nodeIndex) {
     if(node[childrenName].length > 0)
          transferTreeData(node[childrenName]);
      delete node[childrenName];
      listData.push(node);
     });
  }
  return listData;
}

此函数可通过treeToList("children", sourceData)调用测试，sourceData为文章开头给出的树状数据结构举例。这里的逻辑比较简单就不再赘述了。