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

التعليمات

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

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

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

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

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

  a
 / \
i   x
   / \
  f   r

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