创建嵌套结构的算法

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 开头
如果深度大于最后一个，它必须是最后一个的子节点

我无法让它工作。无限nesting/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);

创建嵌套结构的算法

Algorithm for creating nested structure

algorithm

tree

recursion