التعليمات
غيّر أصل شجرة عند عقدة مختارة.
الشجرة هي نوع خاص من الرسوم البيانية تكون فيه جميع العُقد متصلة، ولا توجد فيه دورات مغلقة.
وهذا يعني وجود مسار واحد فقط للانتقال من عقدة إلى أخرى، لأي زوج من العُقد.
يتمحور هذا التمرين حول إعادة توجيه شجرة لرؤية الأمور من وجهة نظر مختلفة.
فعلى سبيل المثال، تُعرض شجرة العائلة عادةً من منظور السلف:
+------0------+
| | |
+-1-+ +-2-+ +-3-+
| | | | | |
4 5 6 7 8 9
لكن لا يوجد اتجاه متأصل في الشجرة.
يمكن عرض المعلومات نفسها من منظور أي عقدة أخرى في الشجرة، بسحبها إلى الجذر وجرّ علاقاتها معها.
لذا ستبدو الشجرة نفسها من منظور العقدة 6 هكذا:
6
|
+-----2-----+
| |
7 +-----0-----+
| |
+-1-+ +-3-+
| | | |
4 5 8 9
وهذا يتيح لنا وصف المسارات بين عقدتين ببساطة أكبر.
فعلى سبيل المثال، يمكن ملاحظة أن المسار من 6 إلى 9 (الذي يصعد في الشجرة الأولى إلى الجذر ثم يهبط إلى عقدة ورقة مختلفة) يتبع المسار 6-2-0-3-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، ويحددان عقدتين في الشجرة عبر قيمتهما.
ويجب أن تُرجع أقصر مسار في الشجرة من العقدة الأولى إلى العقدة الثانية.
