নির্দেশনা
নির্বাচিত একটি নোডকে নতুন রুট বানিয়ে একটি ট্রি সাজানো।
একটি ট্রি হলো এক বিশেষ ধরনের গ্রাফ, যেখানে সব নোড সংযুক্ত কিন্তু কোনো চক্র নেই।
এর অর্থ হলো, যেকোনো এক জোড়া নোডের জন্য এক নোড থেকে অন্যটিতে পৌঁছানোর ঠিক একটি পথ থাকে।
এই অনুশীলনীটি মূলত একটি ট্রি-কে ভিন্ন দৃষ্টিকোণ থেকে দেখার জন্য নতুন করে সাজানোর বিষয়ে।
যেমন বংশলতিকা সাধারণত পূর্বপুরুষের দৃষ্টিকোণ থেকে উপস্থাপন করা হয়:
+------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 নেয়, যা তাদের মান দিয়ে ট্রির দুটি নোড নির্দিষ্ট করে। এটি প্রথম নোড থেকে দ্বিতীয় নোড পর্যন্ত ট্রির সংক্ষিপ্ততম পথটি রিটার্ন করবে।
এক্সেপশন মেসেজ
কখনও কখনও একটি এক্সেপশন থ্রো করা প্রয়োজন হয়। এমন করলে এররটির উৎস কী তা বোঝাতে আপনার সর্বদা একটি অর্থপূর্ণ এরর মেসেজ যোগ করা উচিত। এতে আপনার কোড আরও পাঠযোগ্য হয় এবং debugging-এ যথেষ্ট সাহায্য মেলে।
এই নির্দিষ্ট অনুশীলনীতে আপনাকে throw কীওয়ার্ড ব্যবহার করে একাধিক UnsupportedOperationException "থ্রো" করতে হবে, যদি Tree() ক্লাসকে এমন একটি ট্রি দেওয়া হয় যাকে নতুন দৃষ্টিকোণ থেকে সাজানো যায় না, অথবা start node ও end node-এর মধ্যে কোনো পথ খুঁজে পাওয়া না যায়। টেস্ট পাস হবে কেবল তখনই, যখন আপনি 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");
