আমাদের একটি বাইনারি গাছের ইনঅর্ডার এবং প্রিঅর্ডার ট্রাভার্সাল দেওয়া হয়েছে। লক্ষ্য হল প্রদত্ত ট্রাভার্সাল থেকে একটি গাছ তৈরি করা।
অভ্যন্তরীণ ট্রাভার্সাল − এই ধরনের ট্রি ট্রাভার্সালে, প্রথমে একটি বাম সাবট্রি পরিদর্শন করা হয়, তারপরে নোড এবং ডান সাবট্রিটি শেষে দেখা হয়৷
অনুক্রম (গাছের মূল)
-
রুট দ্বারা নির্দেশিত নোডের বাম সাবট্রি ট্র্যাভার্স, কল ইনঅর্ডার ( রুট→বাম)
-
রুট দেখুন
-
রুট দ্বারা নির্দেশিত নোডের ডান সাবট্রি ট্র্যাভার্স, ইনঅর্ডার কল করুন ( রুট→ডান )
প্রাক-অর্ডার ট্রাভার্সাল − এই ধরনের ট্রি ট্রাভার্সালে, নোডটি প্রথমে পরিদর্শন করে, তারপরে বাম সাবট্রি এবং শেষে ডান সাবট্রি।
প্রাক-অর্ডার (গাছের মূল)
- মূলে যান
- রুট দ্বারা নির্দেশিত নোডের বাম সাবট্রি ট্র্যাভার্স, কল ইনঅর্ডার (রুট→বাম)
- রুট দ্বারা নির্দেশিত নোডের ডান সাবট্রি ট্রাভার্স, ইনঅর্ডার কল করুন ( রুট→ডান )
নিচের গাছের ইনঅর্ডার এবং প্রি-অর্ডার ট্রাভার্সাল দেওয়া আছে −
অনুক্রম
2-3-4-5-6-8-10
প্রাক-অর্ডার
4-3-2-5-8-6-10
এখন আমরা প্রদত্ত প্রি-অর্ডার এবং ইনঅর্ডার ট্রাভার্সালের জন্য উপরের গাছটি আবার তৈরি করব।
অনুক্রম
2-3-4-5-6-8-10
প্রাক-অর্ডার
5-3-2-4-8-6-10
-
আমরা জানি যে প্রি-অর্ডার প্রথমে রুট নোড ভিজিট করে তারপর প্রথম মান সবসময় গাছের মূলকে প্রতিনিধিত্ব করে। উপরের ক্রম থেকে 5 হল গাছের মূল।
প্রাক-অর্ডার
5 -3-2-4-8-6-10
-
উপরের ইনঅর্ডার ট্রাভার্সাল থেকে, আমরা জানি যে একটি নোডের বাম সাবট্রি তার ডান সাবট্রি দ্বারা অনুসরণ করার আগে অতিক্রম করা হয়। তাই, 5 এর বাম দিকের সমস্ত মান এর বাম সাবট্রির অন্তর্গত এবং ডানদিকের সমস্ত মান তার ডান সাবট্রির অন্তর্গত।
অনুক্রম
2-3-4 ← 5 → 6-8-10
- এখন বাম সাবট্রির জন্য উপরের মতই করুন।
বাম সাবট্রির প্রি-অর্ডার ট্রাভার্সাল হল 3 -2-4। তাই 3 রুট হয়ে যায়।
ইনঅর্ডার ট্রাভার্সাল আরও বিভক্ত 2 ← 3 → 4
- এখন ডান সাবট্রির জন্য উপরের মতই করুন।
ডান সাবট্রির প্রি-অর্ডার ট্রাভার্সাল হল 8 -6-10। তাই 8 রুট হয়ে যায়।
ইনঅর্ডার ট্রাভার্সাল আরও বিভক্ত 6 ← 8 → 10
সুতরাং, এইভাবে আমরা প্রদত্ত প্রিঅর্ডার এবং ইনঅর্ডার ট্রাভার্সাল থেকে আসল গাছটি তৈরি করেছি।
