১৮-১ঃ Level Order Traversal of Binary Tree থিওরি
Last updated
Last updated
প্রথমে জেনে নেয়া যাক , একটি বাইনারী ট্রি বা Overall Tree এর Level বলতে কী বুঝানো হয় । একটি ট্রি এর প্রত্যেকটি ফ্লোর আমরা বলতে পারি ঐ ট্রি এর লেভেল। একটি চিত্রের মাধ্যমে ভালোভাবে বিষয়টি জেনে নেয়া যাক।
চিত্রের Tree এর Root Node টি যে ফ্লোর এ আছে তাকে আমরা গ্রাউন্ড ফ্লোরের সাথে চিন্তা করতে পারি। এবং নিয়মানুযায়ী এই ফ্লোর টিকে / লেভেল টিকে বলা হয়ে O th ( Zero-th) লেভেল।
নিচে দেখে নেয়া যাক কোন লেভেল এ কোন কোন Node রয়েছে . Level 0 -> A Level 1 -> B , C Level 2 -> D, E , F Level 3 -> G , H Level 4 -> I
এখন আমরা দেখবো , কীভাবে একটি Binary Tree তে Level Order Traversal করতে পারি।
Traversal মানে হলো প্রত্যেকটি Node ভিজিট করা / প্রত্যেকটি Node এক্সেস করা, যেভাবে আমরা একটি Array এর প্রত্যেকটি Index এক্সেস করতে পারতাম।
এরপর Level Order বলতে বুঝানো হয়েছে আমরা Level / ফ্লোর wise প্রত্যেকটি Node কে এক্সেস করবো। যেমনঃ আমরা শুরু করবো Level 0 থেকে . Level 0 তে অবস্থিত সকল Node কে এক্সেস করে আমরা যাবো এর পরবর্তী Level এর Node গুলোতে অর্থাৎ Level 1 এ থাকা Node গুলোতে।
এখন দেখে নেয়া যাক , কীভাবে আমরা আমাদের previous learning গুলো হতে এই traversal টি implement করতে পারি।
আমরা একটি জিনিস নিয়ে চিন্তা করি প্রথমে। ধরুন , কিছু মানুষ প্রথম দিন একটি টিকেট কাউন্টারে এসেছে। এবং তারা পরবর্তী দিন যারা আসবে তাদের নাম সেই টিকেট কাউন্টারে দিয়ে গেলো। এখন , টিকেট কাউন্টারের ফার্স্ট প্রায়োরিটি হবে , প্রথম দিন যারা এসেছে তাদেরকে আগে সার্ভিস দেয়া। এরপর পরের দিন যারা আসবে তাদের নাম কাউন্টারে লিখে ফেলা । এবং পরের দিন এদের সার্ভিস দেয়া , এবং এর ও পরবর্তী দিন যারা আসবে তাদের নাম লিখে ফেলা। এখন এই ধরনের Serial যে কাজ তা করার জন্য আমরা DS এর Queue ব্যবহার করে থাকি।
Working Procedure :
প্রথমে একটি Queue তৈরি করা , যার মাধ্যমে আমরা System টি operate করবো
Root Node অর্থাৎ Level 0 তে যে Node আছে তা Manually queue তে push করে দিবো।
Level 0 এর Node গুলো ভিজিট করে আমরা তার Children গুলোকে Queue তে পুশ করে দিবো।
এবং যে Node গুলোর অপারেশন শেষ তা আমরা Queue থেকে Remove করে দিবো।
এইভাবে করে বাকিগুলো Automatically চলতে থাকবে।
