javascript - JavaScript 到 tree 的平面列表没有父 ID?

这个问题建立在许多类似的问题之上,例如 https://stackoverflow.com/questions/22367711/construct-hierarchy-tree-from-flat-list-with-parent-field/22367819?noredirect=1#comment127716528_22367819

然而,扭曲是没有父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, ...},
]

构造以下 tree 的高效方法是什么?请注意,孩子总是在父母之后,即可以从 depth value 中看到 tree。例如,id 2id 1 的子级,因为它的深度是 2,而 id 1 的深度是 1。id 3id 2 的子级,因为 id 3 的深度是 3。id 4id 1 而不是 id 3 的子级,因为 id 4 的深度是 id 3 的深度 3 的深度为 2(上一步)

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

应该有 values 喜欢

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

回答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 values 不对应节点的实际深度,而是留有间隙,则使用“字典”(普通对象)记录 depth 属性 values 的映射关系它们对应的深度:

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 节点,使用第一个函数,然后删除虚拟节点会更有效结果中的“根”(深度为 1)。

回答2

遍历数组并将每个项目添加到 tree 以及一系列面包屑。每个下一个项目要么作为一个孩子进入最后一个,要么通过面包屑路径回溯到需要插入它的正确深度:

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 可以直接突变。

回答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; }

相似文章

java - 在二叉搜索树中实现 nodeCount() 和 leafCount()

我正在尝试为这个递归二叉树程序实现leafCount()和nodeCount()。在测试它时,这两种方法(或它们的测试)会抛出失败,所以很明显它们没有按预期工作。我无法弄清楚我在哪里做错或想错了。如果...

最新文章