在JavaScript中如何从一维数组中构建树数组？

Question

原始数据：
其中省略很多字段

const nodes = [
{OrganizeID:'2',ParentID:'0',name:'水果'},
{OrganizeID:'201',ParentID:'2',name:'瓜类'},
{OrganizeID:'202',ParentID:'2',name:'果类'},
{OrganizeID:'20101',ParentID:'201',name:'西瓜'},
{OrganizeID:'20202',ParentID:'202',name:'苹果'},
{OrganizeID:'2020201',ParentID:'20202',name:'苹果-1'},
{OrganizeID:'2020202',ParentID:'20202',name:'苹果-2'},

]

我的尝试：

nodes.forEach(o = >{
    const item = leve1.find(({
        OrganizeID
    }) = >{
         return OrganizeID == o.ParentID
    }) if (item) {
        if (item.children) {
            item.children.push(o)
        } else {
            item["children"] = [o]
        }
    }
})

我想要的：

[
   {
     label:"瓜类",
     value:"201",
     children:[
          {value:'20101',,label:'西瓜',...},
     ],
     ...
   },
   {
     label:"果类",
     value:"202",
     children:[
          {value:'20202',,label:'苹果',children:[
            ....
          ]
          },
     ],
     ...
   }
   
]

label,value,children是必须的，省略了很多字段

非常感谢您的帮助~

Answer 1

这个问题信息中其实有冗余信息，因为OrganizeID信息中已经包含了层级信息，如果原始数组以OrganizeID的长度排序过，则可以一次性的遍历构建出需求的树。
这是基于：

1. OrganizeID 长度为1 的是根节点
2. OrganizeID 长度为7 的为最末端页节点
3. OrganizeID 中间长度的 可能是末端页节点，也可能是有子节点的节点（分枝节点）
4. 除了根节点的OrganizeID为1位外（不存在父节点啦），其他节点的父节点的OrganizeID （临时标记为PID）可以依据当前节点的OrganizeID（临时标记为CID）计算出来，其计算公式为 PID=CID.substr(0,CID.length-2),而且可以依次递归查找到根（OrganizeID 为1位的情况），这样因为父节点肯定已经建立，所以可以直接插入。

不过题主要children属性为数组，其实在这里不够合理，如果还是Object属性，其实更方便查询使用，否则还需要对数组进行遍历查找。

一个参考实现:

const nodes = [
{OrganizeID:'2',ParentID:'0',name:'水果'},
{OrganizeID:'201',ParentID:'2',name:'瓜类'},
{OrganizeID:'202',ParentID:'2',name:'果类'},
{OrganizeID:'20101',ParentID:'201',name:'西瓜'},
{OrganizeID:'20202',ParentID:'202',name:'苹果'},
{OrganizeID:'2020201',ParentID:'20202',name:'苹果-1'},
{OrganizeID:'2020202',ParentID:'20202',name:'苹果-2'},

]
var getIdPath=function(inID){ 
// 以数组返回一个Id对应的路径层级，Arr[0]是对应的根，依次到最后是当前 Arr[length-1] 对应 inID
    let rt=[];
    rt.push(inID);
    let tmpStr=inID;
    let tmpL = tmpStr.length;
    while( tmpL>1){
        tmpStr=tmpStr.substr(0,tmpL-2);
        rt.push(tmpStr);
        tmpL=tmpStr.length;
    }
    rt.reverse(); 
    return rt;
}

var treeCreate=function(inArr,rootID){ 
// inArr 是已经排序过的数组，rootID是根节点以往对应的OrganizeID,比如这里是2
    let rtObj={};
    for(let i=0;i<inArr.length;i++){
       let tmpArr=getIdPath( inArr[i]["OrganizeID"] )
       let tmpL = tmpArr.length;
       if(tmpArr[0]==rootID){
           if( tmpL == 2 ){
           rtObj[ tmpArr[1] ] = {}
           rtObj[ tmpArr[1] ]["label"]= inArr[i]["name"]
           rtObj[ tmpArr[1] ]["value"]= inArr[i]["OrganizeID"]
           rtObj[ tmpArr[1] ]["children"]={};
           }
               if( tmpL == 3){
                   rtObj[ tmpArr[1] ]["children"][tmpArr[2]] = {}
           rtObj[ tmpArr[1] ]["children"][tmpArr[2]]["label"]= inArr[i]["name"]
           rtObj[ tmpArr[1] ]["children"][tmpArr[2]]["value"]= inArr[i]["OrganizeID"]
           rtObj[ tmpArr[1] ]["children"][tmpArr[2]]["children"]={};
               }
               if( tmpL == 4){
                   rtObj[ tmpArr[1] ]["children"][tmpArr[2]]["children"][tmpArr[3]] = {}
           rtObj[ tmpArr[1] ]["children"][tmpArr[2]]["children"][tmpArr[3]]["label"] = inArr[i]["name"]
           rtObj[ tmpArr[1] ]["children"][tmpArr[2]]["children"][tmpArr[3]]["value"] = inArr[i]["OrganizeID"]
               }
       }
    }
    return rtObj;
}
console.log( treeCreate(nodes,"2") );

Answer 2

var  nodes = [
{OrganizeID:'2',ParentID:'0',name:'水果'},
{OrganizeID:'201',ParentID:'2',name:'瓜类'},
{OrganizeID:'202',ParentID:'2',name:'果类'},
{OrganizeID:'20101',ParentID:'201',name:'西瓜'},
{OrganizeID:'20202',ParentID:'202',name:'苹果'},
{OrganizeID:'2020201',ParentID:'20202',name:'苹果-1'},
{OrganizeID:'2020202',ParentID:'20202',name:'苹果-2'},

];
var toTree=(nodes,OrganizeID)=>nodes.filter(({ParentID})=>ParentID==OrganizeID).map(({name,OrganizeID})=>({label:name,value:OrganizeID,children:toTree(nodes,OrganizeID)}));
toTree(nodes,"0")[0].children;
//结果
[
  {
    "label": "瓜类",
    "value": "201",
    "children": [
      {
        "label": "西瓜",
        "value": "20101",
        "children": []
      }
    ]
  },
  {
    "label": "果类",
    "value": "202",
    "children": [
      {
        "label": "苹果",
        "value": "20202",
        "children": [
          {
            "label": "苹果-1",
            "value": "2020201",
            "children": []
          },
          {
            "label": "苹果-2",
            "value": "2020202",
            "children": []
          }
        ]
      }
    ]
  }
]

---------以前回答-----------

var nodes = [
{OrganizeID:'2',ParentID:'0',name:'水果'},
{OrganizeID:'201',ParentID:'2',name:'瓜类'},
{OrganizeID:'202',ParentID:'2',name:'果类'},
{OrganizeID:'20101',ParentID:'201',name:'西瓜'},
{OrganizeID:'20202',ParentID:'202',name:'苹果'},
{OrganizeID:'2020201',ParentID:'20202',name:'苹果-1'},
{OrganizeID:'2020201',ParentID:'20202',name:'苹果-2'},

];
// ParentID 父id filter 首先过滤获取父节点 
// 然后通过遍历递归父节点获取子节点
var toTree=(nodes,ParentID)=>nodes.filter(node=>node.ParentID==ParentID).map(node=>(node.children=toTree(nodes,node.OrganizeID),node));
toTree(nodes,"0");

// 数组转树形结构，参数 pid 父id的属性名；id节点的属性名;child 生成子节点的属性名，val 顶级节点的值
var toTree=(nodes,{pid,id,child,val})=>nodes.filter(node=>node[pid]==val).map(node=>(val=node[id],node[child]=toTree(nodes,{pid,id,child,val}),node));
toTree(nodes,{pid:'ParentID',id:'OrganizeID',child:"children",val:"0"});

[
  {
    "OrganizeID": "2",
    "ParentID": "0",
    "name": "水果",
    "children": [
      {
        "OrganizeID": "201",
        "ParentID": "2",
        "name": "瓜类",
        "children": [
          {
            "OrganizeID": "20101",
            "ParentID": "201",
            "name": "西瓜",
            "children": []
          }
        ]
      },
      {
        "OrganizeID": "202",
        "ParentID": "2",
        "name": "果类",
        "children": [
          {
            "OrganizeID": "20202",
            "ParentID": "202",
            "name": "苹果",
            "children": [
              {
                "OrganizeID": "2020201",
                "ParentID": "20202",
                "name": "苹果-1",
                "children": []
              },
              {
                "OrganizeID": "2020201",
                "ParentID": "20202",
                "name": "苹果-2",
                "children": []
              }
            ]
          }
        ]
      }
    ]
  }
]

Answer 3

这是我构建完整树的写法：

function treeify(list, idAttr, parentAttr, childrenAttr) {
    if (!idAttr) idAttr = "OrganizeID";
    if (!parentAttr) parentAttr = "ParentID";
    if (!childrenAttr) childrenAttr = "children";
    var treeList = [];
    var lookup = {};
    list.forEach(function(obj) {
        obj.label = obj.OrganizeName; 
        obj.value = obj.OrganizeID ;
        lookup[obj[idAttr]] = obj;
    });
    list.forEach(function(obj) {
        if (obj[parentAttr] != "0") {
            if (lookup[obj[parentAttr]][childrenAttr]) {
                lookup[obj[parentAttr]][childrenAttr].push(obj);
            } else {
                lookup[obj[parentAttr]][childrenAttr] = [obj];
            }

        } else {
            treeList.push(obj);
        }
    });
    return treeList;
}

Answer 4

const nodes = [
    {OrganizeID:'2',ParentID:'0',name:'水果'},
    {OrganizeID:'201',ParentID:'2',name:'瓜类'},
    {OrganizeID:'202',ParentID:'2',name:'果类'},
    {OrganizeID:'20101',ParentID:'201',name:'西瓜'},
    {OrganizeID:'20202',ParentID:'202',name:'苹果'},
    {OrganizeID:'2020201',ParentID:'20202',name:'苹果-1'},
    {OrganizeID:'2020201',ParentID:'20202',name:'苹果-2'},
]
const nodeMaps = {
    "0": {
        childIDs: [],
        parentID: null,
        node: { name: "root", OrganizeID: "0" }
    }
}
nodes.forEach((node) => {
    const childIDs = []
    const parentID = node.ParentID
    nodeMaps[node.OrganizeID] = {
        parentID,
        childIDs,
        node
    }
})
nodes.forEach((node) => {
    const parentID = node.ParentID
    if(!parentID) return
    const organizeID = node.OrganizeID
    nodeMaps[parentID].childIDs.push(organizeID)
})

const getTreeByParentID = (pid) => {
    const pNode = nodeMaps[pid]
    const children = pNode.childIDs.map((id) => getTreeByParentID(id))

    return {
        label: pNode.node.name,
        value: pNode.node.OrganizeID,
        children
    }
}

const rootNodes = getTreeByParentID("0")
console.log(JSON.stringify(rootNodes))