বাইনারি ট্রি

আজকে অসাধারন একটা বিষয় পড়লাম । সেটা হচ্ছে বাইনারি ট্রি। সত্যি বলতে বাইনারি ট্রি বলতে ভালো কিছু আমি কিছুক্ষন আগে  পর্যন্ত জানতাম না। যাক, কিছুটা যখন ধারনা হল সেটা শেয়ার করি।
এটি পড়তে গিয়ে আমি যে প্রশ্নগুলোর সম্মুখীন হয়েছি সেগুলো হল
প্রশ্ন ১ঃ ট্রি কী?
উত্তরঃ সরল চক্র ছাড়া যে কোন সংযুক্ত গ্রাফকেই ট্রি বলে। ট্রি হচ্ছে অনির্দিষ্ট গ্রাফ যার যে কোন দুইটি ভারটিক্স একই পাথ(path) এ অবস্থিত।



ট্রি পরিচিতি সংক্ষেপেঃ  সবচেয়ে উপরের নোডকে বলা হয় মূল(root)। কোন একটি নোড আর একটি নোডের অধিনে থাকলে সেটাকে চিলড্রেন নোড, আর যার অধিনে আছে তাকে প্যারেন্ট নোড বলে। সব শেষের যে নোড থাকে, যার আর কোন চিলড্রেন নেই তাকে লিভস বা পাতা বলে। নিচের চিত্রে দেওয়া হল।

tree

--------------------------
                        j<<<root(মূল)
                 
                   /       \
                  f          k
               /    \         \
              a      h       z   <<< পাতা( leaves)
প্রশ্ন ২ঃ বাইনারি ট্রি কি?
উত্তরঃ যে ট্রিতে প্রতিটি নোডের দুইয়ের অধিক চিলড্রেন নেই তাকে বাইনারি ট্রি বলে।
উপরের চিত্রটিই হল বাইনারি ট্রির চিত্র। যেখানে দেখা প্রতিটি প্যারেন্ট নোডে দুইয়ের বেশি চিলড্রেন নেই।
বাইনারি ট্রিতে যে শিশু নোড দুইটি থাকে তার বাম পাশের টাকে বলে লেফট চিলড্রেন এবং ডান পাশের টিকে বলে রাইট চিলড্রেন।

প্রশ্ন ৩ঃ সিতে কিভাবে বাইনারি ট্রি রিপ্রেজেন্ট করব?
উত্তরঃ সাধারণত একটি ট্রির টপ নোড বা মূলকে পয়েন্টার দ্বারা প্রকাশ করা হয়। যদি ট্রি টি খালি হয় তবে তার মূল বা রুট হবে শুন্য।
একটি ট্রি নোডের নিম্মক্ত অংশ থাকে।

1. Data
2. pointer to left child
3. pointer to right child

সিতে সাধারণত আমরা স্ট্রাকচার দিয়ে ট্রি রিপ্রেজেন্ট করতে পারি।

struct node

         {
              int data;
               struct node *left;
               struct  node *right;
          };

এবার সিতে চারটা নোড যুক্ত একটা সিম্পল ট্রি তৈরি করি।

      tree
      ----
       1    <-- root
     /   \
    2     3  
   /   
  4