Construa uma matriz de tree a partir da matriz plana em javascript

Eu tenho um arquivo json complexo que eu tenho que lidar com javascript para torná-lo hierárquico, para depois construir uma tree. Cada input do json possui: id: um id único, parentId: o id do nível do nó pai (que é 0 se o nó é uma raiz da tree): o nível de profundidade na tree

Os dados do json já estão “ordenados”. Quero dizer que uma input terá acima de si um nó pai ou nó irmão, e em si um nó filho ou um nó irmão.

Entrada :

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

Produção esperada:

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

Existe uma solução eficiente se você usar uma pesquisa de mapa. Se os pais sempre vierem antes de seus filhos, você poderá unir os dois laços iniciais. Suporta múltiplas raízes. Ocorre um erro ao pendurar ramificações, mas pode ser modificado para ignorá-las. Não requer uma biblioteca de terceiros. É, até onde eu sei, a solução mais rápida.

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

Se você está na teoria da complexidade, esta solução é n (n log (n)). A solução de filtro recursivo é Θ (n ^ 2), o que pode ser um problema para grandes conjuntos de dados.

Como mencionado por @Sander, a resposta do @Halcyon supõe uma matriz pré-ordenada, o que não segue. (No entanto, supõe-se que você tenha carregado underscore.js – embora possa ser escrito em javascript de baunilha):

Código

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

Requisitos

Ele assume que as propriedades ‘id’ e ‘parentid’ indicam ID e ID pai respectivamente. Deve haver elementos com o ID pai 0, caso contrário, você recuperará um array vazio. Elementos órfãos e seus descendentes são “perdidos”

Exemplo de uso

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

Tive o mesmo problema, mas não pude ter certeza de que os dados foram classificados ou não . Eu não poderia usar uma biblioteca de terceiros, então isso é apenas Js vanilla; Os dados de input podem ser obtidos do exemplo de @ 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 Fiddle

Matriz plana para tree

uma function mais simples list-to-tree-lite

npm install list-to-tree-lite

listToTree(list)

fonte:

 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

Você pode lidar com essa questão com apenas duas linhas de codificação:

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

Teste on-line (consulte o console do navegador para a tree criada)

Requisitos:

1- Instale o lodash 4 (uma biblioteca Javascript para manipular objects e collections com methods de desempenho => como o Linq em c #)

2- Um flatArray como abaixo:

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

Graças ao Sr. Bakhshabadi

Boa sorte

Pode ser uma instalação útil de pacote para tree :

 bower install list-to-tree --save 

ou

 npm install list-to-tree --save 

Por exemplo, tem lista:

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

Use o pacote list-to-tree:

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

Resultado:

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

Uma maneira muito simples de realizar é

(BONUS 1: NODES MAIO ou NÃO PODEM SER ORDENADOS)

(BONUS2: NÃO É NECESSÁRIA BIBLIOTECA TERCEIRA, SIMPLES 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 } 

Aqui está o teste para isso, pode ajudar:

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

Aqui está uma function auxiliar simples que eu criei modelada após as respostas acima, adaptadas a um ambiente 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 } 

também faça isso com 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(); } 
 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; } } 

Aqui está uma versão modificada de Steven Harris, que é simples ES5 e retorna um object typescript no id em vez de retornar uma matriz de nós no nível superior e para os filhos.

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

Esta é uma proposta para itens não ordenados. Essa function funciona com um único loop e com uma tabela de hash e coleta todos os itens com seu id . Se um nó raiz for encontrado, o object será adicionado à matriz resultante.

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

Esta é uma versão modificada do que precede que funciona com vários itens de raiz, eu uso GUIDs para os meus ids e parentIds assim na interface do usuário que cria-los itens raiz de código duro para algo como 0000000-00000-00000-TREE-ROOT-ITEM

var tree = unflatten (registros, “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; } 

Eu gosto da solução pura JavaScript do WilliamLeung, mas às vezes você precisa fazer alterações no array existente para manter uma referência ao object.

 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/

Copiado da Internet http://jsfiddle.net/stywell/k9x2a3g6/

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

Você pode usar o pacote npm array-a-tree https://github.com/alferov/array-to-tree . Ele converte uma matriz simples de nós (com pointers para nós pai) em uma estrutura de dados aninhada.

Resolve um problema com a conversão de recuperados de um database de conjuntos de dados para uma estrutura de dados aninhada (isto é, tree de navegação).

Uso:

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