JavaScript 没有 parent id 的平面列表到树？

Question

这个问题建立在许多类似的问题之上，例如 Construct hierarchy tree from flat list with parent field?

然而，扭曲的是没有 parent id。例如

[
{id: 1, depth: 1, ...},
{id: 2, depth: 2, ...},
{id: 3, depth: 3, ...},
{id: 4, depth: 2, ...},

{id: 5, depth: 1, ...},
{id: 6, depth: 2, ...},
{id: 7, depth: 2, ...},

{id: 8, depth: 1, ...},
{id: 9, depth: 2, ...},


{id: 10, depth: 3, ...},
{id: 11, depth: 3, ...},
]

构建以下树的高效方法是什么？请注意 children 总是在 parent 之后，即可以从 depth 值看到树。例如，id 2 是 id 1 的 child，因为它的深度是 2 而 id 1 的深度是 1。id 3 是 child of id 2 因为 id 3 的深度为 3。id 4 是 id 1 的 child not id 3 因为 id 4 的深度为 2（比 id 3 的深度为 3

\tree digram
1
  2
    3
  4
5
  6
  7
8
  9
    10
    11

应该有像

这样的值

[
{id:1, depth:1, children: [
  {id: 2, depth: 2, children: [...]},
  ...
]},
{id:5, depth:1, children: [...]},
{id:6, depth:1, children: [...]},
]

Answer 1

您可以为此使用一个数组，每个深度都有一个索引。每时每刻，它都代表一条从（虚拟）根节点到当前节点的路径。当处理一个节点时，它的父节点将位于索引 depth-1，它可以插入到该父节点的 children 属性，节点本身将位于索引 depth ]:

function createForest(flatdata) {
    const path = [{ children: [] }];
    for (const obj of flatdata) {
        path[obj.depth - 1].children.push(path[obj.depth] = { ...obj, children: [] });
    }
    return path[0].children;
}

// demo
const flatdata = [{id: 1, depth: 1},{id: 2, depth: 2},{id: 3, depth: 3},{id: 4, depth: 2},{id: 5, depth: 1},{id: 6, depth: 2},{id: 7, depth: 2},{id: 8, depth: 1},{id: 9, depth: 2},{id: 10, depth: 3},{id: 11, depth: 3}];
const roots = createForest(flatdata);

console.log(roots);

不规则深度

如果depth值与节点的实际深度不对应，而是留有间隙，则使用“字典”（普通对象）来记录 depth 属性值的映射，它们对应真实深度：

function createForest(flatdata) {
    const path = [{ children: [] }];
    const depthMap = { 0: 0 };
    for (const obj of flatdata) {
        path[(depthMap[obj.depth] ??= path.length) - 1].children.push(
            path[depthMap[obj.depth]] = { ...obj, children: []}
        );
    }
    return path[0].children;
}

// demo
const flatdata = [{id: 1, depth: 10},{id: 2, depth: 20},{id: 3, depth: 30},{id: 4, depth: 20},{id: 5, depth: 10},{id: 6, depth: 20},{id: 7, depth: 20},{id: 8, depth: 10},{id: 9, depth: 20},{id: 10, depth: 30},{id: 11, depth: 30}];
const roots = createForest(flatdata);

console.log(roots);

然而，如果唯一的不规则是深度并不总是从 1 开始，但有时从 2 开始，那么在输入数据前加上一个虚拟 depth-one 节点会更有效，使用第一个函数，然后从结果中删除虚拟“root”（深度为 1）。

Answer 2

遍历数组并将每个项目添加到树以及面包屑路径中。每个下一个项目要么作为最后一个项目的子项，要么通过面包屑路径回溯到需要插入的正确深度：

const peek = arr =>
  arr[arr.length-1];

function toTree(arr) {
  const tree = [];
  const trail = [];
  
  for (const item of arr) {
    while ((peek(trail)?.depth ?? 0) >= item.depth) {
      trail.pop();
    }
    const current = peek(trail)?.children ?? tree;
    const treeNode = {...item, children: []};
    current.push(treeNode);
    trail.push(treeNode);
  }
  
  return tree;
}


const array = [
  {id: 1, depth: 1, },
  {id: 2, depth: 2, },
  {id: 3, depth: 3, },
  {id: 4, depth: 2, },

  {id: 5, depth: 1, },
  {id: 6, depth: 2, },
  {id: 7, depth: 2, },

  {id: 8, depth: 1, },
  {id: 9, depth: 2, },

  {id: 10, depth: 3  },
  {id: 11, depth: 3  },  
]

console.log(toTree(array));

此解决方案克隆每个项目，以添加 .children 属性。如果不需要克隆，item可以直接变异

Answer 3

您可以获取最后插入的对象的数组。

const
    data = [{ id: 1, depth: 1 }, { id: 2, depth: 2 }, { id: 3, depth: 3 }, { id: 4, depth: 2 }, { id: 5, depth: 1 }, { id: 6, depth: 2 }, { id: 7, depth: 2 }, { id: 8, depth: 1 }, { id: 9, depth: 2 }, { id: 10, depth: 3 }, { id: 11, depth: 3 }],
    result = data.reduce((r, { depth, ...o }) => {
        r[depth - 1].push({ ...o, children: r[depth] = [] });
        return r;
    }, [[]])[0];

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

JavaScript 没有 parent id 的平面列表到树？

JavaScript flat list to tree WITHOUT parent id?

javascript

arrays

tree

不规则深度