Построить массив дерева из плоского массива в javascript

134

У меня есть сложный файл json, который мне нужно обработать с помощью javascript, чтобы сделать его иерархическим, чтобы позже построить дерево. Каждая запись json имеет: id: уникальный идентификатор, parentId: идентификатор родительского узла (который равен 0, если узел является корнем дерева) уровень: уровень глубины в дереве

Данные json уже «заказаны». Я имею в виду, что запись будет иметь над собой родительский узел или узел-брат, а под собой дочерний узел или узел-брат.

Вход:

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

    ]
}
Franck
источник
2
Есть несколько способов сделать это, вы еще что-нибудь пробовали?
bfavaretto 02
Я предполагаю, что a parentIdof 0означает отсутствие родительского идентификатора и должен быть верхним слоем.
Донни Д'Амато,
Обычно такие задачи требовали обширных рабочих знаний. Хороший вопрос
Gangadhar JANNU

Ответы:

158

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

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

console.log(list_to_tree(entries));

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

зимородок
источник
28
имейте в виду, что с этим решением ваши узлы должны быть упорядочены специально, чтобы убедиться, что родители сначала помещены на карту, иначе процесс поиска будет ошибочным ... поэтому вам нужно либо отсортировать их по свойству уровня, либо вам нужно чтобы сначала вставить их в карту. и используйте отдельный цикл for для поиска. (я предпочитаю сортировку, однако, когда у вас нет свойства уровня, отдельные циклы могут быть вариантом)
Сандер
Сначала меня удивило то, что наличие дополнительной информации, например: путь типа [1, 5, 6], где массив является последующими предками, не может быть эффективно использован в нем. Но, глядя на код, он вроде бы имеет смысл, поскольку я считаю, что это O (n)
Ced
1
Несмотря на хороший ответ, это сложно. Примените мой ответ только для двух строчных кодов: ссылка
Иман Бахрампур,
Пожалуйста, не могли бы вы объяснить, почему это решение Θ (n log (n)). Кажется, это занимает O (n) времени.
Амрендер Сингх 07
@amrendersingh внутри цикла for - это поиск по хешу, в mapкотором (теоретически) O (log n).
Halcyon
72

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

Требования

Предполагается, что свойства id и parentid указывают ID и родительский ID соответственно. Должны быть элементы с родительским ID 0, иначе вы получите пустой массив. Осиротевшие элементы и их потомки «потеряны»

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

Стивен Харрис
источник
4
Вы можете добавить else { parent['children'] = []; }после первого предложения if, чтобы гарантировать, что каждый узел имеет атрибут children(он будет пустым, если узел является листовым узлом)
Кристофер,
2
Ваш фрагмент кода работал отлично, спасибо !! Единственное: treeникогда не передается в качестве аргумента при рекурсивном вызове функции, поэтому я думаю, что строку tree = typeof tree !== 'undefined' ? tree : [];можно заменить наlet tree = [];
Оскар Кальдерон
можно ли изменить это, чтобы разрешить nullparent_ids вместо 0? Edit: Nevermind, я получил это работает, изменяя id: 0к id: null.
dlinx90
Имейте в виду, что в приведенном выше ответе используются два цикла, и, следовательно, его можно улучшить. Так как мне не удалось найти модуль npm, реализующий решение O (n), я создал следующий (модульное тестирование, 100% покрытие кода, размер всего 0,5 КБ и включает типизацию). Может быть, это кому-то поможет: npmjs.com/package/performant-array-to-tree
Филип Станислав,
4
Для всех, кому интересно, код легко конвертируется в vanilla js: jsfiddle.net/LkkwH/853
xec
48

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

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

(БОНУС 3: пользователь «Элиас Рабл» говорит, что это самое быстрое решение, см. Его ответ ниже)

Вот:

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)
});
FurkanO
источник
2
Разве не было бы точнее, если бы мы добавляли childNodesтолько тогда, когда это необходимо? Удалив их из первого forEachи переместив внутрь второго?
arpl
@arpl согласился. При необходимости это можно легко изменить. Или, если вы считаете, что это должно быть по умолчанию, я могу его изменить.
FurkanO
@FurkanO действительно хорошее решение, однако можно ли хоть как-то приблизиться к этой производительности с помощью функционального программирования (без мутаций)
Dac0d3r
34

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

JS Fiddle

Плоский массив в дерево

alexandru.pausan
источник
в некоторых случаях mappedArr[mappedElem['parentid']]['children']не удалось получить доступ к childrenundefined.
Аль-Мотафар
как мне начать с родительского идентификатора: 1?
vinni
31

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

shekhardtu
источник
3
Самый короткий и лучший ответ, я думаю
java-man-script
2
sloooow по сравнению с ответом FurkanO
Геза Тури
16

более простая функция 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

Уильям Люнг
источник
10

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

_(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 в C #) 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

Может пригодиться установка списка пакетов в дерево :

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
}];
DenQ
источник
1
Обратите внимание, что ответы только по ссылкам не приветствуются, ответы SO должны быть конечной точкой поиска решения (по сравнению с еще одной остановкой ссылок, которые со временем устаревают). Пожалуйста, подумайте о добавлении здесь автономного синопсиса, сохранив ссылку как ссылку
kleopatra 01
Я не понимаю, почему -1, я думаю, что это хорошее решение, но, к сожалению, я не нахожу пакет в gitHub или в другом общедоступном репозитории
oriaj
Спасибо за внимание к упаковке. Позже планирую расширить. Вот ссылка на репозиторий github.com/DenQ/list-to-tree
DenQ
@oriaj Я рад, что проект приносит пользу. В планах несколько идей
DenQ
Хорошо работает, спасибо @DenQ. Хотелось бы, чтобы у него было больше тестового покрытия!
IliasT
3

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

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

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

/*
** performance test for /programming/18017869/build-tree-array-from-flat-array-in-javascript
*/

// Data Set (e.g. nested comments)
var comments = [{
    id: 1,
    parent_id: null
}, {
    id: 2,
    parent_id: 1
}, {
    id: 3,
    parent_id: 4
}, {
    id: 4,
    parent_id: null
}, {
    id: 5,
    parent_id: 4
}];

// add some random entries
let maxParentId = 10000;
for (let i=6; i<=maxParentId; i++)
{
  let randVal = Math.floor((Math.random() * maxParentId) + 1);
  comments.push({
    id: i,
    parent_id: (randVal % 200 === 0 ? null : randVal)
  });
}

// solution from user "shekhardtu" (https://stackoverflow.com/a/55241491/5135171)
const nest = (items, id = null, link = 'parent_id') =>
  items
    .filter(item => item[link] === id)
    .map(item => ({ ...item, children: nest(items, item.id) }));
;

// solution from user "FurkanO" (https://stackoverflow.com/a/40732240/5135171)
const createDataTree = dataset => {
    let hashTable = Object.create(null)
    dataset.forEach( aData => hashTable[aData.id] = { ...aData, children : [] } )
    let dataTree = []
    dataset.forEach( aData => {
      if( aData.parent_id ) hashTable[aData.parent_id].children.push(hashTable[aData.id])
      else dataTree.push(hashTable[aData.id])
    } )
    return dataTree
};


/*
** lets evaluate the timing for both methods
*/
let t0 = performance.now();
let createDataTreeResult = createDataTree(comments);
let t1 = performance.now();
console.log("Call to createDataTree took " + Math.floor(t1 - t0) + " milliseconds.");

t0 = performance.now();
let nestResult = nest(comments);
t1 = performance.now();
console.log("Call to nest took " + Math.floor(t1 - t0) + " milliseconds.");




//console.log(nestResult);
//console.log(createDataTreeResult);

// bad, but simple way of comparing object equality
console.log(JSON.stringify(nestResult)===JSON.stringify(createDataTreeResult));

Элиас Рабл
источник
2

Это предложение для неупорядоченных товаров. Эта функция работает с одним циклом и с хеш-таблицей и собирает все элементы с их 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; }

Нина Шольц
источник
1

также сделайте это с 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();
}
Уолтер Йе
источник
1

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

Пример: https://jsfiddle.net/kqw1qsf0/17/

Hex.style
источник
1

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

Картик Редди
источник
Я создал эту функцию для преобразования данных из массива объектов в древовидную структуру, которая требуется для интерактивной диаграммы d3 tree. Всего с 40 строками кода я смог получить результат. Я написал эту функцию эффективным способом, используя рекурсивную функциональность в js. Попробуйте и дайте мне знать свой отзыв. Спасибо!!!!
karthik reddy
Спасибо за anwser .. Он отлично работает для моей топологии дерева d3 .. Теперь у меня есть требование, чтобы мне нужно было изменить цвет узла на основе значений узла .. Так что для этого мне нужно передать значение флага в JSON , Как мне это сделать .. {"name": "Top Level", "flag": 1, "parent": "null", "children": [{"name": "india", "flag": 0 , "parent": "Top Level", "children": [
Puneeth Kumar
1

У меня была аналогичная проблема пару дней назад, когда мне приходилось отображать дерево папок из плоского массива. Я не видел здесь никакого решения в TypeScript, поэтому надеюсь, что это будет полезно.

В моих случаях основной родитель был только один, также массив rawData не нуждался в сортировке. Решения основаны на подготовке объекта temp, например {parentId: [child1, child2, ...] }

пример сырых данных

const flatData: any[] = Folder.ofCollection([
  {id: '1', title: 'some title' },
  {id: '2', title: 'some title', parentId: 1 },
  {id: '3', title: 'some title', parentId: 7 },
  {id: '4', title: 'some title', parentId: 1 },
  {id: '5', title: 'some title', parentId: 2 },
  {id: '6', title: 'some title', parentId: 5 },
  {id: '7', title: 'some title', parentId: 5 },

]);

def из папки

export default class Folder {
    public static of(data: any): Folder {
        return new Folder(data);
    }

    public static ofCollection(objects: any[] = []): Folder[] {
        return objects.map((obj) => new Folder(obj));
    }

    public id: string;
    public parentId: string | null;
    public title: string;
    public children: Folder[];

    constructor(data: any = {}) {
        this.id = data.id;
        this.parentId = data.parentId || null;
        this.title = data.title;
        this.children = data.children || [];
    }
}

РЕШЕНИЕ : функция, которая возвращает древовидную структуру для плоского аргумента

    public getTree(flatData: any[]): Folder[] {
        const addChildren = (item: Folder) => {
            item.children = tempChild[item.id] || [];
            if (item.children.length) {
                item.children.forEach((child: Folder) => {
                    addChildren(child);
                });
            }
        };

        const tempChild: any = {};
        flatData.forEach((item: Folder) => {
            const parentId = item.parentId || 0;
            Array.isArray(tempChild[parentId]) ? tempChild[parentId].push(item) : (tempChild[parentId] = [item]);
        });

        const tree: Folder[] = tempChild[0];
        tree.forEach((base: Folder) => {
            addChildren(base);
        });
        return tree;
    }
Оскар Косовски
источник
0

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

}
Эрик Д. Филдс
источник
0

Вот модифицированная версия Стивена Харриса, которая представляет собой простой 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);
nehresman
источник
0

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

var tree = unflatten (записи, "ДЕРЕВО-КОРНИ-ПУНКТ");

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;
}
Ник Ликата
источник
0

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

Вы можете использовать npm package array-to-tree 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
 */
Денищук Павло Миколайович
источник
0

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

// 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"
         }
      ]
   }
]```
Кристи Милеа
источник
0

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

Монтаж:

$ npm install --save-dev treeify-js

user11415035
источник
0

Мое машинописное решение, возможно, оно вам поможет:

type ITreeItem<T> = T & {
    children: ITreeItem<T>[],
};

type IItemKey = string | number;

function createTree<T>(
    flatList: T[],
    idKey: IItemKey,
    parentKey: IItemKey,
): ITreeItem<T>[] {
    const tree: ITreeItem<T>[] = [];

    // hash table.
    const mappedArr = {};
    flatList.forEach(el => {
        const elId: IItemKey = el[idKey];

        mappedArr[elId] = el;
        mappedArr[elId].children = [];
    });

    // also you can use Object.values(mappedArr).forEach(...
    // but if you have element which was nested more than one time
    // you should iterate flatList again:
    flatList.forEach((elem: ITreeItem<T>) => {
        const mappedElem = mappedArr[elem[idKey]];

        if (elem[parentKey]) {
            mappedArr[elem[parentKey]].children.push(elem);
        } else {
            tree.push(mappedElem);
        }
    });

    return tree;
}

Пример использования:

createTree(yourListData, 'id', 'parentId');
zemil
источник
0

Я написал версию ES6 на основе ответа @Halcyon

const array = [
  {
    id: '12',
    parentId: '0',
    text: 'one-1'
  },
  {
    id: '6',
    parentId: '12',
    text: 'one-1-6'
  },
  {
    id: '7',
    parentId: '12',
    text: 'one-1-7'
  },

  {
    id: '9',
    parentId: '0',
    text: 'one-2'
  },
  {
    id: '11',
    parentId: '9',
    text: 'one-2-11'
  }
];

// Prevent changes to the original data
const arrayCopy = array.map(item => ({ ...item }));

const listToTree = list => {
  const map = {};
  const roots = [];

  list.forEach((v, i) => {
    map[v.id] = i;
    list[i].children = [];
  });

  list.forEach(v => (v.parentId !== '0' ? list[map[v.parentId]].children.push(v) : roots.push(v)));

  return roots;
};

console.log(listToTree(arrayCopy));

Принцип этого алгоритма заключается в использовании «карты» для установления отношения индекса. Легко найти «элемент» в списке по «parentId» и добавить «потомков» к каждому «элементу», потому что «список» является ссылочным отношением, поэтому «корни» будут строить отношения со всем деревом.

Weiya ou
источник
0

Ответьте на аналогичный вопрос:

https://stackoverflow.com/a/61575152/7388356

ОБНОВИТЬ

Вы можете использовать Mapобъект, представленный в ES6. По сути, вместо того, чтобы искать родителей путем повторной итерации по массиву, вы просто получаете родительский элемент из массива по родительскому идентификатору, как вы получаете элементы в массиве по индексу.

Вот простой пример:

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

function toTree(arr) {
  let arrMap = new Map(arr.map(item => [item.id, item]));
  let tree = [];

  for (let i = 0; i < arr.length; i++) {
    let item = arr[i];

    if (item.parentId !== "0") {
      let parentItem = arrMap.get(item.parentId);

      if (parentItem) {
        let { children } = parentItem;

        if (children) {
          parentItem.children.push(item);
        } else {
          parentItem.children = [item];
        }
      }
    } else {
      tree.push(item);
    }
  }

  return tree;
}

let tree = toTree(people);

console.log(tree);

Редактировать crazy-williams-glgj3

Yusufbek
источник
1
Хотя эта ссылка может дать ответ на вопрос, лучше включить сюда основные части ответа и предоставить ссылку для справки. Ответы, содержащие только ссылки, могут стать недействительными, если ссылка на страницу изменится. - Из
отзыва
Хорошо, добавил основную идею и привел примерный пример,
Юсуфбек
0

Основываясь на ответе @FurkanO , я создал другую версию, которая не изменяет исходные данные (например, запрос @ Dac0d3r). Мне очень понравился ответ @ shekhardtu , но я понял, что ему нужно много раз фильтровать данные. Я подумал, что решением может быть использование ответа FurkanO, сначала скопировав данные. Я попробовал свою версию в jsperf , и результаты были, к сожалению, (очень) мрачными ... Похоже, что принятый ответ действительно хороший! Моя версия довольно настраиваемая и отказоустойчивая, так что я все равно поделюсь ею с вами, ребята; вот мой вклад:

function unflat(data, options = {}) {
    const { id, parentId, childrenKey } = {
        id: "id",
        parentId: "parentId",
        childrenKey: "children",
        ...options
    };
    const copiesById = data.reduce(
        (copies, datum) => ((copies[datum[id]] = datum) && copies),
        {}
    );
    return Object.values(copiesById).reduce(
        (root, datum) => {
            if ( datum[parentId] && copiesById[datum[parentId]] ) {
                copiesById[datum[parentId]][childrenKey] = [ ...copiesById[datum[parentId]][childrenKey], datum ];
            } else {
                root = [ ...root, datum ];
            }
            return root
        }, []
    );
}

const data = [
    {
        "account": "10",
        "name": "Konto 10",
        "parentAccount": null
    },{
        "account": "1010",
        "name": "Konto 1010",
        "parentAccount": "10"
    },{
        "account": "10101",
        "name": "Konto 10101",
        "parentAccount": "1010"
    },{
        "account": "10102",
        "name": "Konto 10102",
        "parentAccount": "1010"
    },{
        "account": "10103",
        "name": "Konto 10103",
        "parentAccount": "1010"
    },{
        "account": "20",
        "name": "Konto 20",
        "parentAccount": null
    },{
        "account": "2020",
        "name": "Konto 2020",
        "parentAccount": "20"
    },{
        "account": "20201",
        "name": "Konto 20201",
        "parentAccount": "2020"
    },{
        "account": "20202",
        "name": "Konto 20202",
        "parentAccount": "2020"
    }
];

const options = {
    id: "account",
    parentId: "parentAccount",
    childrenKey: "children"
};

console.log(
    "Hierarchical tree",
    unflat(data, options)
);

С помощью параметра options можно настроить, какое свойство использовать в качестве идентификатора или родительского идентификатора. Также есть возможность настроить имя дочернего свойства, если кому- "childNodes": []то что-то нужно .

OP может просто использовать параметры по умолчанию:

input.People = unflat(input.People);

Если родительский идентификатор falsy ( null, undefinedили другие falsy значения) или родительский объект не существует, мы считаем , что объект будет корневой узел.

pekaaw
источник
-1
  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

отключен от сети
источник
-1

Преобразование массива узлов в дерево

Функция ES6 для преобразования массива узлов (связанных родительским идентификатором ) в древовидную структуру:

/**
 * Convert nodes list related by parent ID - to tree.
 * @syntax getTree(nodesArray [, rootID [, propertyName]])
 *
 * @param {Array} arr   Array of nodes
 * @param {integer} id  Defaults to 0
 * @param {string} p    Property name. Defaults to "parent_id"
 * @returns {Object}    Nodes tree
 */

const getTree = (arr, p = "parent_id") => arr.reduce((o, n) => {

  if (!o[n.id]) o[n.id] = {};
  if (!o[n[p]]) o[n[p]] = {};
  if (!o[n[p]].nodes) o[n[p]].nodes= [];
  if (o[n.id].nodes) n.nodes= o[n.id].nodes;

  o[n[p]].nodes.push(n);
  o[n.id] = n;

  return o;
}, {});

Создать список HTML из дерева узлов

Имея наше дерево на месте, вот рекурсивная функция для создания элементов UL> LI:

/**
 * Convert Tree structure to UL>LI and append to Element
 * @syntax getTree(treeArray [, TargetElement [, onLICreatedCallback ]])
 *
 * @param {Array} tree Tree array of nodes
 * @param {Element} el HTMLElement to insert into
 * @param {function} cb Callback function called on every LI creation
 */

const treeToHTML = (tree, el, cb) => el.append(tree.reduce((ul, n) => {
  const li = document.createElement('li');

  if (cb) cb.call(li, n);
  if (n.nodes?.length) treeToHTML(n.nodes, li, cb);

  ul.append(li);
  return ul;
}, document.createElement('ul')));

Демонстрационное время

Вот пример с линейным массивом узлов и использованием обеих вышеуказанных функций:

const getTree = (arr, p = "parent_id") => arr.reduce((o, n) => {
  if (!o[n.id]) o[n.id] = {};
  if (!o[n[p]]) o[n[p]] = {};
  if (!o[n[p]].nodes) o[n[p]].nodes = [];
  if (o[n.id].nodes) n.nodes = o[n.id].nodes;
  o[n[p]].nodes.push(n);
  o[n.id] = n;
  return o;
}, {});


const treeToHTML = (tree, el, cb) => el.append(tree.reduce((ul, n) => {
  const li = document.createElement('li');
  if (cb) cb.call(li, n);
  if (n.nodes?.length) treeToHTML(n.nodes, li, cb);
  ul.append(li);
  return ul;
}, document.createElement('ul')));


// DEMO TIME:

const nodesList = [
  {id: 10,  parent_id: 4,  text: "Item 10"}, // PS: Order does not matters
  {id: 1,   parent_id: 0,  text: "Item 1"},  
  {id: 4,   parent_id: 0,  text: "Item 4"},
  {id: 3,   parent_id: 5,  text: "Item 3"},
  {id: 5,   parent_id: 4,  text: "Item 5"},
  {id: 2,   parent_id: 1,  text: "Item 2"},
];
const myTree = getTree(nodesList)[0].nodes; // Get nodes of Root (0)

treeToHTML(myTree, document.querySelector("#tree"), function(node) {
  this.textContent = `(${node.parent_id} ${node.id}) ${node.text}`;
  this._node = node;
  this.addEventListener('click', clickHandler);
});

function clickHandler(ev) {
  if (ev.target !== this) return;
  console.clear();
  console.log(this._node.id);
};
<div id="tree"></div>

Роко С. Бульян
источник
-1

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

const data = [{
    id: 1,
    parent_id: 0
}, {
    id: 2,
    parent_id: 1
}, {
    id: 3,
    parent_id: 1
}, {
    id: 4,
    parent_id: 2
}, {
    id: 5,
    parent_id: 4
}, {
    id: 8,
    parent_id: 7
}, {
    id: 9,
    parent_id: 8
}, {
    id: 10,
    parent_id: 9
}];

const arrayToTree = (items=[], id = null, link = 'parent_id') => items.filter(item => id==null ? !items.some(ele=>ele.id===item[link]) : item[link] === id ).map(item => ({ ...item, children: arrayToTree(items, item.id) }))
const temp1=arrayToTree(data)
console.log(temp1)

const treeToArray = (items=[], key = 'children') => items.reduce((acc, curr) => [...acc, ...treeToArray(curr[key])].map(({ [`${key}`]: child, ...ele }) => ele), items);
const temp2=treeToArray(temp1)

console.log(temp2)

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

josesuero
источник