后代 ID 列表 - children、grandchildren 等

Question

CREATE TABLE [dbo].[Topic] (
    [Id]          SMALLINT      NOT NULL,
    [ParentId]    SMALLINT      NULL
);

我有一个带有 parent/child 层次结构的简单 table（上图）。我正在使用 Entity Framework 来提取数据。行数小于100

我想获得后代 ID 的列表，由 children、grandchildren 等组成（可能带有包含的选项原始根 parent)。由于 table 仅包含少量行，因此首先将所有数据提取到 List<Topic> 并进行处理可能更容易，但我有待更正。

首选输出为：Dictionary<int, List<int>>

其中键是 ID，列表将包含 child/grandchild ID 的

我在网上看了几十种解决方案，但找不到满足我需求的解决方案。有人可以帮忙吗？

Answer 1

您可以使用 ParentId->Id 关系填充字典并使用它来解析子主题：

// prepare dictionary
var dictionary = new Dictionary<short, List<Topic>>();

// in real life this would get replaced by your database query
var topics = new List<Topic>
{
    new Topic { Id = 1 },
    new Topic { Id = 2, ParentId = 1 },
    new Topic { Id = 3, ParentId = 1 },
    new Topic { Id = 4, ParentId = 1 },
    new Topic { Id = 5, ParentId = 1 },
    new Topic { Id = 6, ParentId = 2 },
    new Topic { Id = 7, ParentId = 2 },
    new Topic { Id = 8, ParentId = 3 },
    new Topic { Id = 9, ParentId = 4 },
    new Topic { Id = 10, ParentId = 4 },
    new Topic { Id = 11, ParentId = 8 },
    new Topic { Id = 12, ParentId = 8 }
};

// populate dictionary with relations from DB
foreach(var topic in topics)
{
    var key = topic.ParentId ?? -1;
    if(!dictionary.ContainsKey(key))
    {
        dictionary.Add(key, new List<Topic>());
    }

    dictionary[key].Add(topic);
}

现在您有了可用的映射，您可以编写一个简单的递归迭代器方法来解析给定 id 的后代：

IEnumerable<short> GetDescendantIDs(short from)
{
    if(dictionary.ContainsKey(from))
    {
        foreach(var topic in dictionary[from])
        {
            yield return topic.Id;
            foreach(var child in GetDescendants(topic.Id))
                yield return child;
        }
    }
}

// resolves to [1, 2, 6, 7, 3, 8, 11, 12, 4, 9, 10, 5]
var descendantsOfRoot = GetDescendantIDs(-1);

// resolves to [8, 11, 12]
var descendantsOfThree = GetDescendantIDs(3);

上面例子中使用的Topicclass就是：

class Topic
{
    internal short Id { get; set; }
    internal short? ParentId { get; set; }
}

Answer 2

考虑结果必须存储在树中：

public class TopicModel
{
    public int Id { get; set; }
    public int? ParentId{ get; set; }
    public List<TopicModel> Children { get; set; };
}

建筑树：

// retrieveing from database
var plainResult = context.Topic
    .Select(t => new TopicModel 
    { 
        Id = x.Id
        ParentId = x.ParentId
    })
    .ToList();

var lookup = plainResult.Where(x => x.ParentId != null).ToLookup(x => x.ParentId);

foreach (c in plainResult)
{
    if (lookup.Contains(c.Id))
    {
        c.Children = lookup[c.Id].ToList();
    }
}

// here we have all root items with children intialized 
var rootItems = plainResult.Where(x => x.ParentId == null).ToList();

并搜索 children:

public static IEnumerable<TopicModel> GetAllChildren(TopicModel model)
{
    if (model.Children != null)
    {
        foreach (var c in model.Children)
        {
            yield return c;

            foreach (sc in GetAllChildren(c))
                yield return sc;
        }
    }
}

后代 ID 列表 - children、grandchildren 等

List of descendant ID - children, grandchildren etc

c#

linq

recursion