ماهواره

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

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

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

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

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

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

  a
 / \
i   x
   / \
  f   r

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

پیام‌های استثنا

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

این تمرین به‌طور خاص می‌خواهد که از دستور raise استفاده کنید تا اگر آرگومان‌های preorder و inorder از نظر طول یا عنصر با هم هم‌خوانی ندارند، یا عناصر یکتا نیستند، یک ValueError را «پرتاب» کنید. آزمون‌ها فقط وقتی قبول می‌شوند که هم exception را raise کنید و هم پیامی همراه آن بگنجانید.

برای ایجاد یک ValueError همراه با پیام، پیام را به‌عنوان آرگومان به نوع exception بدهید:

# if preorder and inorder are not the same length
raise ValueError("traversals must have the same length")

# if preorder and inorder do not share the same elements
raise ValueError("traversals must have the same elements")
    
# if element repeat (are not unique)    
raise ValueError("traversals must contain unique items")