C#生成层次结构的算法

Question

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

{ 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# 算法，可以从这个数据中创建一个对象层次结构。如果您愿意，可以创建一个 "Hierarchize" 函数，将这些数据转换为对象层次结构。

有什么想法吗？

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

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

现在，我需要将这些对象实际组合成一个对象图。

- Judah Gabriel Himango

---

你已经有处理这个文本文件解析的代码了吗？ - pbz

我不明白为什么 { Id = 5 ... } 这个项目是孙子。孙子应该有一个孩子作为它的父亲，但它与所有其他孩子具有相同的父亲。它的 ParentId 不应该是 2、3 或 4 吗？我也不清楚你需要“Position”是用来做什么的。也许它指的是从左到右排列孩子的顺序，你需要明确地指定这一点？ - AHelps

我认为position属性会对每个父元素的子元素进行排序。 - mqp

抱歉，我的错，那是个笔误。我已经更新了帖子。 - Judah Gabriel Himango

pbz，是的，我已经有处理文件解析的代码了。 - Judah Gabriel Himango

Answer 1

非常感谢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);
}

使用这个小型节点类：

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

这个方法足够通用，可以解决各种问题，包括我的文本文件问题。很不错！

****更新****：以下是使用方法：

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

- Judah Gabriel Himango

---

你能给个示例来说明如何使用吗？ - Baran

@Baran 当然可以。我已经添加了使用示例。 - Judah Gabriel Himango

这甚至可以与动态对象一起使用！正是我所需要的！谢谢！ - noocyte

Answer 2

嗯...我不太明白那是如何运作的。2和5怎么可能都有父节点为1，位置为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<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();
    }
}

示例文本文件：

{ 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

- Jon Skeet

---

@Cheeso：这就是为什么我要求您在问题的评论中指定是否需要此内容。解析文本文件是完全不同的问题，对我来说，整个事情都像作业一样。 - pbz

好的，我已经加入了一个非常原始的解析器，它假设没有像字符串转义等有趣的东西。我仍然忽略位置，假设事情会按正确的顺序出现，并且我仍然假设父级在其子级之前。哦，我还假设你提供的示例中有一个错别字...但除此之外，它实际上是有效的。 - Jon Skeet

Jon，我的错，那是一个打字错误。我已经更新了帖子，使ID 5成为一个合适的孙子。 - Judah Gabriel Himango

很抱歉，答案是否定的，父节点并不总是在子节点之前出现。而且子节点也不总是按顺序出现。 - Judah Gabriel Himango

@JonSkeet 为什么我们不试试 http://www.superstarcoders.com/blogs/posts/recursive-hierarchical-joins-in-c-sharp-and-linq.aspx 。但是这个递归似乎不支持深度，尽管看起来他们支持。 - Murali Murugesan

Answer 3

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]));
    }
}

结果：

root
  child 1
  child 2
    grandchild 1
  child 3

- Jimmy

Answer 4

我认为你的例子错误地给了对象#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);
}

- mqp

---

我认为你有两个方面的误解。首先，你只关注了文本文件中某一行的ParentId。让我们暂时假设原问题中有一个错别字。无论如何，问题仍然存在——如何从这种数据中填充对象图。你提供的答案使用的源代码看起来像文本文件。这只是半个答案。你完全忽略了解析文件的问题。这对你来说可能很简单，但它并不是微不足道的。 - Cheeso

我认为他的问题假设文件已经解析成类似于我的FlatObj的某个对象，并向我们展示了文件内容的抽象表示。 - mqp

mquander 是正确的，我的问题假设文本文件已经解析成某个对象数据。我会更新问题以澄清这一点。mquander，谢谢您的解决方案，我会试一下。如果效果不错，我会将其标记为正确答案。 - Judah Gabriel Himango

Answer 5

一旦你解析了文件，你可以按照这篇博客的指导，使用LINQ将对象组装成层次结构。

- Jeremy

---

有趣的是，但是Omer Van Kloeten的实现似乎不关心父元素内部的顺序。 - Judah Gabriel Himango

Answer 6

这是@baran所要求的示例：

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

- Rodolpho Brock

Answer 7

你确定最后一行的ParentID是1吗？标题说是孙子，但如果我理解正确的话，它应该是“根”的子节点。

- Chris Hamons