用于生成层次结构的 C# 算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/947831/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C# algorithm for generating hierarchy
提问by Judah Gabriel Himango
I've got a text file that looks like this:
我有一个看起来像这样的文本文件：
{ Id = 1, ParentId = 0, Position = 0, Title = "root" }
{ Id = 2, ParentId = 1, Position = 0, Title = "child 1" }
{ Id = 3, ParentId = 1, Position = 1, Title = "child 2" }
{ Id = 4, ParentId = 1, Position = 2, Title = "child 3" }
{ Id = 5, ParentId = 4, Position = 0, Title = "grandchild 1" }
I'm looking for a generic C# algorithm that will create an object hierarchy from this. A "Hierarchize" function, if you will, that turns this data into an object hierarchy.
我正在寻找一种通用的 C# 算法，它将由此创建一个对象层次结构。一个“层次化”功能，如果你愿意的话，可以把这个数据变成一个对象层次结构。
Any ideas?
有任何想法吗？
editI've already parsed the file into .NET objects:
编辑我已经将文件解析为 .NET 对象：
class Node
{
public int Id { get; }
public int ParentId { get; }
public int Position { get; }
public string Title { get; }
}
Now I need to actually arrange the objects into an object graph.
现在我需要将对象实际排列成一个对象图。
采纳答案by Judah Gabriel Himango
Many thanks to Jon and to mquander - you guys gave me enough information to help me solve this in a proper, generic way. Here's my solution, a single generic extension method that converts objects into hierarchy form:
非常感谢 Jon 和 mquander - 你们给了我足够的信息来帮助我以适当的通用方式解决这个问题。这是我的解决方案，一个将对象转换为层次结构的通用扩展方法：
public static IEnumerable<Node<T>> Hierarchize<T, TKey, TOrderKey>(
this IEnumerable<T> elements,
TKey topMostKey,
Func<T, TKey> keySelector,
Func<T, TKey> parentKeySelector,
Func<T, TOrderKey> orderingKeySelector)
{
var families = elements.ToLookup(parentKeySelector);
var childrenFetcher = default(Func<TKey, IEnumerable<Node<T>>>);
childrenFetcher = parentId => families[parentId]
.OrderBy(orderingKeySelector)
.Select(x => new Node<T>(x, childrenFetcher(keySelector(x))));
return childrenFetcher(topMostKey);
}
Utilizes this small node class:
利用这个小节点类：
public class Node<T>
{
public T Value { get; private set; }
public IList<Node<T>> Children { get; private set; }
public Node(T value, IEnumerable<Node<T>> children)
{
this.Value = value;
this.Children = new List<Node<T>>(children);
}
}
It's generic enough to work for a variety of problems, including my text file issue. Nifty!
它的通用性足以解决各种问题，包括我的文本文件问题。漂亮！
****UPDATE****: Here's how you'd use it:
****更新****：这是您使用它的方式：
// Given some example data:
var items = new[]
{
new Foo()
{
Id = 1,
ParentId = -1, // Indicates no parent
Position = 0
},
new Foo()
{
Id = 2,
ParentId = 1,
Position = 0
},
new Foo()
{
Id = 3,
ParentId = 1,
Position = 1
}
};
// Turn it into a hierarchy!
// We'll get back a list of Node<T> containing the root nodes.
// Each node will have a list of child nodes.
var hierarchy = items.Hierarchize(
-1, // The "root level" key. We're using -1 to indicate root level.
f => f.Id, // The ID property on your object
f => f.ParentId, // The property on your object that points to its parent
f => f.Position, // The property on your object that specifies the order within its parent
);
回答by Chris Hamons
Are you certain the last line's ParentID is 1? The title says grandchild, but it would be a child of "root" if i'm reading things correctly.
你确定最后一行的 ParentID 是 1 吗？标题说孙子，但如果我正确阅读的话，它将是“根”的孩子。
回答by Jon Skeet
Hmm... I don't quite see how that works. How can 2 and 5 both have parent=1, position=0? Should 5 have parent 2, 3 or 4?
嗯...我不太明白这是如何工作的。2 和 5 怎么会有 parent=1, position=0？5 应该有父母 2、3 还是 4？
Okay, this new version goes through the all the nodes three times:
好的，这个新版本会遍历所有节点 3 次：
- Load all nodes and put them into the a map
- Associate each node with its parent
- Sort each node's child by position
- 加载所有节点并将它们放入地图
- 将每个节点与其父节点相关联
- 按位置对每个节点的子节点进行排序
It's not well-encapsulated, nicely error checking etc - but it works.
它没有很好地封装，很好的错误检查等 - 但它有效。
using System;
using System.Collections.Generic;
using System.IO;
public class Node
{
private static readonly char[] Braces = "{}".ToCharArray();
private static readonly char[] StringTrim = "\" ".ToCharArray();
public Node Parent { get; set; }
public int ParentId { get; private set; }
public int Id { get; private set; }
public string Title { get; private set; }
public int Position { get; private set; }
private readonly List<Node> children = new List<Node>();
public List<Node> Children { get { return children; } }
public static Node FromLine(string line)
{
Node node = new Node();
line = line.Trim(Braces);
string[] bits = line.Split(',');
foreach (string bit in bits)
{
string[] keyValue = bit.Split('=');
string key = keyValue[0].Trim();
string value = keyValue[1].Trim();
switch (key)
{
case "Id":
node.Id = int.Parse(value);
break;
case "ParentId":
node.ParentId = int.Parse(value);
break;
case "Position":
node.Position = int.Parse(value);
break;
case "Title":
node.Title = value.Trim(StringTrim);
break;
default:
throw new ArgumentException("Bad line: " + line);
}
}
return node;
}
public void Dump()
{
int depth = 0;
Node node = this;
while (node.Parent != null)
{
depth++;
node = node.Parent;
}
Console.WriteLine(new string(' ', depth * 2) + Title);
foreach (Node child in Children)
{
child.Dump();
}
}
}
class Test
{
static void Main(string[] args)
{
var dictionary = new Dictionary<int, Node>();
using (TextReader reader = File.OpenText("test.txt"))
{
string line;
while ((line = reader.ReadLine()) != null)
{
Node node = Node.FromLine(line);
dictionary[node.Id] = node;
}
}
foreach (Node node in dictionary.Values)
{
if (node.ParentId != 0)
{
node.Parent = dictionary[node.ParentId];
node.Parent.Children.Add(node);
}
}
foreach (Node node in dictionary.Values)
{
node.Children.Sort((n1, n2) =>
n1.Position.CompareTo(n2.Position));
}
Node root = dictionary[1];
root.Dump();
}
}
Sample text file:
示例文本文件：
{ Id = 5, ParentId = 4, Position = 0, Title = "grandchild 1" }
{ Id = 2, ParentId = 1, Position = 0, Title = "child 1" }
{ Id = 4, ParentId = 1, Position = 2, Title = "child 3" }
{ Id = 3, ParentId = 1, Position = 1, Title = "child 2" }
{ Id = 1, ParentId = 0, Position = 0, Title = "root" }
Output:
输出：
root
child 1
child 2
child 3
grandchild 1
回答by Jeremy
回答by Jimmy
class Node {
public int Id { get;set; }
public int ParentId { get;set; }
public int Position { get;set; }
public string Title { get;set; }
public IEnumerable<Node> Children { get; set; }
public override string ToString() { return ToString(0); }
public string ToString(int depth) {
return "\n" + new string(' ', depth * 2) + Title + (
Children.Count() == 0 ? "" :
string.Join("", Children
.Select(node => node.ToString(depth + 1))
.ToArray()
);
}
}
class Program {
static void Main(string[] args) {
var data = new[] {
new Node{ Id = 1, ParentId = 0, Position = 0, Title = "root" },
new Node{ Id = 2, ParentId = 1, Position = 0, Title = "child 1" },
new Node{ Id = 3, ParentId = 1, Position = 1, Title = "child 2" },
new Node{ Id = 4, ParentId = 1, Position = 2, Title = "child 3" },
new Node{ Id = 5, ParentId = 3, Position = 0, Title = "grandchild 1" }
};
Func<Node, Node> transform = null;
transform = node => new Node {
Title = node.Title,
Id = node.Id,
ParentId = node.ParentId,
Position = node.Position,
Children = (
from child in data
where child.ParentId == node.Id
orderby child.Position
select transform(child))
};
Console.WriteLine(transform(data[0]));
}
}
result:
结果：
root
child 1
child 2
grandchild 1
child 3
回答by mqp
I assume that your example incorrectly gives the wrong parent ID to object #5. This should cover it. Caveats: Assumes the "topmost" node always has a parent ID of zero. Ignores any nodes that aren't eventually descended from the topmost node. Behavior will be odd if presented with duplicate IDs.
我假设您的示例错误地为对象 #5 提供了错误的父 ID。这应该涵盖它。注意事项：假设“最顶层”节点的父 ID 始终为零。忽略最终不是从最顶层节点下降的任何节点。如果出现重复的 ID，行为会很奇怪。
public class FlatObj
{
public int Id;
public int ParentId;
public int Position;
public string Title;
}
public class Node
{
public int ID;
public string Title;
public IList<Node> Children;
public Node(FlatObject baseObject, IList<Node> children)
{
this.ID = baseObject.Id;
this.Title = baseObject.Title;
this.Children = children;
}
}
public static Node CreateHierarchy(IEnumerable<FlatObject> objects)
{
var families = objects.ToLookup(x => x.ParentId);
var topmost = families[0].Single();
Func<int, IList<Node>> Children = null;
Children = (parentID) => families[parentID]
.OrderBy(x => x.Position)
.Select(x => new Node(x, Children(x.Id))).ToList();
return new Node(topmost, Children(topmost.Id));
}
public static void Test()
{
List<FlatObj> objects = new List<FlatObj> {
new FlatObj { Id = 1, ParentId = 0, Position = 0, Title = "root" },
new FlatObj { Id = 2, ParentId = 1, Position = 0, Title = "child 1" },
new FlatObj { Id = 3, ParentId = 1, Position = 1, Title = "child 2" },
new FlatObj { Id = 4, ParentId = 1, Position = 2, Title = "child 3" },
new FlatObj { Id = 5, ParentId = 2, Position = 0, Title = "grandchild" }};
var nodes = CreateHierarchy(objects);
}
回答by Rodolpho Brock
Here is the example that @baran asked for:
这是@baran 要求的示例：
var lHierarchicalMenuItems = lMenuItemsFromDB.Hierarchize(0, aItem => aItem.Id, aItem => aItem.ParentId, aItem => aItem.Position);
