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