创建嵌套结构的算法

Question

我有以下结构:

{
"list": [
{ "depth": 0, "data": "lorem1" },
{ "depth": 1, "data": "lorem2" },
{ "depth": 2, "data": "lorem3" },
{ "depth": 2, "data": "lorem4" },
{ "depth": 0, "data": "lorem5" },
{ "depth": 1, "data": "lorem6" },
{ "depth": 1, "data": "lorem7" },
{ "depth": 2, "data": "lorem8" }
]
}

我正在寻找一种关于如何从depth创建亲子式嵌套结构的算法。

{
"list": [{
"depth": 0,
"data": "lorem1",
"children": [{
"depth": 1,
"data": "lorem2",
"children": [{
"depth": 2,
"data": "lorem3",
"children": [],
}, {
"depth": 2,
"data": "lorem4",
"children": [],
}]
}]
}, {
"depth": 0,
"data": "lorem5",
"children": [{
"depth": 1,
"data": "lorem6",
"children": [],
}, {
"depth": 1,
"data": "lorem7",
"children": [{
"depth": 2,
"data": "lorem8",
"children": [],
}]
}]
}
]}

逻辑如下:

• 假设:列表中的第一项总是以depth=0开头
• 如果depth大于最后一个，它必须是最后一个的子节点

我不能让这个工作。它应该是递归的，以具有无限的嵌套/深度级别。

谢谢大家的帮助!

Answer 1

可以使用堆栈来跟踪树中的当前路径。当深度从一个节点增加到下一个节点时，将新节点也推到该堆栈上。如果没有，则从堆栈中弹出项，直到达到正确的深度。然后，您始终知道需要在哪个children集合中添加新节点。

下面是一个可运行的JavaScript实现:

function algo(list) {
// Create a dummy node to always stay at the bottom of the stack:
let stack = [
{ "depth": -1, "data": "(root)", "children": [] }
];

for (let node of list) {
let newNode = { ...node, children: [] }; // Copy and add children property
if (newNode.depth >= stack.length || newNode.depth < 0) throw "Invalid depth";
while (newNode.depth < stack.length - 1) stack.pop();
stack[stack.length - 1].children.push(newNode);
stack.push(newNode);
}

return stack[0].children;
}
// Demo
let data = {
"list": [
{ "depth": 0, "data": "lorem1" },
{ "depth": 1, "data": "lorem2" },
{ "depth": 2, "data": "lorem3" },
{ "depth": 2, "data": "lorem4" },
{ "depth": 0, "data": "lorem5" },
{ "depth": 1, "data": "lorem6" },
{ "depth": 1, "data": "lorem7" },
{ "depth": 2, "data": "lorem8" }
]
}
// Create a new structure, and load the transformed list in its list property:
let result = {
"list": algo(data.list)
};
// Show result
console.log(result);

回答您的请求，这样做没有虚拟节点:

function algo(list) {
let result = [];
let stack = [];

for (let node of list) {
let newNode = { ...node, children: [] }; // Copy and add children property
if (newNode.depth > stack.length || newNode.depth < 0) throw "Invalid depth";
while (newNode.depth < stack.length) stack.pop();
if (!stack.length) result.push(newNode);
else stack[stack.length - 1].children.push(newNode);
stack.push(newNode);
}

return result;
}
// Demo
let data = {
"list": [
{ "depth": 0, "data": "lorem1" },
{ "depth": 1, "data": "lorem2" },
{ "depth": 2, "data": "lorem3" },
{ "depth": 2, "data": "lorem4" },
{ "depth": 0, "data": "lorem5" },
{ "depth": 1, "data": "lorem6" },
{ "depth": 1, "data": "lorem7" },
{ "depth": 2, "data": "lorem8" }
]
}
// Create a new structure, and load the transformed list in its list property:
let result = {
"list": algo(data.list)
};
// Show result
console.log(result);