类似问题的答案:

https://stackoverflow.com/a/61575152/7388356

更新

你可以使用ES6中引入的Map对象。基本上，你不再通过遍历数组来寻找父元素，你只需要从数组中通过父元素的id来获取父元素就像你在数组中通过索引来获取元素一样。

下面是一个简单的例子:

const 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
  }
];

function toTree(arr) {
  let arrMap = new Map(arr.map(item => [item.id, item]));
  let tree = [];

  for (let i = 0; i < arr.length; i++) {
    let item = arr[i];

    if (item.parentId !== "0") {
      let parentItem = arrMap.get(item.parentId);

      if (parentItem) {
        let { children } = parentItem;

        if (children) {
          parentItem.children.push(item);
        } else {
          parentItem.children = [item];
        }
      }
    } else {
      tree.push(item);
    }
  }

  return tree;
}

let tree = toTree(people);

console.log(tree);

我使用@FurkanO answer并创建了一个可以用于任何对象类型的泛型函数，我还用TypeScript写了这个函数，我更喜欢它，因为它有自动补全功能。

实现:

1. Javascript:

export const flatListToTree = (flatList, idPath, parentIdPath, childListPath, isParent) => {
  const rootParents = [];
  const map = {};
  for (const item of flatList) {
    if (!item[childListPath]) item[childListPath] = [];
    map[item[idPath]] = item;
  }
  for (const item of flatList) {
    const parentId = item[parentIdPath];
    if (isParent(item)) {
      rootParents.push(item);
    } else {
      const parentItem = map[parentId];
      parentItem[childListPath].push(item);
    }
  }
  return rootParents;
};

2. TypeScript:我假设“T”类型有一个属性的孩子列表，你可以改变“childListPath”是一个字符串而不是“keyof T”如果你有不同的用例。

export const flatListToTree = <T>(
  flatList: T[],
  idPath: keyof T,
  parentIdPath: keyof T,
  childListPath: keyof T,
  isParent: (t: T) => boolean,
) => {
  const rootParents: T[] = [];
  const map: any = {};
  for (const item of flatList) {
    if (!(item as any)[childListPath]) (item as any)[childListPath] = [];
    map[item[idPath]] = item;
  }
  for (const item of flatList) {
    const parentId = item[parentIdPath];
    if (isParent(item)) {
      rootParents.push(item);
    } else {
      const parentItem = map[parentId];
      parentItem[childListPath].push(item);
    }
  }
  return rootParents;
};

使用方法:

  const nodes = [
    { id: 2, pid: undefined, children: [] },
    { id: 3, pid: 2 },
    { id: 4, pid: 2 },
    { id: 5, pid: 4 },
    { id: 6, pid: 5 },
    { id: 7, pid: undefined },
    { id: 8, pid: 7 },
  ];
  
  const result = flatListToTree(nodes, "id", "pid", "children", node => node.pid === undefined);

我已经编写了一个测试脚本来评估用户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));

如果使用地图查找，就有一个有效的解决方案。如果父母总是在他们的孩子之前，你可以合并两个for循环。它支持多个根。它在悬垂的分支上给出一个错误，但可以修改为忽略它们。它不需要第三方库。就我所知，这是最快的解决方法。

function list_to_tree(list) { var map = {}, node, roots = [], i; for (i = 0; i < list.length; i += 1) { map[list[i].id] = i; // initialize the map list[i].children = []; // initialize the children } for (i = 0; i < list.length; i += 1) { node = list[i]; if (node.parentId !== "0") { // if you have dangling branches check that map[node.parentId] exists list[map[node.parentId]].children.push(node); } else { roots.push(node); } } return roots; } var entries = [{ "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 } ]; console.log(list_to_tree(entries));

如果你喜欢复杂性理论，这个解决方案是Θ(n log(n))。递归过滤器的解决方案是Θ(n^2)，这对于大型数据集可能是一个问题。

正如@Sander提到的，@Halcyon的答案假设一个预先排序的数组，下面的不是。(然而，它假设你已经加载了underscore.js -尽管它可以用香草javascript编写):

Code

// Example usage 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} ]; unflatten = function( array, parent, tree ){ tree = typeof tree !== 'undefined' ? tree : []; parent = typeof parent !== 'undefined' ? parent : { id: 0 }; var children = _.filter( array, function(child){ return child.parentid == parent.id; }); if( !_.isEmpty( children ) ){ if( parent.id == 0 ){ tree = children; }else{ parent['children'] = children } _.each( children, function( child ){ unflatten( array, child ) } ); } return tree; } tree = unflatten( arr ); document.body.innerHTML = "<pre>" + (JSON.stringify(tree, null, " ")) <script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.9.1/underscore-min.js"></script>

需求

它假设属性'id'和'parentid'分别表示id和父id。必须有父ID为0的元素，否则将返回一个空数组。孤儿元素及其后代“丢失”

http://jsfiddle.net/LkkwH/1/

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);