নির্দেশনা
নির্বাচিত একটি নোডকে নতুন রুট বানিয়ে একটি ট্রি সাজানো।
একটি ট্রি হলো এক বিশেষ ধরনের গ্রাফ, যেখানে সব নোড সংযুক্ত কিন্তু কোনো চক্র নেই।
এর অর্থ হলো, যেকোনো এক জোড়া নোডের জন্য এক নোড থেকে অন্যটিতে পৌঁছানোর ঠিক একটি পথ থাকে।
এই অনুশীলনীটি মূলত একটি ট্রি-কে ভিন্ন দৃষ্টিকোণ থেকে দেখার জন্য নতুন করে সাজানোর বিষয়ে।
যেমন বংশলতিকা সাধারণত পূর্বপুরুষের দৃষ্টিকোণ থেকে উপস্থাপন করা হয়:
+------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 নেয়, যা মানের মাধ্যমে ট্রির দুটি নোড চিহ্নিত করে। এটি ট্রিতে প্রথম নোড থেকে দ্বিতীয় নোড পর্যন্ত সংক্ষিপ্ততম পথ রিটার্ন করবে।
