Corrigé EXAMEN : Arbres binaires de recherche, récursivité et tri par piles – Algorithmique et structure de données

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

يركز الجزء الأول أيضا على مسارات الشجرة: المسار القبلي (RGD)، المسار الوسطي (GRD)، والمسار البعدي (GDR)، مع توضيح أن المسار الوسطي لشجرة البحث الثنائية يعطي عناصر القائمة مرتبة تصاعديا، وهو ما يمثل مبدأ الفرز بالشجرة. يتناول الجزء الثاني مفهوم الاستدعاء الذاتي من خلال دالة فيبوناتشي، مع رسم شجرة الاستدعاءات الخاصة بـ Fibonacci(4) لفهم تكرار التنفيذ.

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

تساعد هذه الوثيقة الطالب على مراجعة مفاهيم أساسية في بنى المعطيات مثل الأشجار الثنائية، الخوارزميات العودية، وتحليل عمليات الفرز، كما تقدم نماذج إجابة مناسبة للتحضير للامتحانات في مقياس Algorithmique et structure de données.