从平面数组构建树结构

问题描述 投票:0回答:1

我有一个对象数组。每个都包含一个“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)。

我在这里做错了什么?有没有更好的方法来解决这个问题?

javascript arrays recursion tree
1个回答
0
投票

使用堆栈,其中其当前状态表示带有节点实例的当前级别的路径。将当前节点添加到位于堆栈顶部的父节点的

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
更一致。

© www.soinside.com 2019 - 2024. All rights reserved.