trees c basic terminology
C ++ ट्रीज़ पर इन-डेप्थ ट्यूटोरियल इन ट्री टाइप्स, ट्री ट्रैवर्सल टेक्निक्स एंड बेसिक टर्मिनोलॉजी विद पिक्चर्स एंड उदाहरण कार्यक्रम:
इस सी ++ श्रृंखला में, अब तक हमने स्थैतिक और गतिशील प्रकृति दोनों के रैखिक डेटा संरचना को देखा है। अब हम गैर-रैखिक डेटा संरचना के साथ आगे बढ़ेंगे। इस श्रेणी में पहली डेटा संरचना 'पेड़' है।
पेड़ गैर-रेखीय श्रेणीबद्ध डेटा संरचनाएं हैं। एक पेड़ 'किनारों' के माध्यम से एक दूसरे से जुड़े नोड्स का एक संग्रह है जो या तो निर्देशित या अप्रत्यक्ष हैं। नोड्स में से एक को 'रूट नोड' के रूप में नामित किया गया है और शेष नोड्स को बाल नोड या रूट नोड के पत्ती नोड्स कहा जाता है।
सामान्य तौर पर, प्रत्येक नोड में कई बच्चे हो सकते हैं लेकिन केवल एक मूल नोड होता है।
=> संपूर्ण C ++ प्रशिक्षण श्रृंखला देखें
अजगर सेलेनियम पाठ द्वारा तत्व खोजता है
एक पेड़ के नोड्स या तो बहन नोड्स के समान स्तर पर होते हैं या उनके माता-पिता-बच्चे के संबंध हो सकते हैं। एक ही माता-पिता के साथ नोड्स सिबलिंग नोड्स हैं।
आप क्या सीखेंगे:
C ++ में पेड़
नीचे दिया गया एक उदाहरण का पेड़ है जिसके विभिन्न भाग हैं।
आइए हम कुछ मूल शब्दों की परिभाषाओं से गुजरते हैं जिनका उपयोग हम पेड़ों के लिए करते हैं।
- रूट नोड: यह पेड़ की पदानुक्रम में सबसे ऊपरी नोड है। उपरोक्त आरेख में, नोड नोड रूट नोड है। ध्यान दें कि रूट नोड में कोई अभिभावक नहीं है।
- पर्ण्सन्धि: यह पेड़ के पदानुक्रम में सबसे नीचे का तल है। लीफ नोड्स वे नोड्स होते हैं जिनमें कोई बच्चा नोड नहीं होता है। उन्हें बाहरी नोड्स के रूप में भी जाना जाता है। उपरोक्त पेड़ में नोड्स ई, एफ, जी, एच और सी सभी पत्ती नोड्स हैं।
- उपप्रकार: सबट्री एक नोड के विभिन्न वंशज का प्रतिनिधित्व करता है जब रूट शून्य नहीं होता है। एक पेड़ में आमतौर पर एक मूल नोड होता है और एक या अधिक उपप्रकार होते हैं। उपरोक्त आरेख में, (B-E, B-F) और (D-G, D-H) उपप्रकार हैं।
- मूल नोड: रूट नोड को छोड़कर कोई भी नोड जिसमें एक बच्चे का नोड है और माता-पिता की ओर एक किनारा है।
- पूर्वज नोड: यह रूट से उस नोड के लिए एक पूर्ववर्ती नोड है। ध्यान दें कि रूट का कोई पूर्वज नहीं है। उपरोक्त आरेख में, A और B, E के पूर्वज हैं।
- चाभी: यह एक नोड के मूल्य का प्रतिनिधित्व करता है।
- स्तर: एक नोड की पीढ़ी का प्रतिनिधित्व करता है। एक रूट नोड हमेशा स्तर 1 पर होता है। रूट के चाइल्ड नोड्स स्तर 2 पर हैं, रूट के पोते 3 स्तर पर हैं और इसी तरह। सामान्य तौर पर, प्रत्येक नोड अपने माता-पिता की तुलना में उच्च स्तर पर होता है।
- पथ: रास्ता लगातार किनारों का एक क्रम है। उपरोक्त आरेख में, E का मार्ग A => B-> E है।
- डिग्री: नोड की डिग्री उन बच्चों की संख्या को इंगित करती है जो एक नोड के पास हैं। उपरोक्त आरेख में, बी और डी की डिग्री 2 प्रत्येक है जबकि सी की डिग्री 0 है।
सी ++ पेड़ों के प्रकार
नीचे दिए गए चित्र में दिखाए गए अनुसार पेड़ डेटा संरचना को निम्नलिखित उपप्रकारों में वर्गीकृत किया जा सकता है।
(१) सामान्य वृक्ष
सामान्य वृक्ष एक वृक्ष का मूल प्रतिनिधित्व है। इसमें एक नोड और एक या अधिक बच्चे नोड हैं। शीर्ष-स्तरीय नोड यानी रूट नोड 1 स्तर पर मौजूद है और अन्य सभी नोड विभिन्न स्तरों पर मौजूद हो सकते हैं।
एक जनरल ट्री को नीचे दिए गए आंकड़े में दिखाया गया है।
जैसा कि उपरोक्त आंकड़े में दिखाया गया है, एक सामान्य पेड़ में किसी भी संख्या में उपप्रकार हो सकते हैं। नोड बी, सी और डी 2 स्तर पर मौजूद हैं और नोड्स सिबल कर रहे हैं। इसी तरह, नोड ई, एफ, जी, और एच भी नोड्स सिबलिंग हैं।
विभिन्न स्तरों पर मौजूद नोड्स अभिभावक-बच्चे के संबंध को प्रदर्शित कर सकते हैं। उपरोक्त आकृति में, नोड्स बी, सी और डी, ए। नोड्स के बच्चे हैं और एफ बी के बच्चे हैं जबकि नोड्स जी और एच डी के बच्चे हैं।
सामान्य पेड़ C ++ कार्यान्वयन का उपयोग करके नीचे प्रदर्शित किया गया है:
#include using namespace std; //declaration for new tree node struct node { int data; struct node *left; struct node *right; }; //allocates new node struct node* newNode(int data) { // declare and allocate new node struct node* node = new struct node(); node->data = data; // Assign data to this node // Initialize left and right children as NULL node->left = NULL; node->right = NULL; return(node); } int main() { /*create root node*/ struct node *rootNode = newNode(10); cout<<'General tree created is as follows:'<data<left = newNode(20); rootNode->right = newNode(30); cout<<' '<left->data<<' '<right->data; cout<left->left = newNode(40); cout<<' '<<'/'<left->left->data; return 0; }
आउटपुट:
सामान्य पेड़ का निर्माण इस प्रकार है:
१०
/ _
२० ३०
/
४०
# 2) वन
जब भी हम पेड़ के जड़ और किनारों को अगले स्तर के तत्वों और जड़ से जुड़ते हुए हटाते हैं, तो हम नीचे दिखाए गए पेड़ों के निराशाजनक सेट प्राप्त करते हैं।
उपरोक्त आकृति में, हमने रूट नोड ए और तीन किनारों को हटाकर दो वन प्राप्त किए जो रूट नोड को बी, सी, और डी से जोड़ रहे थे।
# 3) बाइनरी ट्री
एक पेड़ डेटा संरचना जिसमें प्रत्येक नोड में अधिकतम दो बच्चे नोड होते हैं, एक बाइनरी ट्री कहलाता है। एक बाइनरी ट्री सबसे लोकप्रिय ट्री डेटा संरचना है और इसका उपयोग अभिव्यक्ति मूल्यांकन, डेटाबेस इत्यादि जैसे अनुप्रयोगों में किया जाता है।
निम्नलिखित आंकड़ा एक द्विआधारी वृक्ष को दर्शाता है।
उपरोक्त आकृति में, हम देखते हैं कि नोड ए, बी और डी में दो बच्चे हैं। एक बाइनरी ट्री जिसमें प्रत्येक नोड में बिल्कुल शून्य या दो बच्चे होते हैं, पूर्ण बाइनरी ट्री कहलाता है। इस पेड़ में, एक बच्चा नहीं है।
एक पूर्ण बाइनरी ट्री में एक बाइनरी ट्री होता है जो पूरी तरह से निम्नतम स्तर के अपवाद से भरा होता है जो बाएं से दाएं भरा होता है। ऊपर दिखाया गया बाइनरी ट्री एक पूर्ण बाइनरी ट्री है।
बाइनरी ट्री को प्रदर्शित करने के लिए एक सरल कार्यक्रम निम्नलिखित है। ध्यान दें कि ट्री का आउटपुट इनपुट ट्री का इनवर्टर ट्रैवर्सल अनुक्रम है।
#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
# 4) बाइनरी सर्च ट्री
ऑर्डर किए गए बाइनरी ट्री को बाइनरी सर्च ट्री कहा जाता है। एक बाइनरी सर्च ट्री में, बाईं ओर के नोड रूट नोड से कम होते हैं, जबकि दाईं ओर के नोड रूट नोड से अधिक या उसके बराबर होते हैं।
बाइनरी सर्च ट्री का एक उदाहरण नीचे दिखाया गया है।
उपरोक्त आंकड़े में, हम देख सकते हैं कि बाएं नोड्स सभी 20 से कम हैं जो मूल तत्व है। दूसरी ओर, दाएं नोड, रूट नोड से अधिक होते हैं। बाइनरी सर्च ट्री का उपयोग तकनीकों को खोजने और छांटने में किया जाता है।
# 5) अभिव्यक्ति ट्री
एक द्विआधारी वृक्ष जिसका उपयोग साधारण अंकगणितीय अभिव्यक्तियों के मूल्यांकन के लिए किया जाता है, एक अभिव्यक्ति वृक्ष कहलाता है।
एक सरल अभिव्यक्ति पेड़ नीचे दिखाया गया है।
उपरोक्त नमूना अभिव्यक्ति पेड़ में, हम अभिव्यक्ति (ए + बी) / (ए-बी) का प्रतिनिधित्व करते हैं। जैसा कि ऊपर की आकृति में दिखाया गया है, पेड़ के गैर-पत्ती नोड्स अभिव्यक्ति के ऑपरेटरों का प्रतिनिधित्व करते हैं जबकि पत्ती नोड्स ऑपरेंड का प्रतिनिधित्व करते हैं।
अभिव्यक्ति के पेड़ मुख्य रूप से बीजगणितीय अभिव्यक्तियों को हल करने के लिए उपयोग किए जाते हैं।
ट्री ट्रैवर्सल तकनीक
हमने रैखिक डेटा संरचनाएं जैसे सरणियाँ, लिंक की गई सूचियाँ, ढेर, कतारें इत्यादि देखी हैं। इन सभी डेटा संरचनाओं में एक सामान्य ट्रैवर्सिंग तकनीक होती है जो संरचना को केवल एक ही तरीके से विभाजित करती है यानी रैखिक रूप से।
लेकिन पेड़ों के मामले में, हमारे पास नीचे सूचीबद्ध के रूप में अलग-अलग ट्रैवर्सल तकनीकें हैं:
# 1) क्रम में: इस ट्रैवर्सल तकनीक में, हम बाएं सबट्री को पहले पार करते हैं, जब तक कि बाएं सबट्री में अधिक नोड नहीं होते हैं। इसके बाद, हम रूट नोड पर जाते हैं और फिर सही सबट्री को पार करने के लिए आगे बढ़ते हैं, जब तक कि सही सबट्री में ट्रैवस करने के लिए अधिक नोड नहीं होते हैं। इस प्रकार ऑडर ट्रैवर्सल का क्रम बचा है-> रूट-> राइट।
# 2) पूर्व-आदेश: प्रीऑर्डर ट्रैवर्सल तकनीक के लिए, हम रूट नोड को पहले प्रोसेस करते हैं, फिर हम पूरे लेफ्ट सबट्री को ट्रैवर्स करते हैं और अंत में, हम राइट सबट्री को पार करते हैं। इसलिए प्रीऑर्डर ट्रैवर्सल का क्रम रूट-> लेफ्ट-> राइट है।
# 3) पोस्ट-ऑर्डर: आदेश-पश्चात की त्रैमासिक तकनीक में, हम बाईं सबट्री, फिर दायें सबट्री और अंत में रूट नोड को पार करते हैं। पोस्टऑर्डर तकनीक के लिए ट्रैवर्सल का क्रम बचा है-> दाएं-> रूट।
यदि n रूट नोड है और ’l 'और' r 'क्रमशः पेड़ के बाएँ और दाएँ नोड हैं, तो ट्री ट्रैवर्सल एल्गोरिथम इस प्रकार हैं:
आदेश में (lnr) एल्गोरिथ्म:
- पीछे छोड़ दिया उपशीर्षक का उपयोग कर inOrder (बाएं- सबट्री)।
- रूट नोड (n) पर जाएँ।
- सही दाएं उपशीर्षक का उपयोग कर रहे हैं (सही-सही)।
रिकॉर्डर (nlr) एल्गोरिथ्म:
- रूट नोड (n) पर जाएँ।
- प्रीवार्ड (लेफ्ट-सबट्री) का उपयोग करते हुए ट्रैवर्स लेफ्ट सबट्री।
- प्रीऑर्डर (राइट-सबट्री) का उपयोग करके सही सबट्री को पार करें।
पोस्टऑर्डर (lrn) एल्गोरिथ्म:
- पोस्टऑडर (बाएं-सबट्री) का उपयोग करते हुए ट्रैवर्स को उप-उपशीर्षक छोड़ दिया।
- पोस्टऑडर (राइट-सबट्री) का उपयोग करके सही सबट्री को पार करें।
- रूट नोड (n) पर जाएँ।
ट्रैवर्सल तकनीकों के उपरोक्त एल्गोरिदम से, हम देखते हैं कि वांछित परिणाम प्राप्त करने के लिए तकनीकों को एक पुनरावर्ती फैशन में दिए गए पेड़ पर लागू किया जा सकता है।
निम्नलिखित पेड़ पर विचार करें।
उपरोक्त ट्रावेल तकनीक का उपयोग करते हुए, उपरोक्त ट्री के लिए ट्रैवर्सल अनुक्रम नीचे दिया गया है:
- इनऑर्डर ट्रैवर्सल: 2 3 5 6 10
- प्रीऑर्डर ट्रैवर्सल: 6 3 2 5 10
- पोस्टऑर्डर ट्रैसरल: 2 5 3 10 6
निष्कर्ष
पेड़ एक गैर-रैखिक पदानुक्रमित डेटा संरचना है जिसका उपयोग सॉफ्टवेयर क्षेत्र में कई अनुप्रयोगों में किया जाता है।
रैखिक डेटा संरचनाओं के विपरीत, जिनके पास सूची को पार करने का केवल एक ही तरीका है, हम विभिन्न तरीकों से पेड़ों को पार कर सकते हैं। हमने इस ट्यूटोरियल में ट्रैवर्सल तकनीकों और विभिन्न प्रकार के पेड़ों का विस्तृत अध्ययन किया था।
=> यहाँ सी ++ शुरुआती गाइड पर एक नज़र डालें
अनुशंसित पाठ
- बी ट्री और बी + ट्री डेटा संरचना C ++ में
- सी + + में बाइनरी ट्री डेटा संरचना
- सॉफ्टवेयर परियोजनाओं में जोखिम के प्रकार
- AVL ट्री और ढेर डेटा संरचना C ++ में
- पायथन डेटा प्रकार
- आपके सॉफ्टवेयर परीक्षण के बुनियादी ज्ञान की जाँच के लिए 20 सरल प्रश्न [ऑनलाइन क्विज़]
- C ++ डेटा प्रकार
- C ++ में बेसिक इनपुट / आउटपुट ऑपरेशंस