数据结构转换

Question

如何转换父关系数组结构

const array = [{id: 1, parentId: 2}, {parentId: null, id: 2}];

到一个二维数组，其中嵌套数组的第一个元素是没有 parentId 的父元素，最后一个元素是 child/leaf 元素。

例如：

const array_2 = [
  [{ id: 1, parentId: null}, { id:2, parentId: 1 }, { id: 3, parentId: 2}], [...], [...]
]

Answer 1

如果我没理解错的话，你想收集从树的根节点到每个节点的路径：

const nodes = [
  {id: 1, parentId: 6},
  {id: 2, parentId: 1},
  {id: 3, parentId: 4},
  {id: 4, parentId: 6},
  {id: 5, parentId: 1},
  {id: 6, parentId: null}, // Root
  {id: 7, parentId: 2},
];

const nodeMap = new Map(nodes.map(node => [node.id, node]));
const paths = nodes.map(node => {
  const path = [{...node}]; // Or: const path = [node];
  let parentId = node.parentId;
  while (parentId !== null) {
    const parentNode = nodeMap.get(parentId);
    if (parentNode === undefined) {
      throw new Error(`No node exists with ID ${parentId}`);
    }
    path.unshift({...parentNode}); // Or: path.unshift(parentNode);
    parentId = parentNode.parentId;
  }
  return path;
});
console.log(paths);

这是我在上面的代码中使用的示例树：

从根到每个节点的路径：

Node-1: 6 <- 1
Node-2: 6 <- 1 <- 2
Node-3: 6 <- 4 <- 3
Node-5: 6 <- 1 <- 5
Node-6: 6
Node-7: 6 <- 1 <- 2 <- 7

...这就是我的代码 returns 作为二维 JavaScript 数组的内容。

数据结构转换

Data structure conversion

javascript

arrays

algorithm

tree