التعليمات
غيّر أصل شجرة عند عقدة مختارة.
الشجرة هي نوع خاص من الرسوم البيانية تكون فيه جميع العُقد متصلة، ولا توجد فيه دورات مغلقة.
وهذا يعني وجود مسار واحد فقط للانتقال من عقدة إلى أخرى، لأي زوج من العُقد.
يتمحور هذا التمرين حول إعادة توجيه شجرة لرؤية الأمور من وجهة نظر مختلفة.
فعلى سبيل المثال، تُعرض شجرة العائلة عادةً من منظور السلف:
+------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.
يتضمن هذا التمرين أخذ شجرة مُدخلة وإعادة توجيهها من وجهة نظر إحدى العُقد.
ملاحظات التنفيذ
كائن Tree له سمتان:
- تسمية من نوع
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 يحددان عقدتين في الشجرة من خلال قيمتيهما. ينبغي أن تُرجع أقصر مسار في الشجرة من العقدة الأولى إلى العقدة الثانية.
رسائل الاستثناءات
أحيانًا يلزمك رمي استثناء.
وعندما تفعل ذلك، ينبغي أن تضمّن دائمًا رسالة خطأ ذات معنى توضح مصدر الخطأ.
فهذا يجعل الكود أسهل في القراءة ويساعد كثيرًا في تصحيح الأخطاء.
يتطلب هذا التمرين تحديدًا أن تستخدم الكلمة المفتاحية throw
لكي «ترمي» عدة استثناءات UnsupportedOperationException إذا مُرِّرت للصنف Tree() شجرة لا يمكن إعادة توجيهها، أو تعذّر إيجاد مسار بين start node وend node.
لن تنجح الاختبارات إلا إذا نفّذت throw على exception وأدرجت معه رسالة.
لرمي استثناء 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");
