(奖励1:节点可以排序，也可以不排序)

(bonus2:不需要第三方库，纯js)

(BONUS3:用户“Elias Rabl”说这是最高效的解决方案，见下面他的回答)

下面就是:

const createDataTree = dataset => {
  const hashTable = Object.create(null);
  dataset.forEach(aData => hashTable[aData.ID] = {...aData, childNodes: []});
  const dataTree = [];
  dataset.forEach(aData => {
    if(aData.parentID) hashTable[aData.parentID].childNodes.push(hashTable[aData.ID])
    else dataTree.push(hashTable[aData.ID])
  });
  return dataTree;
};

下面是一个测试，它可能会帮助你理解解决方案是如何工作的:

it('creates a correct shape of dataTree', () => {
  const dataSet = [{
    "ID": 1,
    "Phone": "(403) 125-2552",
    "City": "Coevorden",
    "Name": "Grady"
  }, {
    "ID": 2,
    "parentID": 1,
    "Phone": "(979) 486-1932",
    "City": "Chełm",
    "Name": "Scarlet"
  }];

  const expectedDataTree = [{
    "ID": 1,
    "Phone": "(403) 125-2552",
    "City": "Coevorden",
    "Name": "Grady",
    childNodes: [{
      "ID": 2,
      "parentID": 1,
      "Phone": "(979) 486-1932",
      "City": "Chełm",
      "Name": "Scarlet",
      childNodes : []
    }]
  }];

  expect(createDataTree(dataSet)).toEqual(expectedDataTree);
});

下面是Steven Harris的一个修改版本，它是普通的ES5，返回一个以id为键的对象，而不是返回顶层和子层的节点数组。

unflattenToObject = function(array, parent) {
  var tree = {};
  parent = typeof parent !== 'undefined' ? parent : {id: 0};

  var childrenArray = array.filter(function(child) {
    return child.parentid == parent.id;
  });

  if (childrenArray.length > 0) {
    var childrenObject = {};
    // Transform children into a hash/object keyed on token
    childrenArray.forEach(function(child) {
      childrenObject[child.id] = child;
    });
    if (parent.id == 0) {
      tree = childrenObject;
    } else {
      parent['children'] = childrenObject;
    }
    childrenArray.forEach(function(child) {
      unflattenToObject(array, child);
    })
  }

  return tree;
};

var arr = [
    {'id':1 ,'parentid': 0},
    {'id':2 ,'parentid': 1},
    {'id':3 ,'parentid': 1},
    {'id':4 ,'parentid': 2},
    {'id':5 ,'parentid': 0},
    {'id':6 ,'parentid': 0},
    {'id':7 ,'parentid': 4}
];
tree = unflattenToObject(arr);

ES6地图版本:

getTreeData = (items) => {
  if (items && items.length > 0) {
    const data = [];
    const map = {};
    items.map((item) => {
      const id = item.id; // custom id selector !!!
      if (!map.hasOwnProperty(id)) {
        // in case of duplicates
        map[id] = {
          ...item,
          children: [],
        };
      }
    });
    for (const id in map) {
      if (map.hasOwnProperty(id)) {
        let mappedElem = [];
        mappedElem = map[id];
        /// parentId : use custom id selector for parent
        if (
          mappedElem.parentId &&
          typeof map[mappedElem.parentId] !== "undefined"
        ) {
          map[mappedElem.parentId].children.push(mappedElem);
        } else {
          data.push(mappedElem);
        }
      }
    }
    return data;
  }
  return [];
};

/// use like this :

const treeData = getTreeData(flatList);

下面是我根据上面的答案创建的一个简单的帮助函数，为通天塔环境量身定制:

import { isEmpty } from 'lodash'

export default function unflattenEntities(entities, parent = {id: null}, tree = []) {

  let children = entities.filter( entity => entity.parent_id == parent.id)

  if (!isEmpty( children )) {
    if ( parent.id == null ) {
      tree = children
    } else {
      parent['children'] = children
    }
    children.map( child => unflattenEntities( entities, child ) )
  }

  return tree

}

我已经编写了一个测试脚本来评估用户shekhardtu(见答案)和FurkanO(见答案)提出的两种最通用的解决方案的性能(意味着输入不需要事先排序，代码不依赖于第三方库)。

http://playcode.io/316025?tabs=console&script.js&output

FurkanO的解决方案似乎是最快的。

/* ** performance test for https://stackoverflow.com/questions/18017869/build-tree-array-from-flat-array-in-javascript */ // Data Set (e.g. nested comments) var comments = [{ id: 1, parent_id: null }, { id: 2, parent_id: 1 }, { id: 3, parent_id: 4 }, { id: 4, parent_id: null }, { id: 5, parent_id: 4 }]; // add some random entries let maxParentId = 10000; for (let i=6; i<=maxParentId; i++) { let randVal = Math.floor((Math.random() * maxParentId) + 1); comments.push({ id: i, parent_id: (randVal % 200 === 0 ? null : randVal) }); } // solution from user "shekhardtu" (https://stackoverflow.com/a/55241491/5135171) const nest = (items, id = null, link = 'parent_id') => items .filter(item => item[link] === id) .map(item => ({ ...item, children: nest(items, item.id) })); ; // solution from user "FurkanO" (https://stackoverflow.com/a/40732240/5135171) const createDataTree = dataset => { let hashTable = Object.create(null) dataset.forEach( aData => hashTable[aData.id] = { ...aData, children : [] } ) let dataTree = [] dataset.forEach( aData => { if( aData.parent_id ) hashTable[aData.parent_id].children.push(hashTable[aData.id]) else dataTree.push(hashTable[aData.id]) } ) return dataTree }; /* ** lets evaluate the timing for both methods */ let t0 = performance.now(); let createDataTreeResult = createDataTree(comments); let t1 = performance.now(); console.log("Call to createDataTree took " + Math.floor(t1 - t0) + " milliseconds."); t0 = performance.now(); let nestResult = nest(comments); t1 = performance.now(); console.log("Call to nest took " + Math.floor(t1 - t0) + " milliseconds."); //console.log(nestResult); //console.log(createDataTreeResult); // bad, but simple way of comparing object equality console.log(JSON.stringify(nestResult)===JSON.stringify(createDataTreeResult));

更新2022

这是一个针对无序项的建议。该函数使用单个循环和哈希表，并收集所有带有id的项。如果找到根节点，则将该对象添加到结果数组中。

const getTree = (data, root) => { const t = {}; data.forEach(o => ((t[o.parentId] ??= {}).children ??= []).push(Object.assign(t[o.id] ??= {}, o))); return t[root].children; }, data = { People: [{ id: "12", parentId: "0", text: "Man", level: "1", children: null }, { id: "6", parentId: "12", text: "Boy", level: "2", children: null }, { id: "7", parentId: "12", text: "Other", level: "2", children: null }, { id: "9", parentId: "0", text: "Woman", level: "1", children: null }, { id: "11", parentId: "9", text: "Girl", level: "2", children: null }], Animals: [{ id: "5", parentId: "0", text: "Dog", level: "1", children: null }, { id: "8", parentId: "5", text: "Puppy", level: "2", children: null }, { id: "10", parentId: "13", text: "Cat", level: "1", children: null }, { id: "14", parentId: "13", text: "Kitten", level: "2", children: null }] }, result = Object.fromEntries(Object .entries(data) .map(([k, v]) => [k, getTree(v, '0')]) ); console.log(result); .as-console-wrapper { max-height: 100% !important; top: 0; }