القمر الصناعي

التعليمات

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

اكتب البرنامج الخاص بالقمر الصناعي لإعادة بناء الشجرة من عمليات الاجتياز هذه.

يقرأ الاجتياز بالترتيب المسبق قيمة العقدة الحالية قبل قراءة الشجرة الفرعية اليسرى بالترتيب المسبق (ومن هنا جاءت تسميته "المسبق"). بعد ذلك تُقرأ الشجرة الفرعية اليمنى بالترتيب المسبق.

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

على سبيل المثال، الاجتياز بالترتيب المسبق لهذه الشجرة هو [a, i, x, f, r]. والاجتياز بالترتيب الداخلي لهذه الشجرة هو [i, a, f, x, r]

  a
 / \
i   x
   / \
  f   r

ملاحظة: العنصر الأول في الاجتياز بالترتيب المسبق هو دائمًا الجذر.

ينبغي أن تنفّذ هذا التمرين باستخدام قواعد الجمل المحددة (DCG). لا يقتصر استخدام DCG على تحليل المتتاليات (القوائم)، بل يمتد أيضًا إلى توليدها وإكمالها والتحقق منها.

المكتبة

تتضمّن ملفات التنفيذ الأولية السطر التالي:

:- use_module(library(dcg/basics)).

يضمن هذا إمكانية استخدام مكتبة dcg/basics، وهو ما ينبغي أن يكون كافيًا لحل هذا التمرين.

المصادر

فيما يلي مصادر مفيدة للبدء مع DCG في Prolog:

• metalevel.at
• wikipedia
• swipl