এখানে আমরা থ্রেডেড বাইনারি ট্রি ডেটা স্ট্রাকচার দেখব। আমরা জানি বাইনারি ট্রি নোডে সর্বোচ্চ দুটি চাইল্ড থাকতে পারে। কিন্তু যদি তাদের শুধু একটা চাইল্ড থাকে, বা কোনো চাইল্ড না থাকে, তবে লিংকড লিস্ট রিপ্রেজেন্টেশনে লিংক পার্ট নাল থাকে। থ্রেডেড বাইনারি ট্রি রিপ্রেজেন্টেশন ব্যবহার করে, আমরা সেই খালি লিংকগুলো রিয়ুজ করতে পারি কিছু থ্রেড বানিয়ে।
যদি একটা নোডের খালি লেফট বা রাইট চাইল্ড এরিয়া থাকে, তবে সেটাকে থ্রেড হিসেবে ব্যবহার করা হয়। থ্রেডেড বাইনারি ট্রির দুটি টাইপ আছে। সিঙ্গল থ্রেডেড ট্রি বা ফুলি থ্রেডেড বাইনারি ট্রি। সিঙ্গল থ্রেডেড মোডে, আরও দুটি ভেরিয়েশন আছে। লেফট থ্রেডেড এবং রাইট থ্রেডেড।
লেফট থ্রেডেড মোডে যদি কোনো নোডের লেফট চাইল্ড না থাকে, তবে লেফট পয়েন্টার তার ইনঅর্ডার প্রিডিসেসরকে পয়েন্ট করবে, একইভাবে রাইট থ্রেডেড মোডে যদি কোনো নোডের রাইট চাইল্ড না থাকে, তবে রাইট পয়েন্টার তার ইনঅর্ডার সাকসেসরকে পয়েন্ট করবে। উভয় কেসে, যদি কোনো সাকসেসর বা প্রিডিসেসর না থাকে, তবে সেটি হেডার নোডকে পয়েন্ট করবে।
ফুলি থ্রেডেড বাইনারি ট্রিতে, প্রতিটি নোডের পাঁচটি ফিল্ড থাকে। তিনটি নরমাল বাইনারি ট্রি নোডের মত, আর দুটি ফিল্ড বুলিয়ান ভ্যালু স্টোর করতে যা ডিনোট করে সেই সাইডের লিংক একচুই অ্যাকচুয়াল লিংক নাকি থ্রেড।
| Left Thread Flag | Left Link | Data | Right Link | Right Thread Flag |
এগুলো লেফট এবং রাইট থ্রেডেড ট্রির উদাহরণ
এটি ফুলি থ্রেডেড বাইনারি ট্রি
