Javascript：在树中查找元素的所有父项

Question

我有对象树，但找不到具体对象 ID 的所有父对象。想象一下，我需要为 id = 5 的对象的每个父对象添加一些新字段。有人可以帮助递归循环遍历树吗

 var tree = {
  id: 1,
  children: [
  	{
		id: 3,
		parentId: 1,
		children: [
		  	{
				id: 5,
				parentId: 3,
				children: []
			}
		]
	}
  ]
}

console.log(searchTree (tree, 5));

function searchTree (tree, nodeId){
      for (let i = 0; i < tree.length; i++){
        if (tree[i].id == nodeId) {
            // it's parent
            console.log(tree[i].id);
            tree[i].newField = true;
            if (tree[i].parentId != null) {
              searchTree(tree, tree[i].parentId);
            }
        }
      }
 }

原文由 Lemmy 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

数据构造器

人们需要停止这样写数据：

 const tree =
  { id: 1, parentId: null, children:
    [ { id: 3, parentId: 1, children:
      [ { id: 5, parentId: 3, children: [] } ] } ] }

并开始使用 数据构造函数 写入数据

 // "Node" data constructor
const Node = (id, parentId = null, children = Children ()) =>
  ({ id, parentId, children })

// "Children" data constructor
const Children = (...values) =>
  values

// write compound data
const tree =
  Node (1, null,
    Children (Node (3, 1,
      Children (Node (5, 3)))))

console.log (tree)
// { id: 1, parentId: null, children: [ { id: 3, parentId: 1, children: [ { id: 5, parentId: 3, children: [] } ] } ] }

这使您可以将自己的想法与细节分开，例如 {} 或 [] 甚至 x => ... 是否用于包含您的数据。我会更进一步，创建一个具有保证 tag 字段的统一接口——以便以后可以将其与其他通用数据区分开来

stack-snippets 屠杀下面这个程序中的输出是完美的。 打印出来 的数据是什么样子 _并不重要_—— 重要的是 我们人类很容易在我们的 程序 中读/写，而且我们的程序很容易 读/ 写

当/如果您需要特定格式/形状的它， 则将 其强制为该形状；在那之前，保持它很好用

 const Node = (id, parentId = null, children = Children ()) =>
  ({ tag: Node, id, parentId, children })

const Children = (...values) =>
  ({ tag: Children, values })

// write compound data
const tree =
  Node (1, null,
    Children (Node (3, 1,
      Children (Node (5, 3)))))

console.log (tree)
// { ... really ugly output, but who cares !.. }

---

让我们开始搜索

我们可以用一个简单的 loop 辅助函数来编写 search --- 辅助函数——但请注意你 没有 看到什么；几乎没有逻辑（使用单个三元表达式）；没有像 for / while 这样的命令式构造，也没有像 i++ 这样的手动递增迭代器；不使用 push / unshift 或有效函数 .forEach ；没有毫无意义地检查 .length 属性或使用 [i] 样式查找的直接索引读取——它只是函数和调用；我们不必担心任何其他噪音

 const Node = (id, parentId = null, children = Children ()) =>
  ({ tag: Node, id, parentId, children })

const Children = (...values) =>
  ({ tag: Children, values })

const tree =
  Node (1, null,
    Children (Node (3, 1,
      Children (Node (5, 3)))))

const search = (id, tree = null) =>
  {
    const loop = (path, node) =>
      node.id === id
        ? [path]
        : node.children.values.reduce ((acc, child) =>
            acc.concat (loop ([...path, node], child)), [])
    return loop ([], tree)
  }

const paths =
  search (5, tree)

console.log (paths.map (path => path.map (node => node.id)))
// [ 1, 3 ]

所以 search 返回一个路径 _数组_，其中每个路径都是一个节点 _数组_——为什么会这样？如果 ID 为 X 的孩子出现在树中的 多个 位置，则返回该孩子的 所有 路径

 const Node = (id, parentId = null, children = Children ()) =>
  ({ tag: Node, id, parentId, children })

const Children = (...values) =>
  ({ tag: Children, values })

const tree =
  Node (0, null, Children (
    Node (1, 0, Children (Node (4, 1))),
    Node (2, 0, Children (Node (4, 2))),
    Node (3, 0, Children (Node (4, 3)))))

const search = (id, tree = null) =>
  {
    const loop = (path, node) =>
      node.id === id
        ? [path]
        : node.children.values.reduce ((acc, child) =>
            acc.concat (loop ([...path, node], child)), [])
    return loop ([], tree)
  }

const paths =
  search (4, tree)

console.log (paths.map (path => path.map (node => node.id)))
// [ [ 0, 1 ],
//   [ 0, 2 ],
//   [ 0, 3 ] ]

---

你不小心写了 list monad

列表 monad 编码了 模棱两可的计算 的想法——也就是说，可以返回一个或多个结果的计算的想法。让我们对我们的程序做一个小改动 - 这是有利的，因为 List 是通用的，现在可以在我们程序中需要这种计算的其他地方使用

如果你喜欢这个解决方案，你可能会喜欢阅读 我关于列表 monad 的其他答案

 const List = (xs = []) =>
  ({
    tag:
      List,
    value:
      xs,
    chain: f =>
      List (xs.reduce ((acc, x) =>
        acc.concat (f (x) .value), []))
  })

const Node = (id, parentId = null, children = Children ()) =>
  ({ tag: Node, id, parentId, children })

const Children = (...values) =>
  List (values)

const search = (id, tree = null) =>
  {
    const loop = (path, node) =>
      node.id === id
        ? List ([path])
        : node.children.chain (child =>
            loop ([...path, node], child))
    return loop ([], tree) .value
  }

const tree =
  Node (0, null, Children (
    Node (1, 0, Children (Node (4, 1))),
    Node (2, 0, Children (Node (4, 2))),
    Node (3, 0, Children (Node (4, 3)))))

const paths =
  search (4, tree)

console.log (paths.map (path => path.map (node => node.id)))
// [ [ 0, 1 ],
//   [ 0, 2 ],
//   [ 0, 3 ] ]

原文由 Mulan 发布，翻译遵循 CC BY-SA 3.0 许可协议