获取层次结构级别
问题内容：
我有一个对象数组，其中每个对象都有一个id和一个ParentId属性（以便可以将它们排列在树中）。它们没有特定的顺序。
请注意，id的和parentId不会是整数，它们将是字符串（只是想让示例代码更干净。。）
根只有一个：可以说id：1数据看起来像这样：
data = [
{
id:"id-2",
parentId:"id-3"
},
{
id:"id-4",
parentId:"2"
},
{
id:"id-3",
parentId:"id-4"
},
{
id:"id-5",
parentId:"id-4"
},
{
id:"id-6",
parentId:"id-1"
},
{
id:"id-7",
parentId:"id-1"
}
// and so on...
]
我正在寻找给每个对象一个level属性的有效方法，该属性应指定它的嵌套级别。
然后，它们应如下所示：
data = [
{
id:"id-2",
parentId:"id-1",
level:2
},
{
id:"id-3",
parentId:"id-4",
level:5
},
{
id:"id-4",
parentId:"id-2",
level:3
},
{
id:"id-5",
parentId:"id-4",
level:5
},
{
id:"id-6",
parentId:"id-1",
level:2
},
{
id:"id-7",
parentId:"id-3",
level:4
}
// and so on...
]
简而言之：
我希望level通过循环遍历数组并弄清楚层次结构来动态添加。
此外，（如果可能的话）然后应按照那里的顺序对它们进行排序，例如level:3来自同一父对象的所有对象都应该彼此相邻，而不是应该有同一个父对象的兄弟姐妹彼此相邻而不是两个3级堂兄彼此相邻。
问题答案：
以下代码的工作示例在jsFiddle上。
通过id对树进行索引，并从每个节点向上遍历树，然后计数直到您击中根为止。首先通过索引，我们可以达到O（n）时间复杂度（取决于树的密度）。*已更新以满足排序要求，并允许排除根节点：
function levelAndSort(data, startingLevel) {
// indexes
var indexed = {}; // the original values
var nodeIndex = {}; // tree nodes
var i;
for (i = 0; i < data.length; i++) {
var id = data[i].id;
var node = {
id: id,
level: startingLevel,
children: [],
sorted: false
};
indexed[id] = data[i];
nodeIndex[id] = node;
}
// populate tree
for (i = 0; i < data.length; i++) {
var node = nodeIndex[data[i].id];
var pNode = node;
var j;
var nextId = indexed[pNode.id].parentId;
for (j = 0; nextId in nodeIndex; j++) {
pNode = nodeIndex[nextId];
if (j == 0) {
pNode.children.push(node.id);
}
node.level++;
nextId = indexed[pNode.id].parentId;
}
}
// extract nodes and sort-by-level
var nodes = [];
for (var key in nodeIndex) {
nodes.push(nodeIndex[key]);
}
nodes.sort(function(a, b) {
return a.level - b.level;
});
// refine the sort: group-by-siblings
var retval = [];
for (i = 0; i < nodes.length; i++) {
var node = nodes[i];
var parentId = indexed[node.id].parentId;
if (parentId in indexed) {
var pNode = nodeIndex[parentId];
var j;
for (j = 0; j < pNode.children.length; j++) {
var child = nodeIndex[pNode.children[j]];
if (!child.sorted) {
indexed[child.id].level = child.level;
retval.push(indexed[child.id]);
child.sorted = true;
}
}
}
else if (!node.sorted) {
indexed[node.id].level = node.level;
retval.push(indexed[node.id]);
node.sorted = true;
}
}
return retval;
}
例：
// level 0 (root) excluded
var startingLevel = 1;
var someData = [
{id : "id-1", parentId : "id-0"},
{id : "id-2", parentId : "id-0"},
{id : "id-3", parentId : "id-2"},
{id : "id-4", parentId : "id-3"},
{id : "id-5", parentId : "id-4"},
{id : "id-6", parentId : "id-4"},
{id : "id-7", parentId : "id-0"},
{id : "id-8", parentId : "id-1"},
{id : "id-9", parentId : "id-7"},
{id : "id-10", parentId : "id-1"},
{id : "id-11", parentId : "id-1"},
{id : "id-12", parentId : "id-1"}
];
var outputArray = levelAndSort(someData, startingLevel);
输出：
注意
如果更改输入顺序，则排序会有所不同，但是仍然是正确的（即，按级别顺序，按同级分组）。
