仅使用 parentId 对层次结构数据进行高效排序
本文关键字:高效 排序 数据 层次结构 parentId | 更新日期: 2023-09-27 17:56:41
>问题
排序一组平面无序节点的最快方法是什么,以便父节点始终列在其子节点之前。我当前的解决方案首先使用队列以广度方式迭代树。但是我一直想知道是否有更好/更有效的方法。
笔记:
- 我无法预先计算任何值 Id
- 和 ParentId 也可以是 Guid(即使整数我不能保证顺序 ID)
林克垫代码
void Main()
{
var nodes = new Node[] {
new Node { Id = 7, ParentId = 3 },
new Node { Id = 4, ParentId = 2 },
new Node { Id = 1, ParentId = 0 },
new Node { Id = 2, ParentId = 1 },
new Node { Id = 3, ParentId = 1 },
new Node { Id = 5, ParentId = 2 },
new Node { Id = 6, ParentId = 3 },
new Node { Id = 8, ParentId = 0 },
};
SortHierarchy(nodes).Dump();
}
IEnumerable<Node> SortHierarchy(IEnumerable<Node> list)
{
// hashtable lookup that allows us to grab references to the parent containers, based on id
var lookup = new Dictionary<int, List<Node>>();
Queue<Node> nodeSet = new Queue<Node>();
List<Node> children;
foreach (Node item in list) {
if (item.ParentId == 0) { // has no parent
nodeSet.Enqueue(item); // This will add all root nodes in the forest
} else {
if (lookup.TryGetValue(item.ParentId, out children)) {
// add to the parent's child list
children.Add(item);
} else {
// no parent added yet
lookup.Add(item.ParentId, new List<Node> { item });
}
}
}
while (nodeSet.Any()) {
var node = nodeSet.Dequeue();
if (lookup.TryGetValue(node.Id, out children)) {
foreach (var child in children) {
nodeSet.Enqueue(child);
}
}
yield return node;
}
}
private class Node {
public int Id { get; set; }
public int ParentId { get; set; }
public string Name { get; set; }
}
研究
我确实发现了这个,但它并不完全是我所追求的(代码也不起作用)
从父/子的平面列表生成层次结构对象
此代码给出相同的 dump() 结果,首先使用 parentid 对列表进行排序:
IEnumerable<Node> SortHierarchy2(IEnumerable<Node> list)
{
return list.OrderBy(l => l.ParentId);
}
只要您的孩子 ID