발전기를 사용하여 트리 구조를 반복하는 방법은 무엇입니까?

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를 호출하는 것처럼 보입니다.

모든 도움은 대단히 감사하겠습니다. 미리 감사드립니다.

편집 : 나는 지점이 어린이로서 잎이나 가지를 가질 수 있다는 것을 언급하는 것을 잊었다.

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

Lassevk는 옳습니다. 그러나이 방법의 잠재적 인 문제 중 하나는 재귀 적으로 열거 된 사람을 호출하면 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 블로그에 게시하십시오. 감사합니다 Daniel. =))

또 다른 편집 : 특히 다른 사람들이 코드를 유지할 것으로 기대하는 경우 코드 단순성이 성능보다 더 중요 할 수 있음을 항상 기억하십시오. 당신의 나무가 매우 크게 자라는 것을 기대하지 않는다면, 재귀 방법 Lassevk는 그의 대답에 설명되어 있습니다.

Answer 3

다른 답변은 정확하지만, 재귀 호출이있는 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());
                }
            }

        }
    }

}