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

Question

Я пытаюсь понять, как реализовать функцию в узле дерева, которая возвращает все ее дочерние листья (прямые или косвенные).Однако я не хочу передавать контейнер, в который конечные узлы будут помещаться рекурсивно (дерево может быть огромным), вместо этого я хотел бы использовать генератор для перебора по дереву.Я перепробовал несколько подходов, но пока ни один из них не сработал.Это самое близкое, к чему я пришел, возможное решение:

    public interface ITreeNode
    {
        IEnumerable<ITreeNode> EnumerateLeaves();            
    }

    class Leaf : ITreeNode
    {
        public IEnumerable<ITreeNode> EnumerateLeaves()
        {
            throw new NotImplementedException();
        }
    }

    class Branch : ITreeNode
    {
        private List<ITreeNode> m_treeNodes = new List<ITreeNode>();

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

Но это тоже не работает.Что я делаю не так?Похоже на вызов.Рекурсивный EnumerateLeaves не будет работать, если в той же функции есть оператор yield.

Мы были бы очень признательны за любую помощь.Заранее благодарю.

Редактировать:Я забыл упомянуть, что ветвь может иметь либо листья, либо ответвления в качестве дочерних элементов, отсюда и рекурсия.

Answer 1

Вот как вы должны реализовать 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;
        }
    }
}

Answer 2

лассевк прав - однако одна потенциальная проблема с этим методом заключается в том, что рекурсивный вызов 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 информацию об итераторах.Спасибо, Дэниел.=)

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

Answer 3

Другие ответы верны, но шаблон возврата 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());
                }
            }

        }
    }

}