如果使用地图查找，就有一个有效的解决方案。如果父母总是在他们的孩子之前，你可以合并两个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编写):

代码

// 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>

Requirements

It assumes the properties 'id' and 'parentid' indicate ID and parent ID respectively. There must be elements with parent ID 0, otherwise you get an empty array back. Orphaned elements and their descendants are 'lost'

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

有同样的问题，但我不能确定数据是排序与否。我不能使用第三方库，所以这只是香草Js;输入数据可以从@Stephen的例子中获取;

 var arr = [
{'id':1 ,'parentid' : 0},
{'id':4 ,'parentid' : 2},
{'id':3 ,'parentid' : 1},
{'id':5 ,'parentid' : 0},
{'id':6 ,'parentid' : 0},
{'id':2 ,'parentid' : 1},
{'id':7 ,'parentid' : 4},
{'id':8 ,'parentid' : 1}
];
function unflatten(arr) {
var tree = [],
mappedArr = {},
arrElem,
mappedElem;


// First map the nodes of the array to an object -> create a hash table.
for(var i = 0, len = arr.length; i < len; i++) {
arrElem = arr[i];
mappedArr[arrElem.id] = arrElem;
mappedArr[arrElem.id]['children'] = [];
}




for (var id in mappedArr) {
if (mappedArr.hasOwnProperty(id)) {
mappedElem = mappedArr[id];
// If the element is not at the root level, add it to its parent array of children.
if (mappedElem.parentid) {
mappedArr[mappedElem['parentid']]['children'].push(mappedElem);
}
// If the element is at the root level, add it to first level elements array.
else {
tree.push(mappedElem);
}
}
}
return tree;
}


var tree = unflatten(arr);
document.body.innerHTML = "<pre>" + (JSON.stringify(tree, null, " "))

JS小提琴

平面数组到树

它可能是有用的包列表到树 安装:< / p >

bower install list-to-tree --save

或

npm install list-to-tree --save

例如，有列表:

var list = [
{
id: 1,
parent: 0
}, {
id: 2,
parent: 1
}, {
id: 3,
parent: 1
}, {
id: 4,
parent: 2
}, {
id: 5,
parent: 2
}, {
id: 6,
parent: 0
}, {
id: 7,
parent: 0
}, {
id: 8,
parent: 7
}, {
id: 9,
parent: 8
}, {
id: 10,
parent: 0
}
];

使用包列表到树:

var ltt = new LTT(list, {
key_id: 'id',
key_parent: 'parent'
});
var tree = ltt.GetTree();

结果:

[{
"id": 1,
"parent": 0,
"child": [
{
"id": 2,
"parent": 1,
"child": [
{
"id": 4,
"parent": 2
}, {
"id": 5, "parent": 2
}
]
},
{
"id": 3,
"parent": 1
}
]
}, {
"id": 6,
"parent": 0
}, {
"id": 7,
"parent": 0,
"child": [
{
"id": 8,
"parent": 7,
"child": [
{
"id": 9,
"parent": 8
}
]
}
]
}, {
"id": 10,
"parent": 0
}];

一个更简单的函数list-to-tree-lite

npm install list-to-tree-lite

listToTree(list)

来源:

function listToTree(data, options) {
options = options || {};
var ID_KEY = options.idKey || 'id';
var PARENT_KEY = options.parentKey || 'parent';
var CHILDREN_KEY = options.childrenKey || 'children';


var tree = [],
childrenOf = {};
var item, id, parentId;


for (var i = 0, length = data.length; i < length; i++) {
item = data[i];
id = item[ID_KEY];
parentId = item[PARENT_KEY] || 0;
// every item may have children
childrenOf[id] = childrenOf[id] || [];
// init its children
item[CHILDREN_KEY] = childrenOf[id];
if (parentId != 0) {
// init its parent's children object
childrenOf[parentId] = childrenOf[parentId] || [];
// push it into its parent's children object
childrenOf[parentId].push(item);
} else {
tree.push(item);
}
};


return tree;
}

< a href = " https://jsfiddle.net/kqw1qsf0/1/ " > jsfiddle < / >

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

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


}

也可以使用lodashjs(v4.x)

function buildTree(arr){
var a=_.keyBy(arr, 'id')
return _
.chain(arr)
.groupBy('parentId')
.forEach(function(v,k){
k!='0' && (a[k].children=(a[k].children||[]).concat(v));
})
.result('0')
.value();
}

下面是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);

(奖励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);
});

更新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; }

这是上面的一个修改版本，适用于多个根项，我使用guid为我的id和parentid，所以在创建它们的UI中，我硬编码根项为0000000-00000-00000-TREE-ROOT-ITEM

var树= unflatten(记录，" tree - root - item ");

function unflatten(records, rootCategoryId, parent, tree){
if(!_.isArray(tree)){
tree = [];
_.each(records, function(rec){
if(rec.parentId.indexOf(rootCategoryId)>=0){        // change this line to compare a root id
//if(rec.parentId == 0 || rec.parentId == null){    // example for 0 or null
var tmp = angular.copy(rec);
tmp.children = _.filter(records, function(r){
return r.parentId == tmp.id;
});
tree.push(tmp);
//console.log(tree);
_.each(tmp.children, function(child){
return unflatten(records, rootCategoryId, child, tree);
});
}
});
}
else{
if(parent){
parent.children = _.filter(records, function(r){
return r.parentId == parent.id;
});
_.each(parent.children, function(child){
return unflatten(records, rootCategoryId, child, tree);
});
}
}
return tree;
}

我喜欢@WilliamLeung的纯JavaScript解决方案，但有时你需要在现有数组中进行更改，以保持对对象的引用。

function listToTree(data, options) {
options = options || {};
var ID_KEY = options.idKey || 'id';
var PARENT_KEY = options.parentKey || 'parent';
var CHILDREN_KEY = options.childrenKey || 'children';


var item, id, parentId;
var map = {};
for(var i = 0; i < data.length; i++ ) { // make cache
if(data[i][ID_KEY]){
map[data[i][ID_KEY]] = data[i];
data[i][CHILDREN_KEY] = [];
}
}
for (var i = 0; i < data.length; i++) {
if(data[i][PARENT_KEY]) { // is a child
if(map[data[i][PARENT_KEY]]) // for dirty data
{
map[data[i][PARENT_KEY]][CHILDREN_KEY].push(data[i]); // add child to parent
data.splice( i, 1 ); // remove from root
i--; // iterator correction
} else {
data[i][PARENT_KEY] = 0; // clean dirty data
}
}
};
return data;
}

你可以用两行代码来解决这个问题:

_(flatArray).forEach(f=>
{f.nodes=_(flatArray).filter(g=>g.parentId==f.id).value();});


var resultArray=_(flatArray).filter(f=>f.parentId==null).value();

在线测试(查看浏览器控制台以获得创建的树)

要求:

1-安装lodash 4(一个Javascript库，用于操作对象和集合，使用性能方法=>，就像c#中的Linq) Lodash

2-如下所示的flatArray:

    var flatArray=
[{
id:1,parentId:null,text:"parent1",nodes:[]
}
,{
id:2,parentId:null,text:"parent2",nodes:[]
}
,
{
id:3,parentId:1,text:"childId3Parent1",nodes:[]
}
,
{
id:4,parentId:1,text:"childId4Parent1",nodes:[]
}
,
{
id:5,parentId:2,text:"childId5Parent2",nodes:[]
}
,
{
id:6,parentId:2,text:"childId6Parent2",nodes:[]
}
,
{
id:7,parentId:3,text:"childId7Parent3",nodes:[]
}
,
{
id:8,parentId:5,text:"childId8Parent5",nodes:[]
}];

谢谢Bakhshabadi先生

祝你好运

从互联网复制 http://jsfiddle.net/stywell/k9x2a3g6/ < / p >

    function list2tree(data, opt) {
opt = opt || {};
var KEY_ID = opt.key_id || 'ID';
var KEY_PARENT = opt.key_parent || 'FatherID';
var KEY_CHILD = opt.key_child || 'children';
var EMPTY_CHILDREN = opt.empty_children;
var ROOT_ID = opt.root_id || 0;
var MAP = opt.map || {};
function getNode(id) {
var node = []
for (var i = 0; i < data.length; i++) {
if (data[i][KEY_PARENT] == id) {
for (var k in MAP) {
data[i][k] = data[i][MAP[k]];
}
if (getNode(data[i][KEY_ID]) !== undefined) {
data[i][KEY_CHILD] = getNode(data[i][KEY_ID]);
} else {
if (EMPTY_CHILDREN === null) {
data[i][KEY_CHILD] = null;
} else if (JSON.stringify(EMPTY_CHILDREN) === '[]') {
data[i][KEY_CHILD] = [];
}
}
node.push(data[i]);
}
}
if (node.length == 0) {
return;
} else {
return node;
}
}
return getNode(ROOT_ID)
}


var opt = {
"key_id": "ID",              //节点的ID
"key_parent": "FatherID",    //节点的父级ID
"key_child": "children",     //子节点的名称
"empty_children": [],        //子节点为空时,填充的值  //这个参数为空时,没有子元素的元素不带key_child属性;还可以为null或者[],同理
"root_id": 0,                //根节点的父级ID
"map": {                     //在节点内映射一些值  //对象的键是节点的新属性; 对象的值是节点的老属性,会赋值给新属性
"value": "ID",
"label": "TypeName",
}
};

解决了从数据库数据集检索到嵌套数据结构(即导航树)的转换问题。

用法:

var arrayToTree = require('array-to-tree');


var dataOne = [
{
id: 1,
name: 'Portfolio',
parent_id: undefined
},
{
id: 2,
name: 'Web Development',
parent_id: 1
},
{
id: 3,
name: 'Recent Works',
parent_id: 2
},
{
id: 4,
name: 'About Me',
parent_id: undefined
}
];


arrayToTree(dataOne);


/*
* Output:
*
* Portfolio
*   Web Development
*     Recent Works
* About Me
*/

1. 没有第三方库
2. 不需要预先排序数组
3. 你可以得到树的任何部分

试试这个

function getUnflatten(arr,parentid){
let output = []
for(const obj of arr){
if(obj.parentid == parentid)


let children = getUnflatten(arr,obj.id)


if(children.length){
obj.children = children
}
output.push(obj)
}
}


return output
}

在Jsfiddle上测试

这是一个旧线程，但我认为更新永远不会伤害，与ES6你可以做到:

const data = [{
id: 1,
parent_id: 0
}, {
id: 2,
parent_id: 1
}, {
id: 3,
parent_id: 1
}, {
id: 4,
parent_id: 2
}, {
id: 5,
parent_id: 4
}, {
id: 8,
parent_id: 7
}, {
id: 9,
parent_id: 8
}, {
id: 10,
parent_id: 9
}];


const arrayToTree = (items=[], id = null, link = 'parent_id') => items.filter(item => id==null ? !items.some(ele=>ele.id===item[link]) : item[link] === id ).map(item => ({ ...item, children: arrayToTree(items, item.id) }))
const temp1=arrayToTree(data)
console.log(temp1)


const treeToArray = (items=[], key = 'children') => items.reduce((acc, curr) => [...acc, ...treeToArray(curr[key])].map(({ [`${key}`]: child, ...ele }) => ele), items);
const temp2=treeToArray(temp1)


console.log(temp2)

希望它能帮助到别人

使用ES6方法。工作很有魅力

// Data Set
// One top level comment
const comments = [{
id: 1,
parent_id: null
}, {
id: 2,
parent_id: 1
}, {
id: 3,
parent_id: 1
}, {
id: 4,
parent_id: 2
}, {
id: 5,
parent_id: 4
}];


const nest = (items, id = null, link = 'parent_id') =>
items
.filter(item => item[link] === id)
.map(item => ({ ...item, children: nest(items, item.id) }));


console.log(
nest(comments)
)

这是我在一个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"
}
]
}
]```

你可以从Github在这里或NPM中使用这个“treeify”包。

安装:

$ npm install --save-dev treeify-js

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

我有类似的问题，几天前必须从平面数组显示文件夹树。我在TypeScript中没有看到任何解决方案，所以我希望它会有帮助。

在我的情况下，主父只有一个，rawData数组也不必排序。解决方案基于准备临时对象 {parentId: [child1, child2, ...] } < / p >

示例原始数据

const flatData: any[] = Folder.ofCollection([
{id: '1', title: 'some title' },
{id: '2', title: 'some title', parentId: 1 },
{id: '3', title: 'some title', parentId: 7 },
{id: '4', title: 'some title', parentId: 1 },
{id: '5', title: 'some title', parentId: 2 },
{id: '6', title: 'some title', parentId: 5 },
{id: '7', title: 'some title', parentId: 5 },


]);

文件夹的定义

export default class Folder {
public static of(data: any): Folder {
return new Folder(data);
}


public static ofCollection(objects: any[] = []): Folder[] {
return objects.map((obj) => new Folder(obj));
}


public id: string;
public parentId: string | null;
public title: string;
public children: Folder[];


constructor(data: any = {}) {
this.id = data.id;
this.parentId = data.parentId || null;
this.title = data.title;
this.children = data.children || [];
}
}

解决方案:返回扁平参数的树结构的函数

    public getTree(flatData: any[]): Folder[] {
const addChildren = (item: Folder) => {
item.children = tempChild[item.id] || [];
if (item.children.length) {
item.children.forEach((child: Folder) => {
addChildren(child);
});
}
};


const tempChild: any = {};
flatData.forEach((item: Folder) => {
const parentId = item.parentId || 0;
Array.isArray(tempChild[parentId]) ? tempChild[parentId].push(item) : (tempChild[parentId] = [item]);
});


const tree: Folder[] = tempChild[0];
tree.forEach((base: Folder) => {
addChildren(base);
});
return tree;
}

我的typescript解决方案，可能对你有帮助:

type ITreeItem<T> = T & {
children: ITreeItem<T>[],
};


type IItemKey = string | number;


function createTree<T>(
flatList: T[],
idKey: IItemKey,
parentKey: IItemKey,
): ITreeItem<T>[] {
const tree: ITreeItem<T>[] = [];


// hash table.
const mappedArr = {};
flatList.forEach(el => {
const elId: IItemKey = el[idKey];


mappedArr[elId] = el;
mappedArr[elId].children = [];
});


// also you can use Object.values(mappedArr).forEach(...
// but if you have element which was nested more than one time
// you should iterate flatList again:
flatList.forEach((elem: ITreeItem<T>) => {
const mappedElem = mappedArr[elem[idKey]];


if (elem[parentKey]) {
mappedArr[elem[parentKey]].children.push(elem);
} else {
tree.push(mappedElem);
}
});


return tree;
}

用法示例:

createTree(yourListData, 'id', 'parentId');

我根据@Halcyon的答案写了一个ES6版本

const array = [
{
id: '12',
parentId: '0',
text: 'one-1'
},
{
id: '6',
parentId: '12',
text: 'one-1-6'
},
{
id: '7',
parentId: '12',
text: 'one-1-7'
},


{
id: '9',
parentId: '0',
text: 'one-2'
},
{
id: '11',
parentId: '9',
text: 'one-2-11'
}
];


// Prevent changes to the original data
const arrayCopy = array.map(item => ({ ...item }));


const listToTree = list => {
const map = {};
const roots = [];


list.forEach((v, i) => {
map[v.id] = i;
list[i].children = [];
});


list.forEach(v => (v.parentId !== '0' ? list[map[v.parentId]].children.push(v) : roots.push(v)));


return roots;
};


console.log(listToTree(arrayCopy));

该算法的原理是利用“map”建立索引关系。通过“parentId”可以很容易地在列表中找到“item”，并为每个“item”添加“children”，因为“list”是一个引用关系，所以“roots”将与整个树建立关系。

将节点数组转换为树

ES6函数将节点数组(与父ID相关)-转换为树结构:

/**
* Convert nodes list related by parent ID - to tree.
* @syntax getTree(nodesArray [, rootID [, propertyName]])
*
* @param {Array} arr   Array of nodes
* @param {integer} id  Defaults to 0
* @param {string} p    Property name. Defaults to "parent_id"
* @returns {Object}    Nodes tree
*/


const getTree = (arr, p = "parent_id") => arr.reduce((o, n) => {


if (!o[n.id]) o[n.id] = {};
if (!o[n[p]]) o[n[p]] = {};
if (!o[n[p]].nodes) o[n[p]].nodes= [];
if (o[n.id].nodes) n.nodes= o[n.id].nodes;


o[n[p]].nodes.push(n);
o[n.id] = n;


return o;
}, {});

从节点树生成HTML列表

有了我们的树，这里有一个递归函数来构建UL > LI元素:

/**
* Convert Tree structure to UL>LI and append to Element
* @syntax getTree(treeArray [, TargetElement [, onLICreatedCallback ]])
*
* @param {Array} tree Tree array of nodes
* @param {Element} el HTMLElement to insert into
* @param {function} cb Callback function called on every LI creation
*/


const treeToHTML = (tree, el, cb) => el.append(tree.reduce((ul, n) => {
const li = document.createElement('li');


if (cb) cb.call(li, n);
if (n.nodes?.length) treeToHTML(n.nodes, li, cb);


ul.append(li);
return ul;
}, document.createElement('ul')));

演示时间

下面是一个使用上述两个函数的线性节点数组的例子:

const getTree = (arr, p = "parent_id") => arr.reduce((o, n) => {
if (!o[n.id]) o[n.id] = {};
if (!o[n[p]]) o[n[p]] = {};
if (!o[n[p]].nodes) o[n[p]].nodes = [];
if (o[n.id].nodes) n.nodes = o[n.id].nodes;
o[n[p]].nodes.push(n);
o[n.id] = n;
return o;
}, {});




const treeToHTML = (tree, el, cb) => el.append(tree.reduce((ul, n) => {
const li = document.createElement('li');
if (cb) cb.call(li, n);
if (n.nodes?.length) treeToHTML(n.nodes, li, cb);
ul.append(li);
return ul;
}, document.createElement('ul')));




// DEMO TIME:


const nodesList = [
{id: 10,  parent_id: 4,  text: "Item 10"}, // PS: Order does not matters
{id: 1,   parent_id: 0,  text: "Item 1"},
{id: 4,   parent_id: 0,  text: "Item 4"},
{id: 3,   parent_id: 5,  text: "Item 3"},
{id: 5,   parent_id: 4,  text: "Item 5"},
{id: 2,   parent_id: 1,  text: "Item 2"},
];
const myTree = getTree(nodesList)[0].nodes; // Get nodes of Root (0)


treeToHTML(myTree, document.querySelector("#tree"), function(node) {
this.textContent = `(${node.parent_id} ${node.id}) ${node.text}`;
this._node = node;
this.addEventListener('click', clickHandler);
});


function clickHandler(ev) {
if (ev.target !== this) return;
console.clear();
console.log(this._node.id);
};

<div id="tree"></div>

类似问题的答案:

https://stackoverflow.com/a/61575152/7388356 < a href = " 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的回答，我创建了另一个不改变原始数据的版本(如请求的@Dac0d3r)。我真的很喜欢@shekhardtu的回答，但意识到它必须多次过滤数据。我认为一个解决方案可以使用FurkanO的答案，首先复制数据。我在jsperf中尝试了我的版本，结果很不幸(非常)暗淡…看来公认的答案真的很好!我的版本是相当可配置和故障安全，所以我分享给你们的家伙;以下是我的观点:

function unflat(data, options = {}) {
const { id, parentId, childrenKey } = {
id: "id",
parentId: "parentId",
childrenKey: "children",
...options
};
const copiesById = data.reduce(
(copies, datum) => ((copies[datum[id]] = datum) && copies),
{}
);
return Object.values(copiesById).reduce(
(root, datum) => {
if ( datum[parentId] && copiesById[datum[parentId]] ) {
copiesById[datum[parentId]][childrenKey] = [ ...copiesById[datum[parentId]][childrenKey], datum ];
} else {
root = [ ...root, datum ];
}
return root
}, []
);
}


const data = [
{
"account": "10",
"name": "Konto 10",
"parentAccount": null
},{
"account": "1010",
"name": "Konto 1010",
"parentAccount": "10"
},{
"account": "10101",
"name": "Konto 10101",
"parentAccount": "1010"
},{
"account": "10102",
"name": "Konto 10102",
"parentAccount": "1010"
},{
"account": "10103",
"name": "Konto 10103",
"parentAccount": "1010"
},{
"account": "20",
"name": "Konto 20",
"parentAccount": null
},{
"account": "2020",
"name": "Konto 2020",
"parentAccount": "20"
},{
"account": "20201",
"name": "Konto 20201",
"parentAccount": "2020"
},{
"account": "20202",
"name": "Konto 20202",
"parentAccount": "2020"
}
];


const options = {
id: "account",
parentId: "parentAccount",
childrenKey: "children"
};


console.log(
"Hierarchical tree",
unflat(data, options)
);

通过options参数，可以配置将哪个属性用作id或父id。如果有人想要"childNodes": []或其他东西，也可以配置children属性的名称。

OP可以简单地使用默认选项:

input.People = unflat(input.People);

如果父对象id为假值(null， undefined或其他假值)或父对象不存在，则认为该对象为根节点。

我的解决方案:

• 允许双向映射(根到叶，叶到根)
• 返回所有节点、根节点和叶节点
• 一次数据传递和非常快的性能
• 香草Javascript

/**
*
* @param data items array
* @param idKey item's id key (e.g., item.id)
* @param parentIdKey item's key that points to parent (e.g., item.parentId)
* @param noParentValue item's parent value when root (e.g., item.parentId === noParentValue => item is root)
* @param bidirectional should parent reference be added
*/
function flatToTree(data, idKey, parentIdKey, noParentValue = null, bidirectional = true) {
const nodes = {}, roots = {}, leaves = {};


// iterate over all data items
for (const i of data) {


// add item as a node and possibly as a leaf
if (nodes[i[idKey]]) { // already seen this item when child was found first
// add all of the item's data and found children
nodes[i[idKey]] = Object.assign(nodes[i[idKey]], i);
} else { // never seen this item
// add to the nodes map
nodes[i[idKey]] = Object.assign({ $children: []}, i);
// assume it's a leaf for now
leaves[i[idKey]] = nodes[i[idKey]];
}


// put the item as a child in parent item and possibly as a root
if (i[parentIdKey] !== noParentValue) { // item has a parent
if (nodes[i[parentIdKey]]) { // parent already exist as a node
// add as a child
(nodes[i[parentIdKey]].$children || []).push( nodes[i[idKey]] );
} else { // parent wasn't seen yet
// add a "dummy" parent to the nodes map and put the item as its child
nodes[i[parentIdKey]] = { $children: [ nodes[i[idKey]] ] };
}
if (bidirectional) {
// link to the parent
nodes[i[idKey]].$parent = nodes[i[parentIdKey]];
}
// item is definitely not a leaf
delete leaves[i[parentIdKey]];
} else { // this is a root item
roots[i[idKey]] = nodes[i[idKey]];
}
}
return {roots, nodes, leaves};
}

使用的例子:

const data = [{id: 2, parentId: 0}, {id: 1, parentId: 2} /*, ... */];
const { nodes, roots, leaves } = flatToTree(data, 'id', 'parentId', 0);

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

以防有家长需要。参考id 2，它有多个父元素

  const dataSet = [{
"ID": 1,
"Phone": "(403) 125-2552",
"City": "Coevorden",
"Name": "Grady"
},
{"ID": 2,
"Phone": "(403) 125-2552",
"City": "Coevorden",
"Name": "Grady"
},
{
"ID": 3,
"parentID": [1,2],
"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,3],
"Phone":"(979) 486-1932",
"City":"Chełm",
"Name":"Scarlet",
"childNodes":[]
}]
},
{
"ID":3,
"parentID":[],
"Phone":"(403) 125-2552",
"City":"Coevorden",
"Name":"Grady",
"childNodes":[
{
"ID":2,
"parentID":[1,3],
"Phone":"(979) 486-1932",
"City":"Chełm",
"Name":"Scarlet",
"childNodes":[]
}
]
}
];
      

      

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

});
return dataTree;
};
    

window.alert(JSON.stringify(createDataTree(dataSet)));

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

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% }

经过多次尝试，我得出了这个结论:

const arrayToTree = (arr, parent = 0) => arr .filter(item => item.parent === parent).map(child => ({ ...child, children: arrayToTree(arr, child.index) }));


   

const entries = [
{
index: 1,
parent: 0
},
{
index: 2,
parent: 1
},
{
index: 3,
parent: 2
},
{
index: 4,
parent: 2
},
{
index: 5,
parent: 4
},
{
index: 6,
parent: 5
},
{
index: 7,
parent: 6
},
{
index: 8,
parent: 7
},
{
index: 9,
parent: 8
},
{
index: 10,
parent: 9
},
{
index: 11,
parent: 7
},
{
index: 13,
parent: 11
},
{
index: 12,
parent: 0
}
];


const arrayToTree = (arr, parent = 0) => arr .filter(item => item.parent === parent) .map(child => ({ ...child, children: arrayToTree(arr, child.index) })); console.log(arrayToTree(entries));

我使用@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. 打字稿:我假定&;t &;type有一个children List的属性，你可以把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);