Рекурсивный поиск JavaScript в объекте JSON

Я пытаюсь вернуть конкретный node в структуре объекта JSON, который выглядит как

{
    "id":"0",
    "children":[
        {
            "id":"1",
            "children":[...]
        },
        {
            "id":"2",
            "children":[...]
        }
    ]
}

Итак, это древовидное дочернее-родительское отношение. Каждый node имеет уникальный идентификатор. Я пытаюсь найти конкретный node, как этот

function findNode(id, currentNode) {

    if (id == currentNode.id) {
        return currentNode;
    } else {
        currentNode.children.forEach(function (currentChild) {            
            findNode(id, currentChild);
        });
    }
}

Я выполняю поиск, например, findNode("10", rootNode). Но даже если поиск находит совпадение, функция всегда возвращает undefined. У меня плохое представление о том, что рекурсивная функция не останавливается после нахождения совпадения и продолжает работать, наконец возвращает undefined, потому что в последних рекурсивных исполнениях она не достигает точки возврата, но я не уверен, как исправить это.

Пожалуйста, помогите!

Ответ 1

При поиске рекурсивно вы должны вернуть результат, вернув его. Однако вы не возвращаете результат findNode(id, currentChild).

function findNode(id, currentNode) {
    var i,
        currentChild,
        result;

    if (id == currentNode.id) {
        return currentNode;
    } else {

        // Use a for loop instead of forEach to avoid nested functions
        // Otherwise "return" will not work properly
        for (i = 0; i < currentNode.children.length; i += 1) {
            currentChild = currentNode.children[i];

            // Search in the current child
            result = findNode(id, currentChild);

            // Return the result if the node has been found
            if (result !== false) {
                return result;
            }
        }

        // The node has not been found and we have no more options
        return false;
    }
}

Ответ 2

function findNode(id, currentNode) {

    if (id == currentNode.id) {
        return currentNode;
    } else {
        var result;
        currentNode.children.forEach(function(node){
            if(node.id == id){
                result = node;
                return;
            }
        });
        return (result ? result : "No Node Found");
    }
}
console.log(findNode("10", node));

Этот метод вернет узел, если он присутствует в списке узлов. Но это будет проходить через весь дочерний узел, так как мы не можем успешно разорвать поток forEach. Лучшая реализация будет выглядеть ниже.

function findNode(id, currentNode) {

    if (id == currentNode.id) {
        return currentNode;
    } else {
        for(var index in currentNode.children){
            var node = currentNode.children[index];
            if(node.id == id)
                return node;
            findNode(id, node);
        }
        return "No Node Present";
    }
}
console.log(findNode("1", node));

Ответ 3

Я использую следующее

var searchObject = function (object, matchCallback, currentPath, result, searched) {
    currentPath = currentPath || '';
    result = result || [];
    searched = searched || [];
    if (searched.indexOf(object) !== -1 && object === Object(object)) {
        return;
    }
    searched.push(object);
    if (matchCallback(object)) {
        result.push({path: currentPath, value: object});
    }
    try {
        if (object === Object(object)) {
            for (var property in object) {
                if (property.indexOf("$") !== 0) {
                    //if (Object.prototype.hasOwnProperty.call(object, property)) {
                        searchObject(object[property], matchCallback, currentPath + "." + property, result, searched);
                    //}
                }
            }
        }
    }
    catch (e) {
        console.log(object);
        throw e;
    }
    return result;
}

Тогда вы можете написать

searchObject(rootNode, function (value) { return value != null && value != undefined && value.id == '10'; });

Теперь это работает с циклическими ссылками, и вы можете сопоставить любое поле или комбинацию полей, которые вам нравятся, изменив функцию matchCallback.

Ответ 4

Мне очень понравился поиск по дереву! Дерево является чрезвычайно распространенной структурой данных для большинства современных сложных структурированных задач. Так что у меня была такая же задача на обед тоже. Я даже провел некоторые глубокие исследования, но на самом деле не нашел ничего нового! Итак, что я получил для вас сегодня, это "Как я реализовал это в современном синтаксисе JS":

// helper
find_subid = (id, childArray) => {
    for( child of childArray ) {
        foundChild = find_id( i, child ); // not sub_id, but do a check (root/full search)!
        if( foundChild ) // 200 
            return foundChild;
    }
    return null; // 404
}

// actual search method
find_id = (id, parent) => (id == parent.id) : parent : find_subid(id, parent.childArray);

Ответ 5

Я бы постарался не изобретать велосипед. Мы используем object-scan для всех наших потребностей в обработке данных. Это концептуально очень просто, но допускает много интересных вещей. Вот как бы вы решили свой конкретный вопрос

Определение данных

const data = {
  "id": "0",
  "children": [{
      "id": "1",
      "children": [{
          "id": "3",
          "children": []
        },
        {
          "id": "4",
          "children": []
        }
      ]
    },
    {
      "id": "2",
      "children": [{
          "id": "5",
          "children": []
        },
        {
          "id": "6",
          "children": []
        }
      ]
    }
  ]
};

Logic

const findNode = (id, input) => {
  let obj = null;
  objectScan(['**.id'], {
    filterFn: (key, value, { parents }) => {
      if (value === id) {
        obj = parents[0];
      }
    },
    breakFn: () => obj !== null
  })(data);
  return obj;
};

const result = findNode('6', data);

Выход

// result =>
{
  "id": "6",
  "children": []
}