Javascript:在树中找到元素的所有父对象 [英] Javascript: Find all parents for element in tree

问题描述

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

I have the objects tree, and i can't found all parents for concrete object id. Imagine i need to add some new field to each parent for object with id = 5. Can someone help please with recursive loop through tree

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

推荐答案

数据构造函数

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

People need to stop writing data like this:

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 字段的统一接口，以便以后可以将其与其他通用数据区分开来

This allows you to separate your mind from details like whether {}, or [] or even x => ... is used to contain your data. I would go just one step further and create a uniform interface with a guaranteed tag field – so that it could later be distinguished from other generic datum

在下面的此程序中，堆栈片段屠宰输出是完美的.无关紧要 打印出时数据是什么样子– 重要的是我们人类很容易在我们的程序，我们的程序很容易读/写

It's perfect that stack-snippets butchers the output in this program below. It does not matter what the data looks like when printed out – what matters is it's easy for us humans to read/write in our program, and it's easy for our program to read/write

当/如果您需要特定的格式/形状，请将其强制为然后的形状；在此之前，请保持良好的易用性

When/if you need it in a specific format/shape, coerce it into that shape then; until that point, keep it nice an easy to work with

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] 样式的查找直接索引读取–只是函数和调用；我们不必担心其他任何噪音

We can write search with a simple loop helper function – but notice what you're not seeing; almost no logic (a single ternary expression is used); no imperative constructs like for/while or manual iterator incrementing like i++; no use of mutators like push/unshift or effectful functions like .forEach; no senseless inspection of .length property or direct index reads using [i]-style lookups – it's just functions and calls; we don't have to worry about any of that other noise

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 返回路径的 array ，其中每个路径都是节点的 array –为什么会这样?如果ID为 X 的孩子出现在树中的多个位置，则将返回该孩子的 all 个路径

So search returns an array of paths, where each path is an array of nodes – why is this the case? In the event a child with an ID of X appears in multiple locations in the tree, all paths to the child will be returned

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 ] ]

您不小心写了列表monad

列表monad对模棱两可的计算的思想进行了编码-即，可以返回一个或多个结果的计算的思想.让我们对程序进行一些小的更改-这是有优势的，因为 List 是通用的，现在可以在程序中其他此类计算必不可少的地方使用

The list monad encodes the idea of ambiguous computations – that is, the idea of a computation that can return one or more result. Let's make a small change to our program - this is advantageous because List is generic and now can be used other places in our program where this kind of computation is essential

如果您喜欢此解决方案，则可能会喜欢阅读我的其他有关列表monad的答案

If you like this solution, you will probably enjoy reading my other answers that talk about the 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 ] ]

这篇关于Javascript:在树中找到元素的所有父对象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！