我需要使用路径作为子级的参考创建一个嵌套数组。 例如：4.1 是 4 的孩子，4.1.1 是 4.1 的孩子，4.2 是 4 的孩子...... 我有这个平面数组，包含所有数据和路径。创建嵌套数组的最佳方法是什么，其中子级根据其路径嵌套到其父级。
输入：
const list = [
{
location: 1,
path: '4'
},
{
location: 2,
path: '4.1'
},
{
location: 3,
path: '4.1.1'
},
{
location: 4,
path: '4.1.2'
},
{
location: 5,
path: '4.2'
},
{
location: 6,
path: '4.2.1'
},
{
location: 7,
path: '4.3'
},
{
location: 8,
path: '4.3.1'
}
];
输出：
const list = [
{
location: 1,
path: '4',
children: [
{
location: 2,
path: '4.1',
children: [
{
location: 3,
path: '4.1.1'
},
{
location: 4,
path: '4.1.2'
},
]
},
{
location: 5,
path: '4.2',
children: [
{
location: 6,
path: '4.2.1'
},
]
},
{
location: 7,
path: '4.3',
children: [
{
location: 8,
path: '4.3.1'
}
]
},
]
},
];
最好的方法是递归的。 对此算法有什么建议吗？
我很好奇斯科特的链接答案是否能够在不加修改的情况下解决这个问题。确实如此！
import { tree } from './Tree'
import { bind } from './Func'
const parent = (path = "") =>
bind
( (pos = path.lastIndexOf(".")) =>
pos === -1
? null
: path.substr(0, pos)
)
const myTree =
tree // <- make tree
( list // <- array of nodes
, node => parent(node.path) // <- foreign key
, (node, children) => // <- node reconstructor
({ ...node, children: children(node.path) }) // <- primary key
)
console.log(JSON.stringify(myTree, null, 2))
[
{
"location": 1,
"path": "4",
"children": [
{
"location": 2,
"path": "4.1",
"children": [
{
"location": 3,
"path": "4.1.1",
"children": []
},
{
"location": 4,
"path": "4.1.2",
"children": []
}
]
},
{
"location": 5,
"path": "4.2",
"children": [
{
"location": 6,
"path": "4.2.1",
"children": []
}
]
},
{
"location": 7,
"path": "4.3",
"children": [
{
"location": 8,
"path": "4.3.1",
"children": []
}
]
}
]
}
]
Tree模块在这篇文章中共享，以下是提供bind的Func模块 -
// Func.js
const identity = x => x
const bind = (f, ...args) =>
f(...args)
const raise = (msg = "") => // functional throw
{ throw Error(msg) }
// ...
export { identity, bind, raise, ... }
展开下面的代码段以验证浏览器中的结果 -
// Func.js
const bind = (f, ...args) =>
f(...args)
// Index.js
const empty = _ =>
new Map
const update = (r, k, t) =>
r.set(k, t(r.get(k)))
const append = (r, k, v) =>
update(r, k, (all = []) => [...all, v])
const index = (all = [], indexer) =>
all.reduce
( (r, v) => append(r, indexer(v), v)
, empty()
)
// Tree.js
// import { index } from './Index'
function tree (all, indexer, maker, root = null)
{ const cache =
index(all, indexer)
const many = (all = []) =>
all.map(x => one(x))
const one = (single) =>
maker(single, next => many(cache.get(next)))
return many(cache.get(root))
}
// Main.js
// import { tree } from './Tree'
// import { bind } from './Func'
const parent = (path = "") =>
bind
( (pos = path.lastIndexOf(".")) =>
pos === -1
? null
: path.substr(0, pos)
)
const list =
[{location:1,path:'4'},{location:2,path:'4.1'},{location:3,path:'4.1.1'},{location:4,path:'4.1.2'},{location:5,path:'4.2'},{location:6,path:'4.2.1'},{location:7,path:'4.3'},{location:8,path:'4.3.1'}]
const myTree =
tree
( list // <- array of nodes
, node => parent(node.path) // <- foreign key
, (node, children) => // <- node reconstructor
({ ...node, children: children(node.path) }) // <- primary key
)
console.log(JSON.stringify(myTree, null, 2))一种方法是使用将路径映射到对象的中间索引，然后通过在索引中查找每个节点及其父节点来将列表折叠到结构中。 如果没有父对象，则将其添加到根对象中。 最后，我们返回根对象的子对象。 下面是一些代码：
const restructure = (list) => {
const index = list .reduce(
(a, {path, ...rest}) => ({...a, [path]: {path, ...rest}}),
{}
)
return list .reduce((root, {path}) => {
const node = index [path]
const parent = index [path .split('.') .slice(0, -1) .join('.')] || root
parent.children = [...(parent.children || []), node]
return root
}, {children: []}) .children
}
const list = [{location: 1, path: '4'}, {location: 2, path: '4.1' }, {location: 3, path: '4.1.1'}, {location: 4, path: '4.1.2'}, {location: 5, path: '4.2'}, {location: 6, path: '4.2.1'}, {location: 7, path: '4.3'}, {location: 8, path: '4.3.1'}]
console.log (restructure (list)).as-console-wrapper {min-height: 100% !important; top: 0}使用索引意味着我们不必对任何内容进行排序;输入可以按任何顺序排列。
例如，查找父项涉及将"4.3.1"替换为"4.3"并在索引中查找。 当我们尝试"4"，它会查找空字符串，找不到它并使用根节点。
如果你更喜欢正则表达式，你可以使用这个稍微短一点的行：
const parent = index [path.replace (/(^|.)[^.]+$/, '')] || root
但是，您可能还想在最近关于类似问题的答案中查看更优雅的技术。 我的答案是完成工作(有点丑陋的突变(，但这个答案会教你很多关于有效软件开发的知识。
您可以先按路径对对象数组进行排序，以便父级始终位于排序数组中的子级之前。 例如："4"将在"4.1"之前
现在，您可以创建一个对象，其中键是路径。假设"4"已经插入到我们的对象中。
obj = {
'4': {
"location": 1,
"path": "4",
}
}
当我们处理"4.1"时，我们首先检查"4"是否存在于我们的对象中。如果是，我们现在进入它的子对象(如果键"子"不存在，我们创建一个新的空对象(并检查"4.1"是否存在。如果没有，我们插入"4.1">
obj = {
'4': {
"location": 1,
"path": "4",
"children": {
"4.1": {
"location": 2,
"path": "4.1"
}
}
}
}
我们对列表中的每个元素重复此过程。最后，我们只需要递归地将此对象转换为对象数组。
最终代码：
list.sort(function(a, b) {
return a.path - b.path;
})
let obj = {}
list.forEach(x => {
let cur = obj;
for (let i = 0; i < x.path.length; i += 2) {
console.log(x.path.substring(0, i + 1))
if (x.path.substring(0, i + 1) in cur) {
cur = cur[x.path.substring(0, i + 1)]
if (!('children' in cur)) {
cur['children'] = {}
}
cur = cur['children']
} else {
break;
}
}
cur[x.path] = x;
})
function recurse (obj) {
let res = [];
Object.keys(obj).forEach((key) => {
if (obj[key]['children'] !== null && typeof obj[key]['children'] === 'object') {
obj[key]['children'] = recurse(obj[key]['children'])
}
res.push(obj[key])
})
return res;
}
console.log(recurse(obj));
的思维方式与Aadith相同，但采用了迭代方法。我认为最高性能的方法是使用链表结构，然后将其展平。
const list = [
{
location: 1,
path: '4'
},
{
location: 2,
path: '4.1'
},
{
location: 3,
path: '4.1.1'
},
{
location: 4,
path: '4.1.2'
},
{
location: 5,
path: '4.2'
},
{
location: 6,
path: '4.2.1'
},
{
location: 7,
path: '4.3'
},
{
location: 8,
path: '4.3.1'
}
];
let newList = [];
list.forEach((location) =>
{
console.log('Handling location ',location);
if(location.path.split('.').length==1)
{
location.children = [];
newList.push(location);
}
else
{
newList.forEach(loc => {
console.log('checking out: ',loc);
let found = false;
while(!found)
{
console.log(loc.path,'==',location.path.substring(0, location.path.lastIndexOf('.')));
found = loc.path == location.path.substring(0, location.path.lastIndexOf('.'));
if(!found)
{
for(let i=0;i<loc.children.length;i++)
{
let aloc = loc.children[i];
found = aloc.path == location.path.substring(0, location.path.lastIndexOf('.'));
if(found)
{
console.log('found it...', loc);
location.children = [];
aloc.children.push(location);
break;
}
}
}
else
{
console.log('found it...', loc);
location.children = [];
loc.children.push(location);
}
}
} );
}
});
console.log(newList);
这是我快速而肮脏的方式
感谢您的所有建议！ 我绝对可以看到解决我的问题的真正复杂的解决方案。 到一天结束时，我最终创建了自己的"肮脏"解决方案。
这绝对是一种较慢的方法，但对于我的应用程序来说，这个列表不会长到我应该太担心优化的地步。
为了我的问题，我简化了扁平的清单。虽然，实际上该列表比这要复杂一些。我也可以通过我想找到它的孩子的路径。
这是对我有用的解决方案。
function handleNested(list, location) {
return list.map((item) => {
if (item.children && item.children.length > 0) {
item.children = handleNested(item.children, location);
}
if (
location.path.startsWith(item.path) &&
location.path.split(".").length === item.path.split(".").length + 1
) {
return {
...item,
children: item.children ? [...item.children, location] : [location],
};
} else {
return item;
}
});
}
function locationList(path) {
// Filtering the list to remove items with different parent path, and sorting by path depthness.
const filteredList = list
.filter((location) => location.path.startsWith(path))
.sort((a, b) => a.path.length - b.path.length);
let nestedList = [];
// Looping through the filtered list and placing each item under its parent.
for (let i = 0; i < filteredList.length; i++) {
// Using a recursive function to find its parent.
let res = handleNested(nestedList, filteredList[i]);
nestedList = res;
}
return nestedList;
}
locationList("4");