从列表递归创建树

我有一个基本上形成树的嵌套注释列表。从列表递归创建树

//Non-Relevant properties (Like Body, Creator etc) excluded 
internal class Comment 
{ 
    public int ID { get; set; } 
    public int ItemID { get; set; } 
    public int ParentItemID { get; set; } 
    public List<Comment> ChildComments { get; set; } 
}

首先，我得到的Posts列表从数据库中，然后我得到的所有Comments where ItemID == Posts[all].id

我想遍历一个平坦的列表，并创建一个嵌套，或树列表。

它是这样的：

如果ParentItemID == 0，那么我们有一个顶层评论。如果ParentItemID > 0我们需要将ParentItemID与评论ID匹配，并将子注释添加到父注释列表。

我卡在哪里，我只使用过去的递归来导航文件和文件夹。这不允许我通过后续递归实例化一个集合并保留它。

在递归外部实例化列表似乎也很愚蠢，然后在每次我想添加项目时循环遍历所有项目。

我相信这样做有一个很好的可靠模式，我找不到它。

来源

2012-08-28 Wesley

你可以通过所有评论循环，得到每个孩子的意见：

foreach (Comment comment in comments) { 
    comment.ChildComments = 
    comments.Where(c => c.ParentItemID == comment.ItemID).ToList(); 
}

会表现得更好（如果需要）将组在ParentItemID的意见，并创造另一种选择Dictionary<int, List<Comment>>，然后只是循环上面的评论，并从字典中获取列表。

来源

2012-08-28 22:56:16 Guffa

我相信OP有一个平坦的列表，他想将它转换为嵌套模型。 –

@AndreCalil：是的，它的确如此。 – Guffa

这是真的，我会继续打开这个问题，但是可能需要避免在第一个地方创建平面列表。 – Wesley

Guffa的解决方案是这样漂亮，但这里是一个另类：

public static List<Comment> ToTree(List<Comment> FlatCommentsList) 
    { 
     List<Comment> TopComments = FlatCommentsList.Where<Comment>(x => x.ParentItemID == 0).ToList(); 

     List<Comment> NestedComments = FlatCommentsList.Where<Comment>(x => x.ParentItemID > 0).ToList(); 

     List<int> IdsToRemove; 

     while (NestedComments.Count > 0) 
     { 
      IdsToRemove = new List<int>(); 

      NestedComments.ForEach(x => 
      { 
       Comment ParentComment = TopComments.Where<Comment>(y => y.ItemID == x.ParentItemID).SingleOrDefault<Comment>(); 

       if (ParentComment != null) 
       { 
        ParentComment.ChildComments.Add(x); 
        IdsToRemove.Add(x.ItemID); 
       }  
      }); 

      NestedComments.RemoveAll(x => IdsToRemove.Contains(x.ItemID)); 
     } 

     return TopComments; 
    }

它没有递归为好，但它的工作。我是递归的粉丝，但我不认为我们在这里需要它。

来源

2012-08-28 23:03:37

分离顶级和嵌套的注释可以与LINQ和GroupBy来完成：

var grouped = comments.GroupBy(c => c.ParentItemId == 0); 
var topLevel = grouped.Single(g => g.Key); 
var nested = grouped.Single(g => !g.Key);

（在这些操作的结果实际上不会被计算，直到你遍历序列或使用方法等ToList()在他们身上）

将嵌套评论附加到他们的父母可以像古法的方法（缓慢的很多评论，不使用额外的内存），或者你可以做一个经典的时间空间折衷（快速的大量的意见，需要额外的内存）：

var dictionary = comments.ToDictionary(c => c.Id); 
foreach (nested as comment) { 
    dictionary[comment.ParentItemId].ChildComments.Add(comment); 
}

来源

2012-08-28 23:04:40 Jon

有趣。我可能不得不对这个测试做一些测试，并考虑可能的使用场景。 – Wesley

从列表递归创建树

回答

相关问题