ماهواره

دستورالعمل‌ها

تصور کنید باید یک درخت دودویی را به ماهواره‌ای که به سمت آلفا قنطورس می‌رود مخابره کنید و پهنای باند محدودی دارید. چون درخت هیچ عنصر تکراری ندارد، می‌توان آن را به‌طور یکتا با پیمایش‌های پیش‌ترتیب و میان‌ترتیب آن نمایش داد.

نرم‌افزاری برای ماهواره بنویسید تا درخت را از روی این پیمایش‌ها بازسازی کند.

در پیمایش پیش‌ترتیب، مقدار گره‌ی جاری پیش از خواندن زیردرخت چپ به‌صورت پیش‌ترتیب خوانده می‌شود (به همین دلیل «پیش»). پس از آن، زیردرخت راست به‌صورت پیش‌ترتیب خوانده می‌شود.

در پیمایش میان‌ترتیب، ابتدا زیردرخت چپ به‌صورت میان‌ترتیب خوانده می‌شود، بعد گره‌ی جاری و در نهایت زیردرخت راست به‌صورت میان‌ترتیب. یعنی به ترتیب از چپ به راست.

برای نمونه، پیمایش پیش‌ترتیب این درخت [a, i, x, f, r] است. پیمایش میان‌ترتیب این درخت [i, a, f, x, r] است.

  a
 / \
i   x
   / \
  f   r

نکته: اولین عنصر در پیمایش پیش‌ترتیب همیشه ریشه است.