tipos - Construye una matriz de árbol de una matriz plana en JavaScript

programas en javascript resueltos

Question

Tengo un archivo json complejo que tengo que manejar con javascript para hacerlo jerárquico, para luego construir un árbol. Cada entrada de json tiene: id: un id único, parentId: el id del nodo padre (que es 0 si el nodo es una raíz del árbol) nivel: el nivel de profundidad en el árbol

Los datos json ya están "ordenados". Quiero decir que una entrada tendrá sobre sí misma un nodo padre o nodo hermano, y bajo él un nodo hijo o un nodo hermano.

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

Rendimiento esperado :

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

    ]
}

Answer 1

Aquí hay una función de ayuda sencilla que creé modelada después de las respuestas anteriores, adaptada a un entorno de 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

}

Answer 2

Aquí hay una versión modificada de Steven Harris que es simple ES5 y devuelve un objeto introducido en la identificación en lugar de devolver una matriz de nodos en el nivel superior y para los niños.

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

Answer 3

Como se menciona en @Sander, la respuesta de @ Halcyon asume una matriz preordenada, la siguiente no. (Sin embargo, asume que ha cargado underscore.js, aunque podría escribirse en vainilla javascript):

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

Asume que las propiedades ''id'' y ''parentid'' indican ID e ID principal respectivamente. Debe haber elementos con ID padre 0, de lo contrario, obtendrá una matriz vacía de nuevo. Los elementos huérfanos y sus descendientes están "perdidos"

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

Answer 4

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

Answer 5

Esta es una propuesta para artículos desordenados. Esta función funciona con un solo bucle y con una tabla hash y recopila todos los elementos con su id . Si se encuentra un nodo raíz, el objeto se agrega a la matriz de resultados.

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

Answer 6

Esta es una versión modificada de lo anterior que funciona con varios elementos raíz, utilizo GUID para mis IDs y parentIds, así que en la UI que los crea, codigo los elementos de raíz en 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;
}

Answer 7

Existe una solución eficiente si usa una búsqueda de mapa. Si los padres siempre vienen antes que sus hijos, puedes fusionar los dos bucles for-loop. Es compatible con múltiples raíces. Da un error en ramas colgantes, pero se puede modificar para ignorarlas. No requiere una biblioteca de terceros. Es, hasta donde puedo decir, la solución más 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));

Si te interesa la teoría de la complejidad, esta solución es Θ (n log (n)). La solución de filtro recursivo es Θ (n ^ 2) que puede ser un problema para grandes conjuntos de datos.

Answer 8

La forma más sencilla de lograr es

(BONUS1: NODES PUEDEN O NO PEDIRSE)

(BONUS2: NO SE NECESITA UNA BIBLIOTECA DE FIESTA 3RD, JS SIMPLE)

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
}

Aquí está la prueba, podría ayudar:

it(''creates a correct shape of dataTree'', () => {

    let dataSet = [
        {
            "ID": 1,
            "Phone": "[phone]",
            "City": "Coevorden",
            "Name": "Grady"
        },
        {
            "ID": 2,
            "parentID": 1,
            "Phone": "[phone]",
            "City": "Chełm",
            "Name": "Scarlet"
        }
    ]

    let expectedDataTree = [ 
    {
            "ID": 1,
            "Phone": "[phone]",
            "City": "Coevorden",
            "Name": "Grady",
            childNodes : [
                {
                    "ID": 2,
                    "parentID": 1,
                    "Phone": "[phone]",
                    "City": "Chełm",
                    "Name": "Scarlet",
                    childNodes : []
                }
            ]
    } 
    ]

  expect( createDataTree(dataSet) ).toEqual(expectedDataTree)
});

Answer 9

Me gusta la solución de JavaScript pura de @WilliamLeung, pero a veces es necesario realizar cambios en la matriz existente para mantener una referencia al objeto.

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/

Answer 10

Puede ser una útil instalación de paquete list-to-tree :

bower install list-to-tree --save

o

npm install list-to-tree --save

Por ejemplo, tiene 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 el paquete 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
}];

Answer 11

Tenía el mismo problema, pero no podía estar seguro de que los datos estuvieran clasificados o no . No pude usar una biblioteca de terceros, así que esto es solo Js vainilla; Los datos de entrada se pueden tomar del ejemplo 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 árbol

Answer 12

también hazlo con 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();
}

Answer 13

una función más simple list-to-tree-lite

npm install list-to-tree-lite

listToTree(list)

fuente:

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

Answer 14

Puede manejar esta pregunta con solo dos líneas de codificación:

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

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

Prueba en línea (mira la consola del navegador para el árbol creado)

Requisitos:

1- Instalar lodash 4 (una biblioteca de Javascript para manipular objetos y colecciones con métodos de rendimiento => como el Linq en c #) Lodash

2- Un flatArray como a continuación:

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

Gracias al Sr. Bakhshabadi

Buena suerte

Answer 15

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