Рекурсивная итерация по глубоко вложенному объекту для поиска родителя

Question

У меня есть древовидная структура данных с дочерними элементами:

{  id: 1,
   name: "Dog",
   parent_id: null,
   children: [
         {
             id: 2,
             name: "Food",
             parent_id: 1,
             children: []
         },
         {
             id: 3,
             name: "Water",
             parent_id: 1,
             children: [
                 {
                    id: 4,
                    name: "Bowl",
                    parent_id: 3,
                    children: []
                 },
                 {
                    id: 5,
                    name: "Oxygen",
                    parent_id: 3,
                    children: []
                 },
                 {
                    id: 6,
                    name: "Hydrogen",
                    parent_id: 3,
                    children: []
                 }
             ]
         }
   ]
}

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

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

Вот мой список, который продумывает проблему и пытается псевдокодировать ее:

входные данные:

1. дерево (данные сверху)
2. parentTitle от выбранного элемента в DOM

выходные данные:

1. дерево со вставленным элементом

шаги:

1. определить максимальный используемый идентификатор, чтобы узнать, каким будет следующий уникальный идентификатор
2. проверить текущий уровень данных длясовпадать с заголовком родителя
3. , если совпадает, затем установить id и parent_id в новых данных и вставить в потомки родителя
4. , если совпадения нет, тогда проверить, имеют ли данные текущего уровня дочерние элементы
5. если у текущего уровня есть дети, необходимо повторять шаги 2+ для каждого, пока не будет найдено совпадение

Вот мой код:

function askUserForNewItem(e) {
   const tree = getTree(); // returns above tree data structure
   const name = prompt( 'Enter new item’s name:' ); // user input to match and insert as new item in tree
   const clickedTitle = getClickedTitle(e); // returns string title of clicked on item from DOM - for example "Dog" or "Bowl"
   const parent = determineParent(tree, clickedTitle);
   const parent_id = parent[0].id;
   // TODO - needs to set real unique id (highest unused id)
   const newId = 101; // hard coded for now, needs to be dynamic
   // TODO - needs to insert into correct level of children array in tree
   return tree.children.push({ id: newId, name, emoji, children: [], parent_id: parent_id });
}

function determineParent(tree, clickedTitle) {

    if(tree.children.length === 0) {
        return false;
    }
    let treeLevel = tree;
    let parent = [];
    while(treeLevel.children.length !== 0) {
        parent = treeLevel.children.filter(child => child.name === clickedTitle);
        if(parent.length !== 0) {
            break;
        }
        else {
            // what to do here to make this recursive?
        }
    }

    return parent;
}

Так что, если пользователь набрал "Cat", в то время какнажав кнопку «Добавить» для «Собаки», затем новый объект

{
    id: 7,
    name: "Cat",
    parent_id: 1,
    children: []
}

Будет бВставляется в дочерние объекты первого уровня «Собака» в дереве данных.

Answer 1

Если вы хотите рекурсивное решение, вам следует изменить метод defineParent, чтобы он осуществлял поиск по дереву.Не уверен, что это именно то, что вы ищете, но я надеюсь, что вы получите общую идею

function determineParent(curNode, clickedTitle) {
    if(curNode.name===clickedTitle)
        return curNode; // found the parent node with the correct clickedTitle

    // not found yet, do a recusive search down the tree.

    for(const node of curNode.children) {
        return determineParent(node,clickedTitle);
    }

    return null; // not found.
}

идея состоит в том, чтобы начать с самого верхнего узла (curNode) и сначала определить, является ли он правильным родителем,если нет, то возьмите первых детей, посмотрите, совпадают ли они, а если нет, то найдите их детей и т. д.

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

Один из способов - включитьЗащитный счетчик, который уменьшается при каждом рекурсивном вызове, а затем отключается, когда он достигает нуля.

function determineParent(curNode, clickedTitle, safeGuard) {
    if(curNode.name===clickedTitle)
        return curNode; // found the parent node with the correct clickedTitle

    if(safeGuard===0)
        return null; // bail out 

    // not found yet, do a recusive search down the tree.
    for(const node of curNode.children) {
        return determineParent(node,clickedTitle,--safeGuard);
    }

    return null; // not found.
}

, а затем вызывает его как

  this.determineParent(tree,"title",100);

, чтобы ограничить количество поисков до 100.

Answer 2

Если можно использовать Lodash + Deepdash , тогда:

let child = {
    name: "Cat",
    children: []
};
let maxUsedId=-1;
_.eachDeep([data],(val)=>{
  if(val.id>maxUsedId){
    maxUsedId = val.id;
  }

  if(val.name==parentName){
    val.children.push(child);
    child.parent_id = val.id;
  }
},{tree:true});
child.id=maxUsedId+1;

Кодекс для этого