嵌套结构的生成算法

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" }
  ]
}

我正在寻找一种算法，如何从深度创建一个类似父子嵌套的结构。

{
  "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": [],
      }]
    }]
  }
]}

逻辑是这样的：

• 假设：列表中的第一项总是以深度=0开头
• 如果深度大于最后一个，它必须是最后一个的孩子

我没法让它工作。它应该是递归的，具有无限嵌套/深度级别。

谢谢你们的帮助！

Answer 1

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

下面是一个可运行的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);