دستورالعمل‌ها
درخت را روی یک گره‌ی انتخاب‌شده دوباره والدگذاری کنید.
یک درخت نوع خاصی از گراف است که در آن همه‌ی گره‌ها به هم متصل‌اند اما هیچ دوری وجود ندارد.
یعنی برای هر جفت گره، دقیقاً یک مسیر برای رفتن از یک گره به گره دیگر وجود دارد.
این تمرین تماماً درباره‌ی جهت‌دهی دوباره‌ی یک درخت است تا از دیدگاهی متفاوت به آن نگاه کنید.
برای مثال، شجره‌نامه‌ها معمولاً از دیدگاه نیاکان نمایش داده می‌شوند:
+------0------+
| | |
+-1-+ +-2-+ +-3-+
| | | | | |
4 5 6 7 8 9
اما هیچ جهت ذاتی در درخت وجود ندارد.
همین اطلاعات را می‌توان از دیدگاه هر گره‌ی دیگر در درخت نمایش داد، به این ترتیب که آن را تا ریشه بالا می‌کشیم و روابطش را هم همراه با آن می‌کشیم.
بنابراین همان درخت از دیدگاه ۶ به این شکل خواهد بود:
6
|
+-----2-----+
| |
7 +-----0-----+
| |
+-1-+ +-3-+
| | | |
4 5 8 9
این کار به ما اجازه می‌دهد مسیرهای بین دو گره را ساده‌تر توصیف کنیم.
برای مثال، مسیر از ۶ به ۹ (که در درخت اول تا ریشه بالا می‌رود و سپس تا یک گره برگ دیگر پایین می‌آید) دیده می‌شود که مسیر ۶-۲-۰-۳-۹ را دنبال می‌کند.
این تمرین شامل گرفتن یک درخت ورودی و جهت‌دهی دوباره‌ی آن از دیدگاه یکی از گره‌ها است.
نکات پیاده‌سازی
برنامه‌ی آزمون درخت‌ها را با فراخوانی مکرر تابع New که تعداد آرگومان‌هایش متغیر است می‌سازد.
برای نمونه، دستور زیر
tree := New("a",New("b"),New("c",New("d")))
درخت زیر را می‌سازد:
"a"
|
-------
| |
"b" "c"
|
"d"
می‌توانید فرض کنید که در درخت‌های آزمون مقدار تکراری وجود ندارد.
برنامه‌ی آزمون از متدهای Value و Children برای تجزیه‌ی درخت‌ها استفاده می‌کند.
ساخت و تجزیه‌ی پایه‌ی درخت باید پیش از آنکه سراغ بخش جذاب تمرین بروید کار کند، بنابراین در سه آزمون نخست جداگانه آزمون می‌شود.
متدهای FromPov و PathTo بخش جذاب تمرین هستند.
متد FromPov یک آرگومان رشته‌ای به نام from می‌گیرد که گره‌ای در درخت را با مقدارش مشخص می‌کند.
باید درختی برگرداند که مقدار from در ریشه‌ی آن باشد.
می‌توانید درخت اصلی را تغییر دهید و همان را برگردانید، یا درخت تازه‌ای بسازید و آن را برگردانید.
اگر درخت تازه‌ای برگردانید، آزادید درخت اصلی را مصرف یا نابود کنید.
البته بهتر است آن را بدون تغییر رها کنید.
متد PathTo دو آرگومان رشته‌ای from و to می‌گیرد که دو گره در درخت را با مقدارهایشان مشخص می‌کنند.
باید کوتاه‌ترین مسیر در درخت از گره‌ی نخست به گره‌ی دوم را برگرداند.
