Javascript:查找树中元素的所有父项 [英] Javascript: Find all parents for element in tree
问题描述
我有对象树,但我无法找到具体对象 ID 的所有父对象.想象一下,我需要为 id = 5 的对象的每个父级添加一些新字段.有人可以帮忙通过树进行递归循环
var tree = {编号:1,孩子们: [{编号:3,父 ID:1,孩子们: [{编号:5,父 ID:3,孩子们: []}]}]}控制台日志(搜索树(树,5));功能搜索树(树,nodeId){for (让 i = 0; i
数据构造函数
人们需要停止这样写数据:
const 树 ={ id: 1, parentId: null, children:[ { id: 3, parentId: 1, 孩子:[ { id: 5, parentId: 3, children: [] } ] } ] }
并开始使用数据构造函数
写入数据//节点"数据构造函数const Node = (id, parentId = null, children = Children()) =>({ id, parentId, children })//儿童"数据构造函数const Children = (...values) =>价值观//写入复合数据常量树 =节点(1,空,子节点(节点 (3, 1,子节点(节点 (5, 3)))))控制台日志(树)//{ id: 1, parentId: null, children: [ { id: 3, parentId: 1, children: [ { id: 5, parentId: 3, children: [] } ] } ] }
预>
这使您可以将自己的想法与诸如 {}
或 []
甚至 x => 等细节分开....
用于包含您的数据.我会更进一步,创建一个具有保证 tag
字段的统一接口 - 以便以后可以将其与其他通用数据区分开来
stack-snippets 在下面的程序中处理输出是完美的.打印出来的数据是什么样子并不重要打印出来 - 重要的是我们人类很容易在我们的中读/写>program,我们的程序很容易读/写
当/如果您需要特定格式/形状的它,将其强制为该形状然后;在那之前,请保持良好的易用性
const Node = (id, parentId = null, children = Children()) =>({标签:节点,id,parentId,children})const Children = (...values) =>({标签:儿童,价值观})//写入复合数据常量树 =节点(1,空,子节点(节点 (3, 1,子节点(节点 (5, 3)))))控制台日志(树)//{ ... 非常丑陋的输出,但谁在乎!.. }
开始搜索
我们可以用一个简单的loop
辅助函数来编写search
——但是请注意您没有看到的内容;几乎没有逻辑(使用单个三元表达式);没有像 for
/while
这样的命令式结构或像 i++
这样的手动迭代器递增;不使用像 push
/unshift
这样的修改器或像 .forEach
这样的有效函数;没有对 .length
属性的无意义检查或使用 [i]
样式查找的直接索引读取——它只是函数和调用;我们不必担心任何其他噪音
const Node = (id, parentId = null, children = Children()) =>({标签:节点,id,parentId,children})const Children = (...values) =>({标签:儿童,价值观})常量树 =节点(1,空,子节点(节点 (3, 1,子节点(节点 (5, 3)))))const search = (id, tree = null) =>{const loop = (path, node) =>node.id === id?[小路]: node.children.values.reduce ((acc, child) =>acc.concat (loop ([...path, node], child)), [])返回循环([],树)}常量路径 =搜索(5,树)console.log (paths.map (path => path.map (node => node.id)))//[ 1, 3 ]
所以 search
返回一个 array 路径,其中每个路径都是一个 array 节点——为什么会这样?如果 ID 为 X
的孩子出现在树中的多个位置,所有到孩子的路径将被返回
const Node = (id, parentId = null, children = Children()) =>({标签:节点,id,parentId,children})const Children = (...values) =>({标签:儿童,价值观})常量树 =节点(0,空,儿童(节点 (1, 0, 子节点 (Node (4, 1))),节点 (2, 0, Children (Node (4, 2))),节点 (3, 0, Children (Node (4, 3)))))const search = (id, tree = null) =>{const loop = (path, node) =>node.id === id?[小路]: node.children.values.reduce ((acc, child) =>acc.concat (loop ([...path, node], child)), [])返回循环([],树)}常量路径 =搜索(4,树)console.log (paths.map (path => path.map (node => node.id)))//[ [ 0, 1 ],//[ 0, 2 ],//[ 0, 3 ] ]
你不小心写了列表单子
list monad 编码了模糊计算的思想——也就是说,可以返回一个或多个结果的计算思想.让我们对我们的程序做一个小改动——这是有利的,因为 List
是通用的,现在可以在我们程序中需要这种计算的其他地方使用
如果你喜欢这个解决方案,你可能会喜欢阅读我关于列表单子的其他答案
const List = (xs = []) =>({标签:列表,价值:xs,链:f =>列表 (xs.reduce ((acc, x) =>acc.concat (f (x) .value), []))})const Node = (id, parentId = null, children = Children()) =>({标签:节点,id,parentId,children})const Children = (...values) =>列表(值)const search = (id, tree = null) =>{const loop = (path, node) =>node.id === id?列表([路径]): node.children.chain (child =>循环 ([...path, node], child))返回循环 ([], tree) .value}常量树 =节点(0,空,儿童(节点 (1, 0, 子节点 (Node (4, 1))),节点 (2, 0, Children (Node (4, 2))),节点 (3, 0, Children (Node (4, 3)))))常量路径 =搜索(4,树)console.log (paths.map (path => path.map (node => node.id)))//[ [ 0, 1 ],//[ 0, 2 ],//[ 0, 3 ] ]
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);
}
}
}
}
data constructors
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: [] } ] } ] }
and start writing data using data constructors
// "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: [] } ] } ] }
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 !.. }
let's get searching
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 ]
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 ] ]
you accidentally wrote the list monad
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
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屋!