زاویه‌ی دید

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

درخت را روی یک گره‌ی انتخاب‌شده دوباره والدگذاری کنید.

یک درخت نوع خاصی از گراف است که در آن همه‌ی گره‌ها به هم متصل‌اند اما هیچ دوری وجود ندارد. یعنی برای هر جفت گره، دقیقاً یک مسیر برای رفتن از یک گره به گره دیگر وجود دارد.

این تمرین تماماً درباره‌ی جهت‌دهی دوباره‌ی یک درخت است تا از دیدگاهی متفاوت به آن نگاه کنید. برای مثال، شجره‌نامه‌ها معمولاً از دیدگاه نیاکان نمایش داده می‌شوند:

    +------0------+
    |      |      |
  +-1-+  +-2-+  +-3-+
  |   |  |   |  |   |
  4   5  6   7  8   9

اما هیچ جهت ذاتی در درخت وجود ندارد. همین اطلاعات را می‌توان از دیدگاه هر گره‌ی دیگر در درخت نمایش داد، به این ترتیب که آن را تا ریشه بالا می‌کشیم و روابطش را هم همراه با آن می‌کشیم. بنابراین همان درخت از دیدگاه ۶ به این شکل خواهد بود:

        6
        |
  +-----2-----+
  |           |
  7     +-----0-----+
        |           |
      +-1-+       +-3-+
      |   |       |   |
      4   5       8   9

این کار به ما اجازه می‌دهد مسیرهای بین دو گره را ساده‌تر توصیف کنیم. برای مثال، مسیر از ۶ به ۹ (که در درخت اول تا ریشه بالا می‌رود و سپس تا یک گره برگ دیگر پایین می‌آید) دیده می‌شود که مسیر ۶-۲-۰-۳-۹ را دنبال می‌کند.

این تمرین شامل گرفتن یک درخت ورودی و جهت‌دهی دوباره‌ی آن از دیدگاه یکی از گره‌ها است.

نکات پیاده‌سازی

شیء درخت دو ویژگی دارد:

• برچسب از نوع String
• فرزندان از نوع List<Tree>

برنامه‌ی آزمون درخت‌ها را با فراخوانی مکرر تابع سازنده‌ی Tree.of می‌سازد. برای مثال، دستور

Tree tree = Tree.of("a", List.of(Tree.of("b"), Tree.of("c", List.of(Tree.of("d")))));

درخت زیر را می‌سازد:

      "a"
       |
    -------
    |     |
   "b"   "c"
          |
         "d"

می‌توانید فرض کنید که در درخت‌های آزمون مقدار تکراری وجود ندارد.

متدهای FromPov و PathTo بخش جالب این تمرین هستند.

متد FromPov یک آرگومان رشته‌ای به اسم from می‌گیرد که گرهی در درخت را بر اساس مقدارش مشخص می‌کند. باید درختی برگرداند که مقدار from در ریشه‌ی آن قرار دارد. می‌توانید درخت اصلی را تغییر دهید و همان را برگردانید، یا درخت تازه‌ای بسازید و آن را برگردانید. اگر درخت تازه‌ای برگردانید، آزادید درخت اصلی را مصرف یا نابود کنید. البته بهتر است آن را بدون تغییر بگذارید.

متد PathTo دو آرگومان رشته‌ای from و to می‌گیرد که دو گره در درخت را بر اساس مقدارشان مشخص می‌کنند. باید کوتاه‌ترین مسیر درخت از گره‌ی اول تا گره‌ی دوم را برگرداند.

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

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

این تمرین خاص می‌خواهد که از کلیدواژه‌ی throw استفاده کنید و اگر کلاس Tree() درختی بگیرد که نمی‌توان دوباره جهت‌دهی‌اش کرد، یا مسیری بین یک start node و یک end node پیدا نشود، چندین UnsupportedOperationException را «پرتاب» کنید. آزمون‌ها تنها در صورتی قبول می‌شوند که هم exception را throw کنید و هم پیامی همراه آن بگنجانید.

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

// when a tree cannot be oriented to a new node POV
throw new UnsupportedOperationException("Tree could not be reoriented");

// when a path cannot be found between a start and end node on the tree.
throw new UnsupportedOperationException("No path found");

---

منبع

اقتباسی از تمرینی از 4clojure