邻接表中的树结构 [英] Tree Structure from Adjacency List

问题描述

我正在尝试从具有父ID的平面数组中生成分层树对象.

I am trying to generate a hierarchical tree object from a flat array with parent IDs.

// `parent` represents an ID and not the nesting level.
var flat = [
    { id: 1, name: "Business", parent: 0 },
    { id: 2, name: "Management", parent: 1 },
    { id: 3, name: "Leadership", parent: 2 },
    { id: 4, name: "Finance", parent: 1 },
    { id: 5, name: "Fiction", parent: 0 },
    { id: 6, name: "Accounting", parent: 1 },
    { id: 7, name: "Project Management", parent: 2  }
];

最终的树对象应如下所示:

The final tree object should look as follows:

{ 
    id: 1, 
    name: "Business", 
    children: [
        { 
            id: 2, 
            name: "Management", 
            children: [
                { id: 3, name: "Leadership" },
                { id: 7, name: "Project Management" }
            ]
        }
        // [...]
    ]
}
// [...]

您可以在此小提琴上看到我当前的作品，但它仅适用于前两个级别.

You can see my current work on this fiddle, but it only works on the first two levels.

我考虑过要收集这些孤儿( flat 中的对象，而在 tree 中还没有父对象)，然后再次遍历它们，以查看它们现在是否具有父对象.但这可能意味着在树对象上有许多循环，尤其是在多个级别上有许多类别.

I thought about collecting the orphans (objects from flat without a parent in tree yet) and then looping over them again to see if they now have a parent. But that could mean many loops over the tree object, especially with many categories over multiple levels.

我确定有一个更优雅的解决方案.

I'm sure there is a more elegant solution.

推荐答案

无论树的深度如何，您都可以通过2次传递来完成:

Looks like you can do this in 2 passes no matter the tree depth:

var flat = [
    { id: 1, name: "Business", parent: 0 },
    { id: 2, name: "Management", parent: 1 },
    { id: 3, name: "Leadership", parent: 2 },
    { id: 4, name: "Finance", parent: 1 },
    { id: 5, name: "Fiction", parent: 0 },
    { id: 6, name: "Accounting", parent: 1 },
    { id: 7, name: "Project Management", parent: 2  }
];

var nodes = [];
var toplevelNodes = [];
var lookupList = {};

for (var i = 0; i < flat.length; i++) {
    var n = {
        id: flat[i].id,
        name: flat[i].name,
        parent_id: ((flat[i].parent == 0) ? null : flat[i].parent),
        children: []
        };
    lookupList[n.id] = n;
    nodes.push(n);
    if (n.parent_id == null) {
        toplevelNodes.push(n);
    }
}

for (var i = 0; i < nodes.length; i++) {
  var n = nodes[i];
  if (!(n.parent_id == null)) {
      lookupList[n.parent_id].children = lookupList[n.parent_id].children.concat([n]);
  }
}

console.log(toplevelNodes);

这篇关于邻接表中的树结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！