我有一个对象数组。每个都包含一个“lv”属性,它是一个 >= 0 的整数。
[
{lv: 0, name: "A"},
{lv: 1, name: "B"},
{lv: 1, name: "C"},
{lv: 2, name: "D"},
{lv: 3, name: "E"},
{lv: 1, name: "F"},
{lv: 0, name: "G"},
]
这是从旧软件导出的,表示树结构:“lv”表示节点的深度,它在树中的位置始终相对于数组中的前一个节点。所以第一个对象(A)是级别0(根); B 是级别 1,因此是前一个级别 0 条目 (A) 的子项; C 也是级别 1,因此是 B 的兄弟(也是 A 的子级);等等。最终的结构如下所示:
├ A
│ ├ B
│ ├ C
│ │ └ D
│ │ └ E
│ └ F
└ G
我想编写一个函数来将这个平面数组转换为更能反映树结构的结构,如下所示:
[
{
name: "A",
children: [
{
name: "B",
children: null
},
{
name: "C",
children: [
{
name: "D",
children: [
{
name: "E",
children: null
}
]
}
]
},
{
name: "F",
children: null
}
]
},
{
name: "G",
children: null
}
]
所以基本上每个节点都将其子节点递归地列在“children”属性下的数组中。
我编写了以下递归函数,但当遇到一个备份树的节点时,它会中断(例如,在 3 级节点之后出现 1 级节点):
function buildTree(arr) {
let siblings = [], children = null
while (arr.length) {
let node = arr.shift()
if (arr.length) {
let nodeLv = +node.lv
let nextNodeLv = +arr[0].lv
if (nextNodeLv > nodeLv) {
children = buildTree(arr)
}
}
let newNode = {
name: node.name,
children: children
}
siblings.push(newNode)
}
return siblings
}
这给了我以下结构,而不是上图所示的结构:
└ A
├ B
└ C
└ D
└ E
└ F
└ G
所以基本上,当构建更深时它工作得很好,但不能走相反的路(从E到F或F到G)。
我在这里做错了什么?有没有更好的方法来解决这个问题?
使用堆栈,其中其当前状态表示带有节点实例的当前级别的路径。将当前节点添加到位于堆栈顶部的父节点的
children
列表中。当级别降低时,从该堆栈中弹出节点。
function makeHierarchy(flat) {
const hierarchy = [];
const stack = [{children: hierarchy}];
for (const {lv, name} of flat) {
while (lv < stack.length - 1) stack.pop();
const obj = {name, children: []};
stack.at(-1).children.push(obj);
stack.push(obj);
}
return hierarchy;
}
// Demo with data from question
const flat = [{lv: 0, name: "A"},{lv: 1, name: "B"},{lv: 1, name: "C"},{lv: 2, name: "D"},{lv: 3, name: "E"},{lv: 1, name: "F"},{lv: 0, name: "G"},];
const hierarchy = makeHierarchy(flat);
console.log(hierarchy);
请注意,此处叶节点的
children
属性设置为空数组。在这种情况下,这似乎比使用 null
更一致。