数组元素可以以混乱的顺序排列

let array = [ { id: 1, data: 'something', parent_id: null, children: [] }, { id: 2, data: 'something', parent_id: 1, children: [] }, { id: 5, data: 'something', parent_id: 4, children: [] }, { id: 4, data: 'something', parent_id: 3, children: [] }, { id: 3, data: 'something', parent_id: null, children: [] }, { id: 6, data: 'something', parent_id: null, children: [] } ] function buildTree(array) { let tree = [] for (let i = 0; i < array.length; i++) { if (array[i].parent_id) { let parent = array.filter(elem => elem.id === array[i].parent_id).pop() parent.children.push(array[i]) } else { tree.push(array[i]) } } return tree } const tree = buildTree(array) console.log(tree); .as-console-wrapper { min-height: 100% }

这是我在一个react项目中使用的

// ListToTree.js
import _filter from 'lodash/filter';
import _map from 'lodash/map';

export default (arr, parentIdKey) => _map(_filter(arr, ar => !ar[parentIdKey]), ar => ({
  ...ar,
  children: _filter(arr, { [parentIdKey]: ar.id }),
}));

用法:

// somewhere.js
import ListToTree from '../Transforms/ListToTree';

const arr = [
   {
      "id":"Bci6XhCLZKPXZMUztm1R",
      "name":"Sith"
   },
   {
      "id":"C3D71CMmASiR6FfDPlEy",
      "name":"Luke",
      "parentCategoryId":"ltatOlEkHdVPf49ACCMc"
   },
   {
      "id":"aS8Ag1BQqxkO6iWBFnsf",
      "name":"Obi Wan",
      "parentCategoryId":"ltatOlEkHdVPf49ACCMc"
   },
   {
      "id":"ltatOlEkHdVPf49ACCMc",
      "name":"Jedi"
   },
   {
      "id":"pw3CNdNhnbuxhPar6nOP",
      "name":"Palpatine",
      "parentCategoryId":"Bci6XhCLZKPXZMUztm1R"
   }
];
const response = ListToTree(arr, 'parentCategoryId');

输出:

[
   {
      "id":"Bci6XhCLZKPXZMUztm1R",
      "name":"Sith",
      "children":[
         {
            "id":"pw3CNdNhnbuxhPar6nOP",
            "name":"Palpatine",
            "parentCategoryId":"Bci6XhCLZKPXZMUztm1R"
         }
      ]
   },
   {
      "id":"ltatOlEkHdVPf49ACCMc",
      "name":"Jedi",
      "children":[
         {
            "id":"C3D71CMmASiR6FfDPlEy",
            "name":"Luke",
            "parentCategoryId":"ltatOlEkHdVPf49ACCMc"
         },
         {
            "id":"aS8Ag1BQqxkO6iWBFnsf",
            "name":"Obi Wan",
            "parentCategoryId":"ltatOlEkHdVPf49ACCMc"
         }
      ]
   }
]```

如果使用地图查找，就有一个有效的解决方案。如果父母总是在他们的孩子之前，你可以合并两个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)，这对于大型数据集可能是一个问题。

我使用@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);

类似问题的答案:

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

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