Преобразование реляционного массива в объект дерева в Typescript

Question

У меня есть структура базы данных в массиве объектов, хранящихся так:

array = [ {"name": "a", "id": "1",  "parentId": NULL},
 {"name": "b", "id": "2", "parentId": "1"},
 {"name": "c", "id": "3", "parentId": "1"},
 {"name": "d", "id": "4", "parentId": "1"},
 {"name": "e", "id": "5", "parentId": "2"},
 {"name": "f", "id": "6", "parentId": "3"},
 {"name": "g", "id": "7", "parentId": "3"},
 {"name": "h", "id": "8", "parentId": "4"},
 {"name": "j", "id": "9", "parentId": "4"}]

И я хочу получить как этот объект дерева;

{
    a: {
        b: {
            e: {}
        },
        c: {
            f: {},
            g: {}
        },
        d: {
            h: {},
            j: {}
        }
    }
}

Answer 1

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

buildTree(arr, root) {
  return {
    [root.name]: arr
      .filter(x => x.parentId === root.id)
      .map(x => buildTree(x))
      .reduce((a, b) => ({ ...a, ...b }), {}),
  };
}

const tree = buildTree(array, array.find(x => !x.parentId));

Answer 2

Вы можете взять один цикл и уважать родителей.

Этот подход также работает с несортированными данными.

var array = [{ name: "a", id: "1", parentId: null }, { name: "b", id: "2", parentId: "1" }, { name: "c", id: "3", parentId: "1" }, { name: "d", id: "4", parentId: "1" }, { name: "e", id: "5", parentId: "2" }, { name: "f", id: "6", parentId: "3" }, { name: "g", id: "7", parentId: "3" }, { name: "h", id: "8", parentId: "4" }, { name: "j", id: "9", parentId: "4" }],
    tree = function (data, root) {
        var o = {};
        data.forEach(({ name, id, parentId }) => {
            o[id] = o[id] || {};
            o[parentId] = o[parentId] || {};
            o[parentId][name] = o[id];
        });
        return o[root];
    }(array, null);

console.log(tree);

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

Answer 3

Вы можете просто использовать Array.reduce() здесь, чтобы построить дерево.Основная идея здесь состоит в том, чтобы сохранить flatMap всех ключей и поместить их ссылку в дерево, чтобы изменения, сделанные в дочерних или дочерних узлах на плоской карте, отражались в основном дереве.Он может работать для любого количества уровней, а также для неупорядоченного массива.

Попробуйте следующее:

let array = [ {"name": "a", "id": "1", "parentId": null}, {"name": "b", "id": "2", "parentId": "1"}, {"name": "c", "id": "3", "parentId": "1"}, {"name": "d", "id": "4", "parentId": "1"}, {"name": "e", "id": "5", "parentId": "2"}, {"name": "f", "id": "6", "parentId": "3"}, {"name": "g", "id": "7", "parentId": "3"}, {"name": "h", "id": "8", "parentId": "4"}, {"name": "j", "id": "9", "parentId": "4"}, {"name": "k", "id": "10", "parentId": "9"}, {"name": "l", "id": "11", "parentId": "10"}, {"name": "m", "id": "12", "parentId": "9"}];
 
 let idToNameMap = array.reduce((a, {name, id}) => (a[id] = name, a), {});
 let flatMap = {};
 
 let result = array.reduce((acc, curr)=>{
  if(!curr.parentId)
    return acc;
  let key = idToNameMap[curr.parentId];
  if(!flatMap[key]){
    flatMap[key] = {};
    acc[key] = flatMap[key];
  }
  let node = flatMap[key];
  flatMap[idToNameMap[curr.id]] = {};
  node[idToNameMap[curr.id]] = flatMap[idToNameMap[curr.id]];
  return acc;
 },{});
 
 console.log(result);

Answer 4

Возможная реализация:

function grow(items) {
    var things = {"": {}};
    for (var i of items) {
        things[i.id] = {};
    }
    for (var i of items) {
        things[i.parentId || ""][i.name] = things[i.id];
    }
    return things[""];
}

Два цикла можно объединить, если есть гарантия, что родитель всегда предшествует своим потомкам.