在javascript中从平面数组构build树数组

我有一个复杂的json文件,我必须使用javascript来处理它,以便稍后构build一个树。 json的每个条目都有:id:唯一标识,parentId:父节点的标识(如果节点是树的根,则为0)level:树中的深度级别

json数据已经“sorting”了。 我的意思是一个条目将有一个父节点或兄弟节点本身之上,并且在它自己之下是一个子节点或一个兄弟节点。

input:

{ "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 }, ] } 

预期产出:

 { "People": [ { "id": "12", "parentId": "0", "text": "Man", "level": "1", "children": [ { "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": { "id": "11", "parentId": "9", "text": "Girl", "level": "2", "children": null } } ], "Animals": [ { "id": "5", "parentId": "0", "text": "Dog", "level": "1", "children": { "id": "8", "parentId": "5", "text": "Puppy", "level": "2", "children": null } }, { "id": "10", "parentId": "13", "text": "Cat", "level": "1", "children": { "id": "14", "parentId": "13", "text": "Kitten", "level": "2", "children": null } } ] } 

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

 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" }, { /*...*/ } ]; console.log(list_to_tree(entries)); 

如果你进入复杂性理论,这个解决scheme是Θ(n log(n))。 recursion滤波器解决scheme是Θ(n ^ 2),这可能是大数据集的问题。

正如@Sander所提到的, @ Halcyon的答案假设了一个预先sorting的数组,下面不会。 (但它假设你已经加载了underscore.js – 虽然它可以写在香草的JavaScript):

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

要求

它假定属性“id”和“parentid”分别表示ID和父ID。 必须有父ID为0的元素,否则返回一个空数组。 孤儿和他们的后代是“迷失”

用法示例

 //Array to convert to tree structure. 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 = unflatten( arr ); 

的jsfiddle

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

有同样的问题,但我不能确定数据是否sorting 。 我不能使用第三方库,所以这只是香草Js; input数据可以从@ Stephen的例子中获得;

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

JS小提琴

平面arrays树

一个更简单的函数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; } 

的jsfiddle

这可能是有用的包列表到树的安装:

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

你可以用两行代码来处理这个问题:

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

在线testing (请参阅浏览器控制台了解所创build的树)

要求:

1-安装lodash 4(一个Javascript库,用于处理对象和集合的性能方法=>像C#中的Linq) Lodash

2-平面arrays如下:

  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先生

祝你好运

非常简单的方法来完成

(奖金1:节点或可能不会被订购)

(BONUS2:没有第三方图书馆,平原JS)

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

这是testing它,可能会有所帮助:

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

下面是一个简单的帮助函数,我根据上面的答案创build了模型,并根据Babel环境进行了定制:

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

这是一个无序项目的build议。 此函数使用一个循环和一个哈希表,并收集所有项目与他们的id 。 如果find根节点,则将该对象添加到结果数组中。

 function getTree(data, root) { var r = [], o = {}; data.forEach(function (a) { if (o[a.id] && o[a.id].children) { a.children = o[a.id].children; } o[a.id] = a; if (a.parentId === root) { r.push(a); } else { o[a.parentId] = o[a.parentId] || {}; o[a.parentId].children = o[a.parentId].children || []; o[a.parentId].children.push(a); } }); return r; } var 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 }] }, tree = Object.keys(data).reduce(function (r, k) { r[k] = getTree(data[k], '0'); return r; }, {}); console.log(tree); 
 .as-console-wrapper { max-height: 100% !important; top: 0; } 

这是上面的修改版本与多个根项目一起工作,我使用GUID为我的ids和parentIds,所以在UI中创build它们我硬编码根项目类似0000000-00000-00000-TREE-ROOT-ITEM

var tree = unflatten(logging,“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解决scheme,但是有时您需要对现有数组进行更改以保持对象的引用。

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

Exapmle: https ://jsfiddle.net/kqw1qsf0/17/

 var data = [{"country":"india","gender":"male","type":"lower","class":"X"}, {"country":"china","gender":"female","type":"upper"}, {"country":"india","gender":"female","type":"lower"}, {"country":"india","gender":"female","type":"upper"}]; var seq = ["country","type","gender","class"]; var treeData = createHieArr(data,seq); console.log(treeData) function createHieArr(data,seq){ var hieObj = createHieobj(data,seq,0), hieArr = convertToHieArr(hieObj,"Top Level"); return [{"name": "Top Level", "parent": "null", "children" : hieArr}] function convertToHieArr(eachObj,parent){ var arr = []; for(var i in eachObj){ arr.push({"name":i,"parent":parent,"children":convertToHieArr(eachObj[i],i)}) } return arr; } function createHieobj(data,seq,ind){ var s = seq[ind]; if(s == undefined){ return []; } var childObj = {}; for(var ele of data){ if(ele[s] != undefined){ if(childObj[ele[s]] == undefined){ childObj[ele[s]] = []; } childObj[ele[s]].push(ele); } } ind = ind+1; for(var ch in childObj){ childObj[ch] = createHieobj(childObj[ch],seq,ind) } return childObj; } }