اتساع العكس الأول في التوقيت في ج#

Question

أي شخص لديه تنفيذ جاهز لخوارزمية اجتياز العكسي العكسي في C#؟

بعرض عكسي أول اجتياز ، أعني بدلاً من البحث عن شجرة تبدأ من عقدة مشتركة ، أريد البحث عن الشجرة من الأسفل وتلتفت تدريجياً إلى عقدة مشتركة.

دعونا نرى الشكل أدناه ، هذا هو إخراج العرض الأول:

في اتساع العكس الخاص بي أول اجتياز ، 9,10,11 و 12 ستكون العقد القليلة الأولى الموجودة (ترتيبها ليس مهمًا لأنها جميعًا من الدرجة الأولى). 5, 6, 7 و 8 هي العقد القليلة الثانية التي تم العثور عليها ، وهلم جرا. 1 سيكون آخر عقدة وجدت.

أي أفكار أو مؤشرات؟

تحرير: تغيير "اتساع أول بحث" إلى "اتساع أول اجتياز" لتوضيح السؤال

Answer 1

تشغيل BFS العادية من rootNode ودع depth[i] = linked list of nodes with depth i. لذلك على مثالك سيكون لديك:

depth[1] = {1}, depth[2] = {2, 3, 4} etc.. يمكنك بناء هذا مع بحث بسيط من BFS. ثم طباعة جميع العقد في depth[maxDepth], ثم أولئك في depth[maxDepth - 1] إلخ.

عمق العقدة i يساوي عمق عقدة الأب + 1. يمكن اعتبار عمق عقدة الجذر 1 أو 0.

Answer 2

استخدم مزيجًا من المكدس وقائمة الانتظار.

قم بعمل BFS "العادي" باستخدام قائمة الانتظار (التي أفترض أنك تعرفها بالفعل) ، واستمر في دفع العقد على المكدس أثناء مواجهتها.

بمجرد الانتهاء من BFS ، سيحتوي المكدس على ترتيب BFS العكسي.