通过直接路径在树中查找路径 [英] Find path in tree by direct path
问题描述
我有类似的问题:JavaScript:查找所有树递归中元素的父项
但我不是通过 name 找到路径，而是通过 direct path 找到路径.
But I don't find path by name but by direct path.
const path = ["name1", "name4", "name5"];
const data = [
{
'name': 'name1',
'tree': [
{'name': 'name2'},
{'name': 'name3'},
{
'name': 'name4',
'tree': [
{'name': 'name5'},
{'name': 'name6'}
]
},
{'name': 'name7'}
]
},
{
'name': 'name8',
'tree': [
{'name': 'name9'}
]
}
];
它返回所有可能的路径或什么都不返回.
It returns every possible path or nothing.
当path太短时，它什么都不返回.
When path is too short, it returns nothing.
当path太长时，它什么都不返回.
When path is too long, it returns nothing.
感谢您的帮助！
所需输出的示例:
const path = ["name1", "name4", "name5"];
findAPath(data, path)
返回:["name1", "name4", "name5"]
const path = ["name1", "name7", "name5"];
findAPath(data, path)
返回[]
const path = ["name1", "name4", "name5", "name5"];
findAPath(data, path)
返回[]
我的尝试:
let index = 0;
function find(data, index) {
let index = index;
data.some((o) => {
if(o.name == path[index]) {
index++;
find(o.tree, index);
}
});
// I don't know what return here.
// I need to probably return path where I am.
return <>;
}
推荐答案
using Array.prototype.flatMap
这是一个使用相互递归技术的函数式解决方案 -
Here's a functional solution using a mutual recursion technique -
const None =
Symbol ()
const findPath = (tree = [], names = [], r = []) =>
tree.length && names.length // base: and
? tree.flatMap(branch => findPath1(branch, names, r))
: tree.length || names.length // inductive: xor
? []
: [ r ] // inductive: nor // inductive: nor
const findPath1 = ({ name = "", tree = [] } = {}, [ q = None, ...more ] = [], r = []) =>
name === "" && q === None // base: and
? [ r ]
: name === "" || q === None || name !== q // inductive: xor
? []
: findPath(tree, more, [ ...r, q ]) // inductive: nor
findPath(data, ["name1", "name4", "name5"])
// => [ [ "name1", "name4", "name5" ] ]
注意如果您的数据包含多个输入值的路径，所有路径将被返回 -
NB if your data contains multiple paths to the input values, all paths will be returned -
const data = [
{
'name': 'name1', // name1
'tree': [
{'name': 'name2'},
{'name': 'name3'},
{
'name': 'name4', // name1->name4
'tree': [
{'name': 'name5'}, // name1->name4->name5
{'name': 'name6'}
]
},
{
'name': 'name4', // name1->name4
'tree': [
{'name': 'name5'}, // name1->name4->name5
{'name': 'name6'}
]
},
{'name': 'name7'}
]
},
{
'name': 'name8',
'tree': [
{'name': 'name9'}
]
}
]
就像你问的那样，它返回所有可能的路径，或者什么都不返回 -
Just like you asked, it returns every possible path, or nothing -
findPath(data, ["name1", "name4", "name5"])
// => [ [ "name1", "name4", "name5" ],
// [ "name1", "name4", "name5" ] ]
findPath(data, [ "name1", "name7" ])
// => [ [ "name1", "name7" ] ]
findPath(data, [ "name1", "name9" ])
// => []
当一条路径太短或太长时，它不会返回任何东西-
When a path is too short or too long, it will return nothing -
findPath(data, [ "name1", "name4" ])
// => []
findPath(data, [ "name1", "name4", "name5", "name6" ])
// => []
展开下面的代码片段以在您自己的浏览器中验证结果 -
Expand the snippet below to verify the results in your own browser -
const None =
Symbol ()
const findPath = (tree = [], names = [], r = []) =>
tree.length && names.length
? tree.flatMap(branch => findPath1(branch, names, r))
: tree.length || names.length
? []
: [ r ]
const findPath1 = ({ name = "", tree = [] } = {}, [ q = None, ...more ] = [], r = []) =>
name === "" && q === None
? [ r ]
: name === "" || q === None || name !== q
? []
: findPath(tree, more, [ ...r, q ])
const data = [
{
'name': 'name1',
'tree': [
{'name': 'name2'},
{'name': 'name3'},
{
'name': 'name4',
'tree': [
{'name': 'name5'},
{'name': 'name6'}
]
},
{'name': 'name7'}
]
},
{
'name': 'name8',
'tree': [
{'name': 'name9'}
]
}
]
console.log(findPath(data, ["name1", "name4", "name5"]))
// [ [ "name1", "name4", "name5" ] ]
console.log(findPath(data, [ "name1", "name7" ]))
// [ [ "name1", "name7" ] ]
console.log(findPath(data, [ "name1", "name9" ]))
// []使用生成器
这是使用生成器的替代实现 -
Here's an alternative implementation using generators -
const None =
Symbol ()
const findPath = function* (tree = [], names = [], r = [])
{ if (tree.length && names.length) // base: and
for (const branch of tree)
yield* findPath1(branch, names, r)
else if (tree.length || names.length) // inductive: xor
return
else // inductive: nor
yield r
}
const findPath1 = function* ({ name = "", tree = [] } = {}, [ q = None, ...more ] = [], r = [])
{ if (name === "" && q === None) // base: and
yield r
else if (name === "" || q === None || name !== q) // inductive: xor
return
else // inductive: nor
yield* findPath(tree, more, [ ...r, q ])
}
它和上面的输出完全一样，只是将可迭代生成器强制转换为数组，我们使用Array.from -
It has the exact same output as above, only to coerce the iterable generator into an array, we use Array.from -
Array.from(findPath(data, ["name1", "name4", "name5"]))
// => [ [ "name1", "name4", "name5" ] ]
Array.from(findPath(data, [ "name1", "name7" ]))
// => [ [ "name1", "name7" ] ]
Array.from(findPath(data, [ "name1", "name9" ]))
// => []
展开下面的代码片段以在您自己的浏览器中验证结果 -
Expand the snippet below to verify the results in your own browser -
const None =
Symbol ()
const findPath = function* (tree = [], names = [], r = [])
{ if (tree.length && names.length)
for (const branch of tree)
yield* findPath1(branch, names, r)
else if (tree.length || names.length)
return
else
yield r
}
const findPath1 = function* ({ name = "", tree = [] } = {}, [ q = None, ...more ] = [], r = [])
{ if (name === "" && q === None)
yield r
else if (name === "" || q === None || name !== q)
return
else
yield* findPath(tree, more, [ ...r, q ])
}
const data = [
{
'name': 'name1',
'tree': [
{'name': 'name2'},
{'name': 'name3'},
{
'name': 'name4',
'tree': [
{'name': 'name5'},
{'name': 'name6'}
]
},
{'name': 'name7'}
]
},
{
'name': 'name8',
'tree': [
{'name': 'name9'}
]
}
]
console.log(Array.from(findPath(data, ["name1", "name4", "name5"])))
// [ [ "name1", "name4", "name5" ] ]
console.log(Array.from(findPath(data, [ "name1", "name7" ])))
// [ [ "name1", "name7" ] ]
console.log(Array.from(findPath(data, [ "name1", "name9" ])))
// []它们是如何相同的；他们怎么不
注意两个实现之间的相似性以及结果的形成方式.两者都使用相互递归.函数式解决方案使用表达式，而生成器解决方案使用语句.生成器实现扩展了一个明显的优势，我们可以随时选择停止或继续迭代(查找").
Note the similarity between the two implementations and how the result is formed. Both use mutual recursion. The functional solution uses expressions whereas the generator solution uses statements. The generator implementation extends a distinct advantage where by we can chose to stop or continue iteration ("finding") whenever we want.
例如，想象一个输入，其中给定输入有十 (10) 条唯一路径.也许我们只想返回第一场比赛，
For example, imagine an input where there are ten (10) unique paths for the given input. Perhaps we want to just return the first match,
const findFirst = (tree = [], names = []) =>
{ for (const path of findPath(tree, names))
return path
}
或者获得前三 (3) 场比赛 -
Or get the first three (3) matches -
const findFirst3 = (tree = [], names = []) =>
{ const r = []
for (const path of findPath(tree, names))
if (r.length < 3)
r.push(path)
return r
}
或者得到第一个N -
const findFirstN = (tree = [], names = [], n = 0) =>
{ const r = []
for (const path of findPath(tree, names))
if (r.length < n)
r.push(path)
return r
}
生成器是这样灵活的.相比之下，flatMap 实现是急切的，并且总是返回所有结果.
Generators are flexible like this. By contrast, the flatMap implementation is eager and always returns all results.
这篇关于通过直接路径在树中查找路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
