Como percorrer uma estrutura de árvore usando um gerador?

Question

Eu estou tentando descobrir como implementar uma função em um nó de árvore que retorna todas as suas folhas descendentes (direta ou indireta). No entanto, eu não quero passar um recipiente em que os nós folha será colocado de forma recursiva (a árvore pode ser enorme), em vez eu gostaria de usar um gerador para percorrer a árvore. Eu tentei algumas abordagens, mas nenhum deles funcionou até agora. Este é o mais próximo que eu vim a uma solução possível:

    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();
            }
        }
    }

Mas isso não está funcionando. O que estou fazendo de errado? Parece chamando .EnumerateLeaves recursivamente não funcionará se houver uma declaração de rendimento na mesma função.

Qualquer ajuda seria muito apreciado. Agradecemos antecipadamente.

Edit:. Eu esqueci de mencionar que um ramo pode ter ou folhas ou ramos como crianças, daí a recursão

Answer 1

Aqui está como você deve implementar 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

lassevk é certo - um potencial problema com esse método, no entanto, é que recursivamente pôr em enumerables pode render O (n ^ 2) o desempenho. Se este é um problema, então você em vez deve levar a recursão para fora e usar uma pilha interna.

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]);
            }
        }
    }
}

Isso deve executar a mesma função, sem a recursividade.

Edit: Daniel Plaisted postou um comentário sobre um problema maior com Enumerators chamar de forma recursiva, resumiu em uma post sobre os blogs MSDN sobre iteradores . Graças Daniel. =)

Outro Edit: Lembre-se sempre que a simplicidade código pode ser mais importante do que o desempenho, especialmente se você esperar que os outros para manter seu código. Se você não espera sua árvore a crescer muito grande, use o método recursão lassevk delineado na sua resposta.

Answer 3

As outras respostas estão corretas, mas o padrão de ter um retorno de rendimento dentro de um loop foreach com uma chamada recursiva vai fazer o tempo correr para percorrer a algo árvore como O (número de nós * profundidade média de um nó). Consulte este post para obter mais detalhes sobre o problema.

Aqui é uma tentativa de um gerador que é eficiente, tanto o uso de tempo de execução e memória:

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());
                }
            }

        }
    }

}