在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
有同样的问题，但我不能确定数据是否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; } }
