هل من الممكن تنفيذ خوارزمية العودية مع التكرار?

Question

لقد أعطيت شجرة مثل هذا:

http://www.seqan.de/dddoc/html/streePreorder.png http://www.seqan.de/dddoc/html/streePreorder.png

أنا يمكن أن الق كل عقدة مع المشغل.

// postorder dfs
Iterator< Index<String<char> >, BottomUp<> >::Type myIterator(myIndex);
for (; !atEnd(myIterator); goNext(myIterator)) 
    // do something with myIterator

ولكن أريد أن استخدام خوارزمية العودية على الشجرة.
هل هناك طريقة يمكنني جعل خوارزمية العودية (exlude أكبر الشجرة على كل عقدة) تكرارية ?
أو كيف يمكن أن الق العناصر غير متكرر ?

تحرير:المشكلة الفعلية :
لقد أعطيت العودية الخوارزمية التي تعمل على الأشجار.(العودية)
أود أيضا أن استخدام المكتبة حيث أنا فقط يمكن أن الق العناصر مع التكرار ( غير القياسية ، تكرارية)

العودية <-> متكررة.
كيف يمكنني حل هذا ؟

Answer 1

إذا كان مكرر يدعم فقط إلى الأمام (وربما الخلف) اجتياز ولكن ليس من خلال الروابط التالية على شجرة أو سريع الوصول العشوائي, سيكون لديك الوقت الصعب جدا تكييف خوارزمية شجرة إلى ذلك.ولكن في النهاية أي إجابة تعتمد على واجهة قدمها المخصصة الخاصة بك التكرار ، التي لم تقدم.

على سبيل المثال في السهل خوارزمية شجرة البحث.إذا العملية الوحيدة التي قدمها مكرر الخاصة بك هو "بداية من العنصر الأول والانتقال واحدة تلو الأخرى" ، من الواضح أنك لا يمكن أن تنفذ شجرة البحث بكفاءة.ولا يمكن تنفيذ البحث الثنائية.لذلك يجب تقديم قائمة بالضبط ما هي العمليات المعتمدة ، و (خطيرة) تعقد حدود لكل منها.

Answer 2

يمكنك تحويل أن وظيفة العودية إلى تكرارية وظيفة مع مساعدة من كومة.

//breadth first traversal pseudo-code
push root to a stack
while( stack isn't empty )
    pop element off stack
    push children
    perform action on current node

اعتمادا على كيفية كنت ترغب في اجتياز العقد تنفيذ ستكون مختلفة.جميع وظائف العودية يمكن أن تتحول إلى تكرارية منها.عامة الاستخدام على كيفية يتطلب معلومات عن مشكلة معينة.باستخدام مداخن/طوابير تحول الى حلقة هي الطرق الشائعة التي يجب أن تحل معظم الحالات.

يجب أن ننظر أيضا في ذيل العودية و كيفية التعرف عليها ، كما أن هذه المشاكل بشكل جيد يترجم إلى حلقة for العديد من المجمعين حتى أفعل هذا بالنسبة لك.

بعض من أكثر رياضيا الموجهة دعوات متكررة يمكن حلها عن طريق تكرار العلاقات.احتمال أن كنت تأتي عبر هذه التي لم يتم حلها حتى الآن غير جيد ، ولكن قد تهمك.

//تحرير الأداء ؟ حقا يتوقف على تنفيذ حجم الشجرة.إذا كان هناك الكثير من العمق في دعوة متكررة, ثم سوف تحصل على كومة تجاوز سعة ، في حين تكرارية النسخة أداء جيد.وأود أن الحصول على فهم أفضل العودية (كيفية استخدام الذاكرة) ، يجب أن تكون قادرة على أن تقرر ما هو أفضل من أجل الوضع الخاص بك. هنا هو مثال على هذا النوع من التحليل مع أرقام فيبوناتشي.

Answer 3

أي وظيفة متكررة بدلا من ذلك يمكن تنفيذها مع مداخن.إذا كان هذا هو السؤال الذي تطرحه.

هنا المادة بواسطة فيل Haack على هذا الموضوع.

المكاسب الأداء بطريقة أو أخرى هي المضاربة ، مترجم يفعل أشياء مع التعليمات البرمجية خلف الكواليس التي لا يمكن دائما التنبؤ بها.تنفيذ والحصول على بعض الأرقام الحقيقية.إذا كانت متشابهة استخدام أحد أن تجد أكثر قابلية للقراءة.

Answer 4

حتى متكررة مع التكرار, يمكنك في نهاية المطاف مع عقدة كل عقدة الزيارة.

ما تحتاج إلى معرفته هو:كيف يمكن ان التكرار يقال أن تذهب العمق أولا ثم:كيف سيتم إعلامك أن مستوى واحد بدأ/انتهى (أيبداية/نهاية العودية الخطوة).

أن المعرفة يمكن تعيينها على خوارزمية العودية.