Как я могу рекурсивно использовать Array.prototype.find() при возврате одного объекта?

Большая проблема, которую я пытаюсь решить, заключается в следующих данных:

var data = [
    { id: 1 },
    { id: 2 },
    { id: 3 },
    { id: 4, children: [
        { id: 6 },
        { id: 7, children: [
            {id: 8 },
            {id: 9 }
        ]}
    ]},
    { id: 5 }
]

Я хочу сделать функцию findById(data, id) которая возвращает { id: id }. Например, findById(data, 8) должен возвращать { id: 8 }, а findById(data, 4) должен возвращать { id: 4, children: [...] }.

Чтобы реализовать это, я использовал Array.prototype.find рекурсивно, но столкнулся с трудностями, когда return Array.prototype.find объектов. Моя реализация возвращает путь к определенному объекту.

Например, когда я использовал findById(data, 8), он возвращает путь к { id: 8 }:

 { id: 4, children: [ { id: 6 }, { id: 7, children: [ { id: 8}, { id: 9] } ] }

Вместо этого я хотел бы просто вернуться

{ id: 8 }

Реализация (Node.js v4.0.0)

jsfiddle

var data = [
    { id: 1 },
    { id: 2 },
    { id: 3 },
    { id: 4, children: [
        { id: 6 },
        { id: 7, children: [
            {id: 8 },
            {id: 9 }
        ]}
    ]},
    { id: 5 }
]

function findById(arr, id) {
    return arr.find(a => {
        if (a.children && a.children.length > 0) {
            return a.id === id ? true : findById(a.children, id)
        } else {
            return a.id === id
        }
    })
    return a
}

console.log(findById(data, 8)) // Should return { id: 8 }

// Instead it returns the "path" block: (to reach 8, you go 4->7->8)
//
// { id: 4,
//   children: [ { id: 6 }, { id: 7, children: [ {id: 8}, {id: 9] } ] }

Ответ 1

Я бы просто использовал регулярный цикл и рекурсивный поиск стиля:

function findById(data, id) {
    for(var i = 0; i < data.length; i++) {
        if (data[i].id === id) {
            return data[i];
        } else if (data[i].children && data[i].children.length && typeof data[i].children === "object") {
            findById(data[i].children, id);
        }
    }
}

//findById(data, 4) => Object {id: 4, children: Array[2]}
//findById(data, 8) => Object {id: 8}

Ответ 2

Проблема в том, что у вас есть пузырение находки. Если идентификатор найден внутри вложенной структуры, обратный вызов пытается вернуть элемент, который интерпретируется как true, значение для поиска.

Метод find выполняет функцию обратного вызова один раз для каждого элемента, присутствующего в массиве, пока не найдет элемент, в котором callback возвращает истинное значение. [ MDN ]

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

var data = [{ id: 1 }, { id: 2 }, { id: 3 }, { id: 4, children: [{ id: 6 }, { id: 7, children: [{ id: 8 }, { id: 9 }] }] }, { id: 5 }];

function findById(data, id) {
    function iter(a) {
        if (a.id === id) {
            result = a;
            return true;
        }
        return Array.isArray(a.children) && a.children.some(iter);
    }

    var result;
    data.some(iter);
    return result
}

console.log(findById(data, 8));

Ответ 3

Давайте рассмотрим реализацию, основанную на рекурсивных вызовах:

function findById(tree, nodeId) {
  for (let node of tree) {
    if (node.id === nodeId) return node

    if (node.children) {
      let desiredNode = findById(node.children, nodeId)
      if (desiredNode) return desiredNode
    }
  }
  return false
}

использование

var data = [
  { id: 1 }, { id: 2 }, { id: 3 },
  { id: 4, children: [
      { id: 6 },
      { id: 7,
        children: [
          { id: 8 }, 
          { id: 9 }
        ]}]},
  { id: 5 }
]

findById(data,  7 ) // {id: 7, children: [{id: 8}, {id: 9}]}
findById(data,  5 ) // {id: 5}
findById(data,  9 ) // {id: 9}
findById(data,  11) // false

Чтобы упростить картину 🐒, представьте, что:

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

Теперь давайте попробуем применить его к нашему рекурсивному алгоритму 🍌:

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

Продолжать изучать рекурсию в первый раз, кажется, нелегко this но эта техника позволяет элегантно решать повседневные задачи 😍.

Ответ 4

На основе решения Пурхало Алекса,

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

Это похоже на find и find findIndex вместе через массивы объектов с вложенными массивами объектов в данном свойстве.

findByIdRecursive(tree, nodeId, prop = '', byIndex = false, arr = []) {
    for (let [index, node] of tree.entries()) {
        if (node.id === nodeId) return byIndex ? [...arr, index] : node;

        if (prop.length && node[prop].length) {
            let found = this.findByIdRecursive(node[prop], nodeId, prop, byIndex, [
                ...arr,
                index
            ]);
            if (found) return found;
        }
    }
    return false;
}

Теперь вы можете управлять свойством и типом поиска и получать правильный результат.