Как реализовать рекурсивное добавление узлов в древовидную структуру на JavaScript

Оффтоп javascript
1

Проблема с построением дерева рекурсивно

Пытаюсь написать функцию для создания дерева из массива данных, но что-то идет не так. Может кто-то подскажет правильный подход?

Исходные данные:

[
  { name: 'x', kids: ['y', 'z'] },
  { name: 'y', kids: [''] },
  { name: 'z', kids: ['y', 'w'] },
  { name: 'w', kids: ['y'] }
]

Ожидаемый результат:

 x
/|\
y z
  /|\
 y  w
    |
    y

Мой код (не работает):

var TreeNode = require("tree-node");
var dataArray = [
  { name: 'x', kids: ['y', 'z'] },
  { name: 'y', kids: [''] },
  { name: 'z', kids: ['y', 'w'] },
  { name: 'w', kids: ['y'] }
];

function buildTreeRecursive(currentNode) {
    var newNode = new TreeNode();
    var nodeKids = currentNode.data("kids");
    
    dataArray.forEach(function(element) {
        if(nodeKids !== undefined) {
            nodeKids.forEach(function(kidName) {
                if(element.name == kidName) {
                    newNode.data("name", kidName).data("kids", element.kids);
                    newNode = buildTreeRecursive(newNode);
                    currentNode.appendChild(newNode);
                }
            });
        }
    });
    return currentNode;
}

var mainRoot = new TreeNode();
mainRoot.data("name", dataArray[0].name).data("kids", dataArray[0].kids);
mainRoot = buildTreeRecursive(mainRoot);

Проблема в том, что получается слишком сложный алгоритм из-за вложенных циклов. Как это можно упростить?

2

Твоя главная проблема - ты перезаписываешь newNode в цикле. Создаешь узел, а потом следующий его затирает. Для каждого ребенка делай отдельный узел и сразу добавляй к родителю. Или еще лучше - напиши простую рекурсивную функцию: передаешь имя узла и массив данных, она находит элемент и для каждого ребенка вызывает себя. Будет гораздо чище без этой путаницы с переменными.

3

Проблема в том, что ты создаешь новый узел внутри рекурсии и переписываешь его в цикле. Лучше сначала создать мапу всех узлов, потом связать их. Вот так:

function buildTree(data) {
    const nodeMap = {};
    
    // создаем все узлы
    data.forEach(item => {
        nodeMap[item.name] = new TreeNode().data('name', item.name);
    });
    
    // связываем родителей с детьми
    data.forEach(item => {
        item.kids.forEach(kidName => {
            if (kidName && nodeMap[kidName]) {
                nodeMap[item.name].appendChild(nodeMap[kidName]);
            }
        });
    });
    
    return nodeMap['x']; // корневой узел
}

Так проще и без вложенных циклов.

4

А ты пробовал создать индекс всех узлов по имени? Просто пройдись по массиву и сделай объект типа {x: {name: 'x', kids: []}, y: {...}}. Потом рекурсивно строй связи. Так намного проще искать элементы без вложенных forEach. Какие ошибки выдает?