একটি বাইনারি গাছ হল একটি বিশেষ ধরনের গাছ যেখানে গাছের প্রতিটি নোডে সর্বাধিক দুটি চাইল্ড নোড থাকতে পারে। এই শিশু নোডগুলি ডান শিশু এবং বাম শিশু হিসাবে পরিচিত৷
একটি সাধারণ বাইনারি গাছ হল −
গাছের প্রতিনিধিত্ব করার জন্য, দুটি উপায় আছে,
- ডাইনামিক নোড উপস্থাপনা যা লিঙ্ক করা তালিকা ব্যবহার করে
- অনুক্রমিক উপস্থাপনা যা অ্যারে ব্যবহার করে।
এখানে, আমরা বাইনারি গাছের অ্যারে উপস্থাপনা সম্পর্কে আলোচনা করব। এর জন্য আমাদের BT এর নোডগুলিকে নম্বর দিতে হবে। এই সংখ্যাকরণ 0 থেকে (n-1) বা 1 থেকে n পর্যন্ত শুরু হতে পারে।
অ্যারেতে নোডের অবস্থান এবং তাদের পিতামাতা এবং চাইল্ড নোডগুলি বের করা যাক৷
যখন আমরা 0 সূচক ভিত্তিক সিকোয়েন্সিং, ব্যবহার করি
ধরুন প্যারেন্ট নোড হল একটি ইনডেক্স p.
তারপর, বাম_চাইল্ড নোডটি ইনডেক্সে (2*p)+ 1।
ডান_চাইল্ড নোডটি ইনডেক্সে (2*p) + 2।
রুট নোড ইনডেক্স 0 এ রয়েছে।
left_child সূচক 1 এ আছে।
Right_child সূচক 2 এ রয়েছে।
যখন আমরা 1 সূচক ভিত্তিক সিকোয়েন্সিং, ব্যবহার করি
ধরুন প্যারেন্ট নোড index p, এ আছে
Right_node index (2*p) এ আছে
Left_node index (2*p)+1 এ আছে .
রুট নোড ইনডেক্স 1 এ রয়েছে।
left_child সূচক 2 এ আছে।
Right_child সূচক 3 এ আছে।
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
char tree[10];
int rootnode(char key){
if(tree[0] != '\0')
cout<<"Tree already had root";
else
tree[0] = key;
return 0;
}
int leftchild(char key, int parent){
if(tree[parent] == '\0')
cout <<"\nCan't set child at"<<(parent * 2) + 1<<" , no parent found";
else
tree[(parent * 2) + 1] = key;
return 0;
}
int rightchild(char key, int parent){
if(tree[parent] == '\0')
cout<<"\nCan't set child at"<<(parent * 2) + 2<<" , no parent found";
else
tree[(parent * 2) + 2] = key;
return 0;
}
int traversetree(){
cout << "\n";
for(int i = 0; i < 10; i++){
if(tree[i] != '\0')
cout<<tree[i];
else
cout<<"-";
}
return 0;
}
int main(){
rootnode('A');
rightchild('C', 2);
leftchild('D', 0);
rightchild('E', 1);
rightchild('F', 2);
traversetree();
return 0;
} আউটপুট
Can't set child at6 , no parent found Can't set child at6 , no parent found AD--E-----
