Создайте массив массивов из плоского массива в javascript

Ответ 1

Существует эффективное решение, если вы используете поиск по карте. Если родители всегда приходят перед своими детьми, вы можете объединить две петли. Он поддерживает несколько корней. Он дает ошибку на висячих ветвях, но может быть изменен, чтобы игнорировать их. Это не требует сторонней библиотеки. Это, насколько я могу судить, самое быстрое решение.

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

Если вы занимаетесь теорией сложности, это решение Θ (n log (n)). Рекурсивным фильтром является Θ (n ^ 2), что может быть проблемой для больших наборов данных.

Ответ 2

Как упомянул @Sander, ответ @Halcyon предполагает предварительно отсортированный массив, а следующий - нет. (Однако предполагается, что вы загрузили underscore.js - хотя это может быть написано на vanilla 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>

Ответ 3

Была такая же проблема, но я не мог быть уверен, что данные отсортированы или нет. Я не мог использовать стороннюю библиотеку, так что это просто ванильный 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, " "))

Ответ 4

Очень простой способ сделать это

(БОНУС1: УЗЛЫ МОГУТ или МОГУТ НЕ ЗАКАЗАТЬСЯ)

(БОНУС2: НЕ ТРЕБУЕТСЯ БИБЛИОТЕКА ТРЕТЬЕЙ СТОРОНЫ, ПРОСТО JS)

(BONUS3: пользователь "Elias Rabl" говорит, что это самое быстрое решение, см. его ответ ниже)

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
}

Вот тест, он может помочь вам понять, как работает решение:

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

Ответ 5

более простая функция 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 children object
            childrenOf[parentId] = childrenOf[parentId] || [];
            // push it into its parent children object
            childrenOf[parentId].push(item);
        } else {
            tree.push(item);
        }
    };

    return tree;
}

jsfiddle

Ответ 6

Используйте этот подход 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)
)

Ответ 7

Вы можете справиться с этим вопросом с помощью двухстрочного кодирования:

_(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 для управления объектами и коллекциями с помощью методов-исполнителей => как 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:[]
    }];

Благодарю господина Бахшабади

Удачи

Ответ 8

Это может быть полезный пакет list-to-tree Установите:

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

Ответ 9

Это предложение для неупорядоченных предметов. Эта функция работает с одним циклом и хэш-таблицей и собирает все элементы с их id. Если корневой узел найден, объект добавляется в массив результатов.

function getTree(data, root) {
    var o = {};
    data.forEach(function (a) {
        if (o[a.id] && o[a.id].children) {
            a.children = o[a.id].children;
        }
        o[a.id] = a;
        o[a.parentId] = o[a.parentId] || {};
        o[a.parentId].children = o[a.parentId].children || [];
        o[a.parentId].children.push(a);
    });
    return o[root].children;
}

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

Ответ 10

Я написал тестовый скрипт для оценки производительности двух самых общих решений (это означает, что входные данные не должны быть отсортированы заранее и код не зависит от сторонних библиотек), предложенный пользователями shekhardtu (см. Ответ) и FurkanO (см. ответ).

http://playcode.io/316025?tabs=console&script.js&output

Решение FurkanO кажется самым быстрым.

Ответ 11

Здесь простая вспомогательная функция, созданная мной после вышеупомянутых ответов, адаптированная к среде 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

}

Ответ 12

также делать это с помощью 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();
}

Ответ 13

Мне нравится @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;
}

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

Ответ 14

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

Ответ 15

Вы могли бы взглянуть на утилиту дерева пакетов npm. Это также может быть очень удобно, если вы хотите загрузить данные из таблицы данных SQL DB. Вы также можете легко добавить дополнительные данные к узлам в созданном дереве.

Отказ от ответственности, я сделал этот пакет.

Ответ 16

Вы можете использовать этот пакет "treeify" от Github здесь или NPM.

Монтаж:

$ npm install --save-dev treeify-js

Ответ 17

Вот модифицированная версия Стивена Харриса, которая является простой ES5, и возвращает объект с ключом на идентификатор, а не возвращает массив узлов как на верхнем уровне, так и на дочерних.

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

Ответ 18

Это модифицированная версия выше, которая работает с несколькими корневыми элементами, я использую GUID для своих идентификаторов и родительских элементов, поэтому в пользовательском интерфейсе, который создает их, я жестко кодирую корневые элементы примерно на 0000000-00000-00000-TREE-ROOT -item

var tree = 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;
}

Ответ 19

Скопировано из Интернета 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",
        }
    };

Ответ 20

Вы можете использовать пакет массива npm для дерева https://github.com/alferov/array-to-tree. Он преобразует простой массив узлов (с указателями на родительские узлы) во вложенную структуру данных.

Решает проблему с преобразованием извлеченных из базы данных наборов данных во вложенную структуру данных (т.е. дерево навигации).

Использование:

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

Ответ 21

Это старая ветка, но я подумал, что обновление никогда не повредит, с ES6 вы можете сделать:

(parent => categories.filter(cat => cat. parentId === parent).map(cat=>({...cat, children: recursive1(cat.id)})))(0)

надеюсь, это поможет кому-то

Ответ 22

это то, что я использовал в реактивном проекте

// 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"
         }
      ]
   }
]'''

Ответ 23

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