Преобразовать дерево строк в массив

Question

У меня есть объекты с идентификатором в виде строки.Каждый объект может быть дочерним по отношению к другому объекту.Отношения можно угадать по идентификаторам.Например:

[
  { id: '1:2:6', ids: ['1', '2', '6'] },
  { id: '1:4', ids: ['1', '4'] },
  { id: '1', ids: ['1'] },
  { id: '1:2', ids: ['1', '2'] },
]

В этом примере корневым объектом является id: 1, который имеет 2 дочерних элемента id: 1:2 и id: 1:4.Наконец, у id: 1:2 есть дочерние элементы id: 1:2:6.

Я хотел бы преобразовать этот массив в другой массив, в котором дочерние элементы встроены в родителей, поэтому предыдущий массив приведет к:

[
  {
    id: '1',
    children: [
      {
        id: '1:2',
        children: [
          { id: '1:2:6', children: [] }
        ],
      },
      {
        id: '1:4',
        children: [],
      }
    ],
  }
]

Я могу использовать ES6.Я часами пытался найти решение, используя все виды циклов, но не могу понять это.Любая помощь будет оценена!

Answer 1

Вы можете перебирать объекты и уменьшать ids, ища объект на реальном уровне.Если не найден, создайте новый объект.Тогда верните детей.

var data = [{ id: '1:2:6', ids: ['1', '2', '6'] }, { id: '1:4', ids: ['1', '4'] }, { id: '1', ids: ['1'] }, { id: '1:2', ids: ['1', '2'] }],
    tree = data.reduce((r, { ids }) => {
        ids.reduce((t, _, i, a) => {
            var id = a.slice(0, i + 1).join(':'),
                temp = t.find(o => o.id === id);
            
            if (!temp) t.push(temp = { id, children: [] });
            return temp.children;
        }, r);
        return r;
    }, []);

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

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

Итак, мы делаем итерацию по всем объектам всписок.Первоначально для каждого объекта мы устанавливаем текущий список узлов в качестве конечного дерева.И мы повторяем по длине идентификаторов.

Сначала мы создаем идентификатор из списка идентификаторов, разделяя массив ids на постепенно увеличивающиеся фрагменты с помощью slice (['1'], ['1', '2'], ['1', '2', '6') и объединить в строку с :.Таким образом, мы получаем идентификаторы 1, 1: 2, 1: 2: 6 для первого элемента.

Далее мы находим узел в currentNodelist по ранее созданному идентификатору.Если мы не можем найти узел, это означает, что мы еще не добавили его, поэтому нам нужно создать и добавить его (если мы его найдем, нам не нужно добавлять его).

На следующем шагенам нужно углубиться в дерево, поэтому мы назначаем дочерние узлы созданного в данный момент (или того, которого мы нашли) как currentNodelist.С этим мы пройдем дерево глубже, предоставив идентификаторы.

let objs = [
  { id: '1:2:6', ids: ['1', '2', '6'] },
  { id: '1:4', ids: ['1', '4'] },
  { id: '1', ids: ['1'] },
  { id: '1:2', ids: ['1', '2'] },
];

let tree = [];
for (let i = 0; i < objs.length; i++) {
  let obj = objs[i];

  let currentNodeList = tree;
  for (let j = 0; j < obj.ids.length; j++) {
    let id = obj.ids.slice(0, j + 1).join(':');
    let currentNode = currentNodeList.find((node) => node.id === id);

    if (!currentNode) {
      currentNode = {id, children: []};
      currentNodeList.push(currentNode);
    } 

    currentNodeList = currentNode.children;
  }
}

console.log(tree);

Я создал простой gif, который показывает, что происходит в первых двух итерациях.Стрелка указывает на currentListNode.

Answer 3

Построение дерева с использованием рекурсивных алгоритмов

var jsonTree = [{ id: '1:2:6', ids: ['1', '2', '6'] },{ id: '1:4', ids: ['1', '4'] },{ id: '1', ids: ['1'] },{ id: '1:2', ids: ['1', '2'] },]

var newJsonTree = [];
var currentElement = {id: '1',childs: []}
newJsonTree.push(currentElement)

function buildTree(jsonTree, currentElement){
    for(var i=0;i<jsonTree.length;i++){
        var parent = jsonTree[i];
        for(var j=0;j<jsonTree.length;j++){
            var child = jsonTree[j];
            if(child['visited'] != true && child['id'] != currentElement['id'] && child['id'].indexOf(currentElement['id']) == 0 ){
                if(child['id'].split(":").length == currentElement['id'].split(":").length+1){
                    var newElement = {}
                    newElement['id'] = child['id'];
                    newElement['childs'] = [];
                    currentElement['childs'].push(newElement);
                    child['visited'] = true;
                    buildTree(jsonTree, newElement);
                }
            }
        }
    }
}

buildTree(jsonTree, currentElement);
document.write(JSON.stringify(newJsonTree));

результат:

[{ "ID": "1", "Чайлдс": [{ "ID": "1: 4", "Childs": []}, { "ID": "1: 2", "Childs ": [{" ID ":" 1: 2: 6" , "Чайлдс": []}]}]}]

Answer 4

Сначала выясните свой алгоритм «на бумаге».Давайте начнем с пустого дерева и возьмем первую запись: [1, 2, 6].

1. Узел 1: добавьте 1 к дереву - теперь это корень и последний посещенный узел.
2. Узел 2: добавьте дочерний элемент 2 к узлу 1.
3. Узел 6: добавьте дочерний элемент 6 к узлу 2.

При обработке следующей записи, [1, 4], 1 уже находится в дереве - просто добавьте к нему 4.

При обработке последней записи, [1, 2], помните, что 2 также уже находится в дереве.

PSЭто «дети», а не «дети».