मेन्यू

सी ++ में बाइनरी ट्री डेटा संरचना

binary tree data structure c

C ++ में बाइनरी ट्री पर यह इन-डेप्थ ट्यूटोरियल C ++ में बाइनरी ट्रीज़ के प्रकार, रिप्रेजेंटेशन, ट्रैवर्सल, एप्लीकेशन और इंप्लीमेंटेशन को समझाता है:



एक द्विआधारी वृक्ष एक व्यापक रूप से उपयोग किया जाने वाला वृक्ष डेटा संरचना है। जब किसी पेड़ के प्रत्येक नोड में अधिकतम दो बच्चे होते हैं तो पेड़ को बाइनरी ट्री कहा जाता है।

तो एक सामान्य बाइनरी ट्री में निम्नलिखित घटक होंगे:

  • एक बाएँ उपप्रकार
  • एक रूट नोड
  • एक सही उपशीर्षक

=> इस श्रृंखला में सी ++ ट्यूटोरियल की पूरी सूची देखें।



सी ++ में बाइनरी ट्री

आप क्या सीखेंगे:





बाइनरी ट्री सी ++ में

बाइनरी ट्री का एक चित्रमय प्रतिनिधित्व नीचे दिखाया गया है:

एक बाइनरी ट्री का सचित्र प्रतिनिधित्व

किसी दिए गए बाइनरी ट्री में, किसी भी स्तर पर नोड्स की अधिकतम संख्या 2 हैएल -1जहां 'l' स्तर संख्या है।

इस प्रकार 1 के स्तर पर रूट नोड के मामले में, नोड्स की अधिकतम संख्या = 21-1= २०= 1

जैसा कि बाइनरी ट्री में प्रत्येक नोड में अधिकतम दो नोड होते हैं, अगले स्तर पर अधिकतम नोड्स 2 * 2 होंगेएल -1।

गहराई या ऊँचाई के बाइनरी ट्री को देखते हुए, ऊँचाई h = 2 के बाइनरी ट्री में नोड्स की अधिकतम संख्याएच- 1।

इसलिए ऊँचाई 3 के बाइनरी ट्री में (ऊपर दिखाया गया है), नोड्स की अधिकतम संख्या = 2३-1 = 7।

अब हम विभिन्न प्रकार के बाइनरी पेड़ों पर चर्चा करते हैं।

बाइनरी ट्री के प्रकार

निम्नलिखित बाइनरी पेड़ों के सबसे आम प्रकार हैं।

(1) पूर्ण बाइनरी ट्री

एक बाइनरी ट्री जिसमें प्रत्येक नोड में 0 या 2 बच्चे हैं, को पूर्ण बाइनरी ट्री कहा जाता है।

पूर्ण बाइनरी ट्री

ऊपर दिखाया गया एक पूर्ण बाइनरी ट्री है जिसमें हम देख सकते हैं कि पत्ती के नोड्स को छोड़कर इसके सभी नोड्स में दो बच्चे हैं। यदि L पत्ती नोड्स की संख्या है और 'l' आंतरिक या गैर-पत्ती नोड्स की संख्या है, तो पूर्ण बाइनरी ट्री, L = l + 1 के लिए।

# 2) पूरा बाइनरी ट्री

एक पूर्ण बाइनरी ट्री में अंतिम स्तर को छोड़कर सभी स्तर भरे होते हैं और अंतिम स्तर के सभी नोड्स बायीं ओर होते हैं।

पूरा बाइनरी ट्री

ऊपर दिखाया गया पेड़ एक पूर्ण बाइनरी पेड़ है। पूर्ण बाइनरी ट्री का एक विशिष्ट उदाहरण एक बाइनरी हीप है जिसे हम बाद के ट्यूटोरियल में चर्चा करेंगे।

स्थानापन्न (0,0)

# 3) परफेक्ट बाइनरी ट्री

एक बाइनरी ट्री को तब सही कहा जाता है जब उसके सभी आंतरिक नोड्स में दो बच्चे होते हैं और सभी पत्ती नोड्स एक ही स्तर पर होते हैं।

सही बाइनरी ट्री

ऊपर दिखाया गया एक बाइनरी ट्री उदाहरण एक पूर्ण बाइनरी ट्री है क्योंकि इसके प्रत्येक नोड में दो बच्चे हैं और सभी पत्ती नोड्स समान स्तर पर हैं।

ऊँचाई h का एक सही बाइनरी ट्री 2 हैएच- 1 नंबर की नोड्स।

# 4) एक डीजेनरेट ट्री

एक द्विआधारी वृक्ष जहां प्रत्येक आंतरिक नोड में केवल एक बच्चा होता है उसे पतित वृक्ष कहा जाता है।

पतित वृक्ष

ऊपर दिखाया गया पेड़ एक पतित पेड़ है। जहां तक ​​इस पेड़ के प्रदर्शन का संबंध है, पतित पेड़ लिंक-सूचियों के समान हैं।

# 5) संतुलित बाइनरी ट्री

एक बाइनरी ट्री जिसमें प्रत्येक नोड के दो उपप्रकारों की गहराई कभी 1 से अधिक नहीं होती है, एक संतुलित बाइनरी ट्री कहलाता है।

संतुलित बाइनरी ट्री

ऊपर दिखाया गया बाइनरी ट्री एक संतुलित बाइनरी ट्री है, क्योंकि प्रत्येक नोड के दो उपप्रकारों की गहराई 1. एवीएल पेड़ों से अधिक नहीं है, जिनके बारे में हम अपने बाद के ट्यूटोरियल में चर्चा करने वाले हैं, एक सामान्य संतुलित पेड़ हैं।

बाइनरी ट्री प्रतिनिधित्व

एक बाइनरी ट्री को दो तरीकों से मेमोरी आवंटित की जाती है।

(१) अनुक्रमिक प्रतिनिधित्व

पेड़ डेटा संरचना को स्टोर करने की यह सबसे सरल तकनीक है। ट्री नोड्स को संग्रहीत करने के लिए एक सरणी का उपयोग किया जाता है। एक पेड़ में नोड्स की संख्या सरणी के आकार को परिभाषित करती है। पेड़ की जड़ नोड सरणी में पहले सूचकांक पर संग्रहीत है।

सामान्य तौर पर, यदि एक नोड i पर संग्रहीत हैवेंस्थान तब उसके बाएँ और दाएँ बच्चे को क्रमशः 2i और 2i + 1 स्थान पर संग्रहीत किया जाता है।

निम्नलिखित बाइनरी ट्री पर विचार करें।

नमूना बाइनरी ट्री

उपरोक्त बाइनरी ट्री का क्रमिक प्रतिनिधित्व इस प्रकार है:

बाइनरी ट्री का क्रमिक प्रतिनिधित्व

उपरोक्त प्रतिनिधित्व में, हम देखते हैं कि प्रत्येक नोड के बाएं और दाएं बच्चे को क्रमशः 2 * (नोड_लोकेशन) और 2 * (नोड_लोकेशन) +1 पर संग्रहीत किया जाता है।

उदाहरण के लिए, सरणी में नोड 3 का स्थान 3 है। इसलिए इसे छोड़ दिया गया बच्चा 2 * 3 = 6 पर रखा जाएगा। इसका दायां बच्चा स्थान 2 * 3 +1 = 7 पर होगा। जैसा कि हम सरणी में देख सकते हैं, बच्चे 3 में से जो 6 और 7 हैं, उन्हें 6 और 7 के स्थान पर रखा गया है।

पेड़ का क्रमिक निरूपण अकुशल है क्योंकि जिस सरणी का उपयोग पेड़ के नोड्स को संग्रहीत करने के लिए किया जाता है वह स्मृति में बहुत अधिक स्थान लेता है। जैसे-जैसे पेड़ बढ़ता है, यह प्रतिनिधित्व अक्षम और प्रबंधन करना मुश्किल हो जाता है।

लिंक्ड लिस्ट में ट्री नोड्स को स्टोर करके इस कमी को दूर किया जाता है। ध्यान दें कि यदि पेड़ खाली है, तो रूट नोड स्टोर करने वाला पहला स्थान 0 पर सेट किया जाएगा।

# 2) लिंक्ड-लिस्ट प्रतिनिधित्व

इस प्रकार के प्रतिनिधित्व में, पेड़ नोड्स को संग्रहीत करने के लिए एक लिंक की गई सूची का उपयोग किया जाता है। गैर-संदर्भ स्थानों में मेमोरी में कई नोड्स बिखरे हुए हैं और नोड्स पेड़ की तरह माता-पिता के बच्चे के रिश्ते का उपयोग करके जुड़े हुए हैं।

निम्नलिखित आरेख एक पेड़ के लिए एक लिंक्ड सूची प्रतिनिधित्व दिखाता है।

लिंक्ड-लिस्ट प्रतिनिधित्व

जैसा कि उपरोक्त प्रतिनिधित्व में दिखाया गया है, प्रत्येक लिंक किए गए सूची नोड में तीन घटक हैं:

  • बायाँ सूचक
  • डेटा भाग
  • सही सूचक

बाएं पॉइंटर में नोड के बाएं बच्चे के लिए एक पॉइंटर है; दाएं पॉइंटर में नोड के दाएं बच्चे के लिए एक पॉइंटर होता है जबकि डेटा भाग में नोड का वास्तविक डेटा होता है। यदि किसी दिए गए नोड (लीफ नोड) के लिए कोई बच्चे नहीं हैं, तो उस नोड के लिए बाएं और दाएं संकेत ऊपर की आकृति में दिखाए गए अनुसार शून्य करने के लिए सेट किए गए हैं।

सी ++ में बाइनरी ट्री कार्यान्वयन

अगला, हम C ++ में एक लिंक सूची प्रतिनिधित्व का उपयोग करके एक बाइनरी ट्री प्रोग्राम विकसित करते हैं। हम एक नोड को घोषित करने के लिए एक संरचना का उपयोग करते हैं और फिर एक वर्ग का उपयोग करते हुए, हम नोड्स की एक लिंक्ड सूची विकसित करते हैं।

#include using namespace std; struct bintree_node{ bintree_node *left; bintree_node *right; int data; } ; class bst{ bintree_node *root; public: bst(){ root=NULL; } int isempty() { return(root==NULL); } void insert(int item); void displayBinTree(); void printBinTree(bintree_node *); }; void bst::insert(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL){ parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bst::displayBinTree(){ printBinTree(root); } void bst::printBinTree(bintree_node *ptr){ if(ptr!=NULL){ printBinTree(ptr->left); cout<<' '<data<<' '; printBinTree(ptr->right); } } int main(){ bst b; b.insert(20); b.insert(10); b.insert(5); b.insert(15); b.insert(40); b.insert(45); b.insert(30); cout<<'Binary tree created: '<

आउटपुट:

बाइनरी ट्री बनाया:

5 10 15 20 30 40 45

बुलबुला सी + + एल्गोरिथ्म

बाइनरी ट्री ट्रैवर्सल

हमने पहले ही पेड़ों पर अपने मूल ट्यूटोरियल में ट्रैवर्सल्स पर चर्चा की है। इस खंड में, हम एक प्रोग्राम लागू करते हैं जो बाइनरी ट्री में नोड्स सम्मिलित करता है और बाइनरी ट्री के लिए सभी तीन ट्रैवर्सल्स यानी इनवर्टर, प्रीऑर्डर और पोस्टऑर्डर को भी प्रदर्शित करता है।

#include using namespace std; //binary tree node declaration struct bintree_node{ bintree_node *left; bintree_node *right; char data; } ; class bintree_class{ bintree_node *root; public: bintree_class(){ root=NULL; } int isempty() { return(root==NULL); } void insert_node(int item); void inorder_seq(); void inorder(bintree_node *); void postorder_seq(); void postorder(bintree_node *); void preorder_seq(); void preorder(bintree_node *); }; void bintree_class::insert_node(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL) { parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bintree_class::inorder_seq() { inorder(root); } void bintree_class::inorder(bintree_node *ptr) { if(ptr!=NULL){ inorder(ptr->left); cout<<' '<data<<' '; inorder(ptr->right); } } void bintree_class::postorder_seq() { postorder(root); } void bintree_class::postorder(bintree_node *ptr) { if(ptr!=NULL){ postorder(ptr->left); postorder(ptr->right); cout<<' '<data<<' '; } } void bintree_class::preorder_seq() { preorder(root); } void bintree_class::preorder(bintree_node *ptr) { if(ptr!=NULL){ cout<<' '<data<<' '; preorder(ptr->left); preorder(ptr->right); } } int main() { bintree_class bintree; bintree.insert_node('A'); bintree.insert_node('B'); bintree.insert_node('C'); bintree.insert_node('D'); bintree.insert_node('E'); bintree.insert_node('F'); bintree.insert_node('G'); cout<<'Inorder traversal:'<

आउटपुट:

इनवर्टर ट्रैवर्सल:

ए बी सी डी ई एफ एफ जी

मेल ऑर्डर ट्रैवर्सल:

जी एफ ई डी सी बी ए

सीमा पारगमन:

ए बी सी डी ई एफ एफ जी

बाइनरी ट्री के अनुप्रयोग

डेटा के भंडारण के लिए कई अनुप्रयोगों में एक बाइनरी ट्री का उपयोग किया जाता है।

बाइनरी पेड़ों के कुछ महत्वपूर्ण अनुप्रयोग नीचे सूचीबद्ध हैं:

  • द्विआधारी खोज पेड़: बाइनरी ट्री का उपयोग बाइनरी सर्च ट्री के निर्माण के लिए किया जाता है जिसका उपयोग कई खोज अनुप्रयोगों जैसे कई भाषा पुस्तकालयों में सेट और मैप्स में किया जाता है।
  • हैश पेड़: मुख्य रूप से विशेष छवि हस्ताक्षर अनुप्रयोगों में हैश को सत्यापित करने के लिए उपयोग किया जाता है।
  • हीप्स: हीप्स का उपयोग प्राथमिकता कतार को लागू करने के लिए किया जाता है जो कि राउटर, ऑपरेटिंग सिस्टम में प्रोसेसर को शेड्यूल करने आदि के लिए उपयोग किया जाता है।
  • हफ़मैन कोडिंग: हफ़मैन कोडिंग ट्री का उपयोग संपीड़न एल्गोरिदम (छवि संपीड़न की तरह) के साथ-साथ क्रिप्टोग्राफ़िक अनुप्रयोगों में किया जाता है।
  • सिंटेक्स ट्री: कंपाइलर अक्सर वाक्यविन्यास पेड़ों का निर्माण करते हैं जो कार्यक्रम में उपयोग किए जाने वाले भावों को पार्स करने के लिए कुछ भी नहीं है।

निष्कर्ष

बाइनरी ट्री व्यापक रूप से सॉफ्टवेयर उद्योग में डेटा संरचनाओं का उपयोग किया जाता है। द्विआधारी पेड़ वे पेड़ हैं जिनके नोड्स में सबसे अधिक दो बच्चे नोड हैं। हमने विभिन्न प्रकार के बाइनरी पेड़ देखे हैं जैसे एक पूर्ण बाइनरी ट्री, एक पूर्ण बाइनरी ट्री, एक परफेक्ट बाइनरी ट्री, एक डीजनरेटेड बाइनरी ट्री, एक संतुलित बाइनरी ट्री, आदि।

बाइनरी ट्री डेटा को इनवर्टर, प्रीऑर्डर और पोस्टऑर्डर ट्रावर्सल तकनीकों का उपयोग करके भी ट्रैवर्स किया जा सकता है, जिसे हमने अपने पिछले ट्यूटोरियल में देखा है। स्मृति में, एक बाइनरी ट्री को एक लिंक्ड सूची (गैर-सन्निहित मेमोरी) या सरणियों (अनुक्रमिक प्रतिनिधित्व) का उपयोग करके दिखाया जा सकता है।

सरणियों की तुलना में लिंक्ड सूची प्रतिनिधित्व अधिक कुशल है, क्योंकि सरणियाँ बहुत अधिक स्थान लेती हैं।

=> यहां सर्वश्रेष्ठ C ++ प्रशिक्षण ट्यूटोरियल देखें।

अनुशंसित पाठ

^