用于生成层次结构的C＃算法

我有一个看起来像这样的文本文件：

{ 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" } 

我正在寻找一种通用的C＃算法，它将从中创建一个对象层次结构。 如果您愿意，可以使用“层次结构”function将此数据转换为对象层次结构。

有任何想法吗？

编辑我已经将文件解析为.NET对象：

 class Node { public int Id { get; } public int ParentId { get; } public int Position { get; } public string Title { get; } } 

现在我需要将对象实际排列到对象图中。

Answer 1

非常感谢Jon和mquander – 你们给了我足够的信息来帮助我以正确，通用的方式解决这个问题。 这是我的解决方案，一个将对象转换为层次结构forms的通用扩展方法：

 public static IEnumerable> Hierarchize( this IEnumerable elements, TKey topMostKey, Func keySelector, Func parentKeySelector, Func orderingKeySelector) { var families = elements.ToLookup(parentKeySelector); var childrenFetcher = default(Func>>); childrenFetcher = parentId => families[parentId] .OrderBy(orderingKeySelector) .Select(x => new Node(x, childrenFetcher(keySelector(x)))); return childrenFetcher(topMostKey); } 

利用这个小节点类：

 public class Node { public T Value { get; private set; } public IList> Children { get; private set; } public Node(T value, IEnumerable> children) { this.Value = value; this.Children = new List>(children); } } 

它足够通用，可以解决各种问题，包括我的文本文件问题。 漂亮！

****更新****：以下是你如何使用它：

 // 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 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 ); 

Answer 2

嗯……我不太明白这是怎么回事。 2和5如何都有parent = 1，position = 0？ 5有父母2,3或4吗？

好的，这个新版本经历了三次所有节点：

• 加载所有节点并将它们放入地图中
• 将每个节点与其父节点相关联
• 按位置对每个节点的子节点进行排序

它没有很好的封装，很好的错误检查等 – 但它的工作原理。

 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 children = new List(); public List 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(); 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(); } } 

示例文本文件：

 { 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" } 

输出：

 root child 1 child 2 child 3 grandchild 1 

Answer 3

解析完文件后，可以按照此博客了解如何使用LINQ将对象组装到层次结构中。

Answer 4

我假设您的示例错误地将错误的父ID提供给对象＃5。 这应该涵盖它。 注意事项：假设“最顶层”节点的父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 Children; public Node(FlatObject baseObject, IList children) { this.ID = baseObject.Id; this.Title = baseObject.Title; this.Children = children; } } public static Node CreateHierarchy(IEnumerable objects) { var families = objects.ToLookup(x => x.ParentId); var topmost = families[0].Single(); Func> 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 objects = new List { 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); } 

Answer 5

 class Node { public int Id { get;set; } public int ParentId { get;set; } public int Position { get;set; } public string Title { get;set; } public IEnumerable 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 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])); } } 

结果：

 root child 1 child 2 grandchild 1 child 3 

Answer 6

你确定最后一行的ParentID是1吗？ 标题是孙子，但如果我正确地读东西，那将是一个“根”的孩子。

Answer 7

这是@baran要求的例子：

 var lHierarchicalMenuItems = lMenuItemsFromDB.Hierarchize(0, aItem => aItem.Id, aItem => aItem.ParentId, aItem => aItem.Position);