JavaScript递归搜索JSON对象

Question

我正在尝试返回 JSON 对象结构中特定的节点，它看起来像这样

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

所以这是一种类似树形结构的父子关系。每个节点都有一个独特的ID。 我正在尝试查找一个特定的节点，就像这样。

function findNode(id, currentNode) {

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

我执行搜索，例如findNode("10", rootNode)。但即使搜索找到匹配项，该函数始终返回undefined。我有一种不好的感觉，递归函数在找到匹配项后没有停止并继续运行，最终返回undefined，因为在后续递归执行中它没有到达返回点，但我不确定如何修复此问题。

请帮帮我！

- Dropout

---

由于JavaScript中的foreach循环无法停止，请勿在算法中使用foreach。 - wayne

你为什么要在JSON对象上执行搜索呢？最好考虑在生成JSON对象的地方进行搜索，比如数据库。 - jmbmage

@jmb.mage 因为在现实世界中，你经常需要解决不具备理想条件且细节超出你能力范围的任务。这就是其中之一。 - Dropout

请查看deepdash。 - milahu

@milahu，deepdash在问题发布后4年开始开发，这个功能绝对不需要在其上添加库来实现所需的结果。 - Dropout

Answer 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;
    }
}

- Butt4cak3

---

谢谢！完美运作。 - Dropout

我不得不在for循环中添加额外的检查（即for (i = 0; currentNode.children !== undefined && i < currentNode.children.length; i += 1)），以避免在叶节点出现“TypeError：Cannot read property 'length' of undefined”错误，因为在那里“children”不存在。 - Denis Weerasiri

无法找到未定义的长度休止符。它是一个文档对象。 - amitava mozumder

现在我正在使用Premiere Pro ExtendScript在所有的垃圾桶中按名称搜索一个子项 :) - Guntram

这里有一个类似的解决方案，但代码更少 https://stackoverflow.com/a/52205610/3666971 - jakxnz

如果你在另一个地方返回类型为T的对象，那么最好返回null而不是false。但JavaScript的动态类型非常宽容。 - Stefan Steiger

Answer 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));

- Triode

---

亲爱的@Triode，您定义了“result”，但从未使用它。 - user8106148

@Mehr88sh 抱歉，已经更正了！ - Triode

Answer 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函数，您可以匹配任何字段或字段组合。

- Peter

---

回调函数是个好主意，我也喜欢你能够获取路径和对象。干杯！ - frumbert

可以了，谢谢。你应该提到为了搜索特定节点，你需要更改这部分代码： if (property.indexOf("NameOfTheNodeYouAreLookingFor") !== 0) {}并且将返回结果从 return result; 改为 return object; - atfede

@atfede 我返回 result 的原因是为了允许多个匹配。我有点不确定你在 if (property.indexOf("NameOfTheNodeYouAreLookingFor") !== 0) {} 中的意思是什么。 - Peter

Answer 4

既然这个老问题已经被重新提起，这里提供一种不同的方法。我们可以编写一个相当通用的 searchTree 函数，然后在一个 findId 函数中使用它。 searchTree 函数负责遍历对象；它接受一个回调函数以及树形结构；回调函数确定节点是否匹配。除了节点之外，回调函数还提供了两个函数： next 和 found，我们在不带任何参数的情况下调用它们，分别表示应继续处理或已找到匹配项。如果没有找到匹配项，则返回 null。

具体代码如下：

const searchTree = (fn) => (obj) =>
  Array.isArray(obj)
    ? obj.length == 0
      ? null
      : searchTree (fn) (obj [0]) || searchTree (fn) (obj .slice (1))
    : fn (
      obj,
      () => searchTree (fn) (obj .children || []),
      () => obj
    )

const findId = (target, obj) => searchTree (
  (node, next, found) => node.id == target ? found () : next(),
) (tree)


const tree = {id: 1, name: 'foo', children: [
  {id: 2, name: 'bar', children: []}, 
  {id: 3, name: 'baz', children: [
    {id: 17, name: 'qux', children: []}, 
    {id: 42, name: 'corge', children: []},
    {id: 99, name: 'grault', children: []}
  ]}
]}


console .log (findId (42, tree))
console .log (findId (57, tree))

这段代码特定于在属性children下的数组中找到子节点的结构。虽然我们可以根据需要将其更加通用化，但我发现这是一种常见的支持结构。

有一个很好的争论是这个部分最好使用相互递归来编写。如果需要，我们可以通过以下版本获得相同的API:

const searchArray = (fn) => ([x, ...xs]) =>
  x === undefined
    ? null
    : searchTree (fn) (x) || searchArray (fn) (xs)

const searchTree = (fn) => (obj) =>
  fn (
    obj,
    () => searchArray (fn) (obj .children || []),
    (x) => x
  )

这个方法的效果是相同的，但我认为代码更清晰。但两种方法都可以胜任这个任务。

- Scott Sauyet

Answer 5

我们在数据处理方面使用了object-scan。它的概念非常简单，但可以实现很多酷炫的功能。以下是如何解决您的问题的方法。

// const objectScan = require('object-scan');

const findNode = (id, input) => objectScan(['**'], {
  abort: true,
  rtn: 'value',
  filterFn: ({ value }) => value.id === id
})(input);

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

console.log(findNode('6', data));
// => { id: '6', children: [] }

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

<script src="https://bundle.run/object-scan@13.8.0"></script>

Disclaimer: I'm the author of object-scan

- vincent

---

这里的其他答案提到它们适用于循环对象。object-scan 是否考虑了这一点？ - Scott Sauyet

是的。但是由于这是性能权衡，您需要明确处理它。也就是说，您可以简单地添加 breakFn: ({ isCircular }) => isCircular。 - vincent

我非常喜欢object-scan让这个问题变得如此简单。虽然我还没有完全相信我想在自己的代码中尝试它，但我可能很快就会到达那里。 - Scott Sauyet

Answer 6

类似的问题已经回答了多次，但我只想添加一个包括嵌套数组的通用方法。

const cars = [{
  id: 1,
  name: 'toyota',
  subs: [{
    id: 43,
    name: 'supra'
  }, {
    id: 44,
    name: 'prius'
  }]
}, {
  id: 2,
  name: 'Jeep',
  subs: [{
    id: 30,
    name: 'wranger'
  }, {
    id: 31,
    name: 'sahara'
  }]
}]

function searchObjectArray(arr, key, value) {
  let result = [];
  
  arr.forEach((obj) => {
    if (obj[key] === value) {
      result.push(obj);
    } else if (obj.subs) {
      result = result.concat(searchObjectArray(obj.subs, key, value));
    }
  });
  console.log(result)
  return result;
}

searchObjectArray(cars, 'id', '31') 

searchObjectArray(cars, 'name', 'Jeep')

我希望这能帮助到某些人。

- 697

Answer 7

递归结构搜索、修改、键/值调整/替换。

使用示例：

const results = []; // to store the search results

mapNodesRecursively(obj, ({ v, key, obj, isCircular }) => {
    // do something cool with "v" (or key, or obj)
    // return nothing (undefined) to keep the original value

    // if we search:
    if (key === 'name' && v === 'Roman'){
        results.push(obj);
    }

    // more example flow:
    if (isCircular) {
        delete obj[key]; // optionally - we decide to remove circular links
    } else if (v === 'Russia') {
        return 'RU';
    } else if (key.toLocaleLowerCase() === 'foo') {
        return 'BAR';
    } else if (key === 'bad_key') {
        delete obj[key];
        obj['good_key'] = v;
    } else {
        return v; // or undefined, same effect
    }
});

提示和技巧：

您可以将其用作搜索回调，只需返回空（不会影响任何内容）并选择所需的值到您的数组/集合/映射中。

请注意，回调在每个叶子/值/键上运行（而不仅仅是对象）。

或者您可以使用回调来调整特定值，甚至更改键。 它还自动检测循环环路并提供一个标志，让您决定如何处理它们。

代码

（使用ES6）

函数本身+一些示例演示数据

function mapNodesRecursively(obj, mapCallback, { wereSet } = {}) {
    if (!wereSet) {
        wereSet = new Set();
    }

    if (obj && (obj === Object(obj) || Array.isArray(obj))) {
        wereSet.add(obj);

        for (let key in obj) {
            if (!obj.hasOwnProperty(key)){
                continue;
            }

            let v = obj[key];

            const isCircular = wereSet.has(v);

            const mapped = mapCallback({ v, key, obj, isCircular });
            if (typeof (mapped) !== 'undefined') {
                obj[key] = mapped;
                v = mapped;
            }

            if (!isCircular) {
                mapNodesRecursively(v, mapCallback, { wereSet });
            }
        }
    }

    return obj;
}

let obj = {
    team: [
        {
            name: 'Roman',
            country: 'Russia',
            bad_key: 123,
        },
        {
            name: 'Igor',
            country: 'Ukraine',
            FOO: 'what?',
        },
        {
            someBool: true,
            country: 'Russia',
        },
        123,
        [
            1,
            {
                country: 'Russia',
                just: 'a nested thing',
                a: [{
                    bad_key: [{
                        country: 'Russia',
                        foo: false,
                    }],
                }],
            },
        ],
    ],
};

// output the initial data
document.getElementById('jsInput').innerHTML = JSON.stringify(obj, null, 2);

// adding some circular link (to fix with our callback)
obj.team[1].loop = obj;

mapNodesRecursively(obj, ({ v, key, obj, isCircular }) => {
    if (isCircular) {
        delete obj[key]; // optionally - we decide to remove circular links
    } else if (v === 'Russia') {
        return 'RU';
    } else if (key.toLocaleLowerCase() === 'foo') {
        return 'BAR';
    } else if (key === 'bad_key') {
        delete obj[key];
        obj['good_key'] = v;
    } else {
        return v;
    }
});

// output the result - processed object
document.getElementById('jsOutput').innerHTML = JSON.stringify(obj, null, 2);

.col {
  display: inline-block;
  width: 40%;
}

<div>
  <h3>Recursive structure modification, keys/values adjustments/replacement</h3>
  <ol>
    <li>
      Replacing "Russia" values with "RU"
    </li>
    <li>
      Setting the value "BAR" for keys "FOO"
    </li>
    <li>
      Changing the key "bad_key" to "good_key"
    </li>
  </ol>
  <div class="col">
    <h4>BEFORE</h4>
    <pre id="jsInput"></pre>
  </div>
  <div class="col">
    <h4>AFTER</h4>
    <pre id="jsOutput"></pre>
  </div>
</div>

- Roman86

Answer 8

我真的很喜欢树搜索！对于今天大多数复杂结构化任务来说，树是一种极为常见的数据结构。所以我刚刚也有类似的任务。我甚至进行了一些深入研究，但实际上并没有发现任何新东西！所以今天我给你带来的是“我如何在现代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);

- xakepp35