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# 算法，它将由此创建一个对象层次结构。 如果您愿意的话，可以使用“层次化”功能，将这些数据转换为对象层次结构。

有任何想法吗？

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

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

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

Answer 1

我假设您的示例错误地为对象 #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);
}

Answer 2

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

Answer 3

你确定最后一行的 ParentID 是 1 吗？ 标题说的是孙子，但如果我读得正确的话，它将是“根”的孩子。

Answer 4

这是@baran 要求的示例：

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

Answer 5

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

Answer 6

嗯...我不太明白这是如何工作的。 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<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

Answer 7

解析完文件后，您可以按照此 博客。