Как перебирать древовидную структуру с помощью генератора?

Вот как следует реализовать Branch.EnumerateLeaves:

public IEnumerable<ITreeNode> EnumerateLeaves()
{
    foreach( var node in m_treeNodes )
    {
        if ( node is Leaf )
            yield return node;
        else
        {
            foreach (ITreeNode childNode in node.EnumerateLeaves())
                yield return childNode;
        }
    }
}

lassevk прав - одна потенциальная проблема с этим методом, однако, заключается в том, что рекурсивный вызов enumerables может дать производительность O (n ^ 2). Если это проблема, вы должны вместо этого исключить рекурсию и использовать внутренний стек.

public IEnumerable<ITreeNode> EnumerateLeaves()
{
    Stack<ITreeNode> workStack = new Stack<ITreeNode>(m_treeNodes);

    while(workStack.Count > 0) {
        var current = workStack.Pop();
        if (current is Leaf)
            yield return current;
        else {
            for(n = 0; n < current.m_treeNodes.Count; n++) {
                workStack.Push(current.m_treeNodes[n]);
            }
        }
    }
}

Это должно выполнять ту же функцию без рекурсии.

Обновлено: Дэниел Плейстед опубликовано в комментарии о более серьезной проблеме с рекурсивным вызовом перечислителей, обобщенной в сообщение в блогах MSDN об итераторах. Спасибо, Даниэль. знак равно

Другое редактирование: всегда помните, что простота кода может быть важнее производительности, особенно если вы ожидаете, что другие будут поддерживать ваш код. Если вы не ожидаете, что ваше дерево станет очень большим, используйте метод рекурсии lassevk, описанный в его ответе.

Другие ответы верны, но шаблон возврата yield внутри цикла foreach с рекурсивным вызовом приведет к тому, что время выполнения итерации по дереву будет примерно таким, как O (количество узлов * средняя глубина узла). См. это сообщение в блоге для более подробной информации о проблеме.

Вот попытка генератора, который эффективен как во время выполнения, так и в использовании памяти:

class Node
{
    List<Node> _children;

    public bool IsLeaf { get { return _children.Count == 0; } }

    public IEnumerable<Node> Children { get { return _children; } }

    public IEnumerable<Node> EnumerateLeaves()
    {
        if (IsLeaf)
        {
            yield return this;
            yield break;
        }

        var path = new Stack<IEnumerator<Node>>();

        path.Push(Children.GetEnumerator());

        while(!path.Empty)
        {
            var cur = path.Pop();
            if (cur.MoveNext())
            {
                path.Push(cur);
                if (cur.IsLeaf)
                {
                    yield return cur;
                }
                else
                {
                    path.Push(cur.Children.GetEnumerator());
                }
            }

        }
    }

}