كيفية التكرار من خلال هيكل شجرة باستخدام مولد؟

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 هو الحق - قضية واحدة محتملة مع هذا الأسلوب، ومع ذلك، هو أن تدعو بشكل متكرر إلى enumerables يمكن أن تسفر O (ن ^ 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 المبينة في جوابه.

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

        }
    }

}