एक बाइनरी ट्री एक विशेष प्रकार का पेड़ है जिसमें पेड़ के प्रत्येक नोड में अधिकतम दो चाइल्ड नोड हो सकते हैं। इन चाइल्ड नोड्स को राइट चाइल्ड और लेफ्ट चाइल्ड के रूप में जाना जाता है।
एक साधारण बाइनरी ट्री है -
पेड़ों का प्रतिनिधित्व करने के दो तरीके हैं,
- गतिशील नोड प्रतिनिधित्व जो लिंक की गई सूची का उपयोग करता है
- अनुक्रमिक प्रतिनिधित्व जो सरणी का उपयोग करता है।
यहां, हम बाइनरी ट्री के सरणी प्रतिनिधित्व के बारे में चर्चा करेंगे। इसके लिए हमें बीटी के नोड्स को नंबर देना होगा। यह संख्या 0 से (n-1) या 1 से n तक शुरू हो सकती है।
सरणी में नोड्स और उनके माता-पिता और चाइल्ड नोड्स की स्थिति प्राप्त करें।
जब हम 0 अनुक्रमणिका आधारित अनुक्रमण, . का उपयोग करते हैं
मान लीजिए पैरेंट नोड एक इंडेक्स पी है।
फिर, लेफ्ट_चाइल्ड नोड इंडेक्स (2*p)+ 1 पर है।
राइट_चाइल्ड नोड इंडेक्स (2*p) + 2 पर है।
रूट नोड इंडेक्स 0 पर है।
left_child इंडेक्स 1 पर है।
राइट_चाइल्ड इंडेक्स 2 पर है।
जब हम 1 अनुक्रमणिका आधारित अनुक्रमण, . का उपयोग करते हैं
मान लीजिए पैरेंट नोड इंडेक्स p, . पर है
राइट_नोड इंडेक्स (2*p) पर है।
लेफ्ट_नोड इंडेक्स (2*p)+1 . पर है ।
रूट नोड इंडेक्स 1 पर है।
left_child इंडेक्स 2 पर है।
राइट_चाइल्ड इंडेक्स 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-----