使用键的值获取JSON/JS对象中任意(深度)嵌套节点的引用

Question

我通宵在SO上寻找与我的问题相似的许多帖子，但没有一个能直接解决我的问题。请看下面。

我有一个这样的对象：

let data = [{
   "id": 777,
   "name": "Level 1_section_1",
   "children": [{
       "id": 778,
       "name": "Level 2a",
       "children": [

       ]
     },
     {
       "id": 783,
       "name": "Level 2b",
       "children": [

       ]
     }
   ]
 },
 {
   "id": 786,
   "name": "Level 1_section_2",
   "children": [{
     "id": 781,
     "name": "Level 2c",
     "children": [

     ]
   }]
 }
]

基本上，children 包含一个相同结构的节点数组。

如果我想要获取包含 id:783 的节点的引用，我会直觉地使用递归，但我不知道如何确保它递归地覆盖整个树，直到找到并返回我想要的确切节点，以便我可以将更多的子节点添加到找到的节点中。

尽管来自 CS 背景，但我对递归的了解相当生疏。

这是我在 jsfiddle 中尝试过的内容： https://jsfiddle.net/hanktrizz/surmf7dq/4/

请注意，data 树可能会任意深入（虽然我不希望它超过 8 或 9 层深度），但只是想指出这一点。

- Han K

Answer 1

以下是一个可能的方案，使用递归函数中的 for 循环：

let data=[{id:777,name:"Level 1_section_1",children:[{id:778,name:"Level 2a",children:[]},{id:783,name:"Level 2b",children:[]}]},{id:786,name:"Level 1_section_2",children:[{id:781,name:"Level 2c",children:[]}]}];

const findNode = (arr, idToFind) => {
  for (const item of arr) {
    if (item.id === idToFind) {
      return item;
    }
    const possibleResult = findNode(item.children, idToFind);
    if (possibleResult) {
      return possibleResult;
    }
  }
};

console.log(findNode(data, 778));

- CertainPerformance

---

我真的非常感谢您的及时和有效的回复。在紧迫的期限下工作，但事情并没有顺利进行。祝您有美好的一天。 - Han K

Answer 2

这是一个高阶的findNode函数，不仅限于仅通过id进行搜索。相反，它接受用户定义的lambda表达式，使用任何条件来搜索节点。将其命名为"最初的回答"。

findNode (n => n.id === 778, data)
// { id: 778, name: "Level 2a" }

findNode (n => n.name === "Level 2c", data)
// { id: 781, name: "Level 2c" }

findNode (n => n.id === 999, data)
// undefined

在下面的浏览器中验证您自己的结果 -

最初的回答：

const data =
    [{id:777,name:"Level 1_section_1",children:[{id:778,name:"Level 2a",children:[]},{id:783,name:"Level 2b",children:[]}]},{id:786,name:"Level 1_section_2",children:[{id:781,name:"Level 2c",children:[]}]}];

const None =
  Symbol ()

// findNode : (node -> boolean, node array) -> node?
const findNode = (f, [ node = None, ...nodes ]) =>
  node === None
    ? undefined
    : find1 (f, node) || findNode (f, nodes)

// find1 : (node -> boolean, node) -> node?
const find1 = (f, node = {}) =>
  f (node) === true
    ? node
    : findNode (f, node.children)

console.log (findNode (n => n.id === 778, data))
// { id: 778, name: "Level 2a" }

console.log (findNode (n => n.name === "Level 2c", data))
// { id: 781, name: "Level 2c" }

console.log (findNode (n => n.id === 999, data))
// undefined

以上，解构赋值允许优雅的表达式，但也会创建不必要的中间值。下面的修订是一个重大改进 -

最初的回答：

上面的代码使用了解构赋值，这样可以写出更加简洁的表达式，但同时也会产生一些不必要的中间变量。下面的代码对其进行了改进，使得代码更加高效。

// findNode : (node -> boolean, node array, int) -> node?
const findNode = (f, nodes = [], i = 0) =>
  i >= nodes.length
    ? undefined
    : find1 (f, nodes[i]) || findNode (f, nodes, i + 1)

// find1 : (node -> boolean, node) -> node?
const find1 = (f, node = {}) =>
  f (node) === true
    ? node
    : findNode (f, node.children)

两个版本都提供短路评估，并且在找到第一个结果后立即停止迭代。"Original Answer"的翻译是"最初的回答"。

- Mulan

---

我喜欢谓词的想法。我也将其纳入了我的代码中。 - גלעד ברקן

像往常一样不错！我想知道find1是否最好声明为(f, node, { children = [] } = node) => ...。这样可以让谓词测试children的存在或内容，并返回树中实际节点的引用而不是部分克隆。（或者更简单地说，(f, node) => ... : findNode(f, node.children)。） - Scott Sauyet

感谢您的评论。针对这个特定的答案，简化版本可能更好，因为所有输入节点都似乎具有明确定义的“children”属性。 - Mulan

Answer 3

为了好玩，这里有一个试图返回所有实例的示例。

var data=[{id:777,name:"Level 1_section_1",children:[{id:778,name:"Level 2a",children:[]},{id:786,name:"Level 2b",children:[]}]},{id:786,name:"Level 1_section_2",children:[{id:781,name:"Level 2c",children:[]}]}]

var f = (o, pred, acc=[]) =>
  pred(o) ? [o] : Object.values(o).reduce((a, b) =>
    b && typeof b == 'object' ? a.concat(f(b, pred, acc)) : a, acc)

console.log(JSON.stringify(f(data, o => o.id == 781)))
console.log(JSON.stringify(f(data, o => o.id == 786)))

- גלעד ברקן

Answer 4

这里是使用object-scan的迭代解决方案

主要优点是您可以访问filterFn中的其他数据，并且可以轻松进行进一步处理。显然，引入依赖关系存在权衡。

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

const myData = [{ id: 777, name: 'Level 1_section_1', children: [{ id: 778, name: 'Level 2a', children: [] }, { id: 783, name: 'Level 2b', children: [] }] }, { id: 786, name: 'Level 1_section_2', children: [{ id: 781, name: 'Level 2c', children: [] }] }];

const treeSearch = (data, id) => objectScan(['**(^children$)'], {
  useArraySelector: false,
  abort: true,
  rtn: 'value',
  filterFn: ({ value }) => value.id === id
})(data);

console.log(treeSearch(myData, 778));
// => { id: 778, name: 'Level 2a', children: [] }

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

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

声明：本人是object-scan的作者。

- vincent