#1 楼
我会分开迭代并将项目添加到列表中:public IEnumerable<Channel> ChildrenOf(Channel root)
{
yield return root;
foreach(var c in root.Children)
foreach(var cc in ChildrenOf(c))
yield return cc;
}
评论
\ $ \ begingroup \ $
这会使其变得更好/更快吗? IL如何比较?
\ $ \ endgroup \ $
–luketorjussen
2011年10月28日在7:47
\ $ \ begingroup \ $
快到了,别忘了退回一级孩子
\ $ \ endgroup \ $
–礼貌
11-10-28在7:51
\ $ \ begingroup \ $
@luketorjussen:此方法更快,因为它不需要在堆上进行任何分配,因此不需要释放。请注意,由于数据未缓存在列表中,因此无法进行操作,并且多次迭代将多次执行该函数
\ $ \ endgroup \ $
–礼貌
2011-10-28 7:53
\ $ \ begingroup \ $
@Polity:实际上,每个“ foreach”循环都会创建一个枚举数对象,该对象仍然是堆上的分配(内部循环为外循环的每次迭代创建一个枚举数)。
\ $ \ endgroup \ $
–布赖恩·赖希尔(Brian Reichle)
2011-10-28 8:47
\ $ \ begingroup \ $
您应该小心避免在递归函数中返回收益,内存使用量会爆炸性地扩展。请参阅stackoverflow.com/a/30300257/284795。因此,Guffa和Lippert的解决方案是优选的。
\ $ \ endgroup \ $
–上校恐慌
15年5月18日在10:09
#2 楼
只是为了弄清楚其他答案:我将倾向于这样编写您的解决方案: >static IEnumerable<T> DepthFirstTreeTraversal<T>(T root, Func<T, IEnumerable<T>> children)
{
var stack = new Stack<T>();
stack.Push(root);
while(stack.Count != 0)
{
var current = stack.Pop();
// If you don't care about maintaining child order then remove the Reverse.
foreach(var child in children(current).Reverse())
stack.Push(child);
yield return current;
}
}
现在,您有了一个更通用的工具,可以用来获取任何树结构的深度优先遍历,而不仅仅是您的特定结构。
我的解决方案的另一个不错的功能是它使用固定数量的调用堆栈空间。即使您的层次结构深达两万,您也不会耗尽堆栈空间,因为该方法从一开始就不是递归的。递归所需的所有信息都存储在“堆栈”数据结构中,而不是存储在实际调用堆栈中的激活记录中。
评论
\ $ \ begingroup \ $
该死。在这里,我只是用这样的通用堆栈来回答这个问题... :)
\ $ \ endgroup \ $
–John Gietzen
2011年11月3日,下午4:15
\ $ \ begingroup \ $
+1,用于使用此遍历扩展名填充列表。我对遍历方法进行了C#扩展,并在很多东西上使用了它。我发现比使用递归方法更容易理解。
\ $ \ endgroup \ $
–约翰·耶稣
2014年5月22日13:47
\ $ \ begingroup \ $
微观优化:我将收益率放在foreach之前,以节省一些周期和内存,以防枚举器的迭代中途停止。
\ $ \ endgroup \ $
– Pablo H
17年5月27日在3:09
#3 楼
将递归部分放在私有方法中,以便您可以将项目直接添加到列表中,而不必创建中间列表:public List<Channel> ChildrenOf(Channel startingChannel) {
List<Channel> result = new List<Channel>();
AddChildren(startingChannel, result);
return result;
}
private void AddChildren(Channel channel, List<Channel> list) {
foreach (Channel child in channel.Children) {
list.Add(child);
AddChildren(child, list);
}
}
(这基本上是相同的原理正如Polity建议的那样,只有两种方法可以实现它,因此您不必创建一个空列表来调用它。)
#4 楼
分享您的结果列表将是防止分配,尤其是发生收集的一种方法 public List<Channel> ChildrenOf(Channel startingChannel, List<Channel> result)
{
foreach (Channel child in startingChannel.Children)
{
result.Add(child);
// this will internally add to result
ChildrenOf(child, result);
}
return result;
}
评论
在我看来就是这样。但是也许其他人有其他想法。您的方法存在深度嵌套列表的问题。假设您有N个项目,嵌套深度D。然后将每个项目复制D次-> O(N * D)次。 “收益回报”答案有一个类似的问题:对于每个项目,它都必须执行D个“收益回报”语句。 Guffa的答案没有这个问题,它将在O(N)时间运行。
有没有办法做到这一点与尾递归? HRMMM。