我有一个集合展示了一个树状数据结构，它的节点是。
Node:
Id
Name
ParentID
现在，我想得到 level 对于这个集合中的每一个节点，我试着用下面的代码，但不知道是不是最好的实现方式。
Func<int, int> GetLevel = (nodeID) =>
{
int _level = 0;
var _node = source.First(p => p.Id == nodeID);
// while hasn't reached the root yet
while (_node .ParentID.HasValue)
{
_level++;
_node = source.First(p => p.Id == _node.ParentID);
}
return _level;
};
// source is a collection of Node.
var query = from node in source
select new
{
Id = node.Id,
Name = node.Name,
ParentID = node.ParentID,
Level = GetLevel(node.Id)
};
我认为在 GetLevel 功能是可以减少.或者说有更好的方法可以不用这个功能直接获得!
有什么好办法吗!
有了这个 节点类 你可以很容易地做到这一点。
public class Subject
{
public int Id { get; set; }
public int? ParentId { get; set; }
public string Name { get; set; }
}
创建一棵树并显示每个节点的级别。
var list = new List<Subject>
{
new Subject {Id = 0, ParentId = null, Name = "A"},
new Subject {Id = 1, ParentId = 0, Name = "B"},
new Subject {Id = 2, ParentId = 1, Name = "C"},
new Subject {Id = 3, ParentId = 1, Name = "D"},
new Subject {Id = 4, ParentId = 2, Name = "E"},
new Subject {Id = 5, ParentId = 3, Name = "F"},
new Subject {Id = 6, ParentId = 0, Name = "G"},
new Subject {Id = 7, ParentId = 4, Name = "H"},
new Subject {Id = 8, ParentId = 3, Name = "I"},
};
var rootNode = Node<Subject>.CreateTree(list, n => n.Id, n => n.ParentId).Single();
foreach (var node in rootNode.All)
{
Console.WriteLine("Name {0} , Level {1}", node.Value.Name, node.Level);
}
你可以在 n 步骤与广度第一遍遍历。您的方法是 n*log(n)据我所知？
在LinqPad中用一个节点类快速地破解了一个带有 Level 领域
class Node
{
public string Id;
public string ParentID;
public int Level;
public Node SetLevel(int i)
{
Level = i;
return this;
}
}
void Main()
{
var source = new List<Node>(){
new Node(){ Id = "1" },
new Node(){ Id = "2", ParentID="1"},
new Node(){ Id = "3", ParentID="1"},
new Node(){ Id = "4", ParentID="2"}
};
var queue = source.Where(p => p.ParentID == null).Select(s => s.SetLevel(0)).ToList();
var cur = 0;
while (queue.Any())
{
var n = queue[0];
queue.AddRange(source.Where(p => p.ParentID == n.Id).Select(s => s.SetLevel(n.Level + 1)));
queue.RemoveAt(0);
}
source.Dump();
}
输出。
Id ParentID Level
1 null 0
2 1 1
3 1 1
4 2 2
但这一切都取决于Linq部分的复杂性(.Where)
既然你说你需要得到的水平为 各 在这个集合中的节点，你可以制作一个从节点到层级的地图。热切.
通过适当的广度优先遍历，可以在O(n)时间内完成。
(未经测试)。
public static Dictionary<Node, int> GetLevelsForNodes(IEnumerable<Node> nodes)
{
//argument-checking omitted.
// Thankfully, lookup accepts null-keys.
var nodesByParentId = nodes.ToLookup(n => n.ParentID);
var levelsForNodes = new Dictionary<Node, int>();
// Singleton list comprising the root.
var nodesToProcess = nodesByParentId[null].ToList();
int currentLevel = 0;
while (nodesToProcess.Any())
{
foreach (var node in nodesToProcess)
levelsForNodes.Add(node, currentLevel);
nodesToProcess = nodesToProcess.SelectMany(n => nodesByParentId[n.Id])
.ToList();
currentLevel++;
}
return levelsForNodes;
}
下面是你所做的一个更紧凑的版本，注意我在测试中使用了一个简化的数据结构，Flatten返回一个IEnumerable < Tree > 树上每个节点的IEnumerable < Tree > 从变量树开始向下。如果你能访问该源，我会把递归深度函数作为树类的一部分。如果你经常这样做，或者你的树是巨大的（或者两者兼而有之），我特别喜欢在字典或树结构本身中缓存深度的解决方案。如果你不经常这样做，这就可以了。我用它来从GUI中翻阅相对较小的树结构，从来没有人认为这个操作很慢。复杂度是O(N log N)的平均情况下得到每个节点的深度。如果你想看所有的代码，我可以明天放进去。
Func<Tree, int> Depth = null;
Depth = p => p.Parent == null ? 0 : Depth(p.Parent) + 1;
var depth = tree.Flatten().Select(p => new { ID = p.NodeID(), HowDeep = Depth(p) });
现在你正在多次处理很多事情.我会递归地建立层次。这样你就不会有任何处理开销。
另外，如果你经常运行这个功能，我会把关卡放在节点类中作为一个变量，当添加节点时自动计算。
源代码如下。
尝试使用 .ToDictionary 像这样。
var dictionary =
source.ToDictionary(n => n.Id, n => n.ParentId);
Func<int, int> GetLevel = nid =>
{
var level = -1;
if (dictionary.ContainsKey(nid))
{
level = 0;
var pid = dictionary[nid];
while (pid.HasValue)
{
level++;
pid = dictionary[pid.Value];
}
}
return level;
};
这是相当有效的，因为你的最终查询 是要递归所有的节点。因此，建立字典的费用很便宜。
根据你的节点有多深，你可能会发现，在任何情况下，建立一个字典都比做多级蛮力搜索要快。