सी में बाइनरी ट्री
सी में, ए बाइनरी ट्री पेरेंट नोड के साथ ट्री डेटा संरचना का एक उदाहरण है जिसमें अधिकतम दो चाइल्ड नोड हो सकते हैं; 0, 1, या 2 संतान नोड। प्रत्येक नोड में a बाइनरी ट्री इसका अपना मूल्य है और इसके बच्चों के लिए दो पॉइंटर्स हैं, एक पॉइंटर बाएं बच्चे के लिए और दूसरा दाएं बच्चे के लिए।
बाइनरी ट्री की घोषणा
ए बाइनरी ट्री नामक वस्तु का उपयोग करके C में घोषित किया जा सकता है struct जो पेड़ में नोड्स में से एक को दर्शाता है।
struct नोड {
डेटा प्रकार var_name ;
struct नोड * बाएं ;
struct नोड * सही ;
} ;
ऊपर एक की घोषणा है बाइनरी ट्री नोड के रूप में नोड का नाम। इसमें तीन मान होते हैं; एक डेटा-स्टोरिंग वेरिएबल है और अन्य दो बच्चे के लिए पॉइंटर्स हैं। (मूल नोड के बाएँ और दाएँ बच्चे)।
बाइनरी ट्री के तथ्य
डेटा के बड़े सेट के लिए भी, a का उपयोग करना बाइनरी ट्री खोज को आसान और तेज़ बनाता है। पेड़ की शाखाओं की संख्या सीमित नहीं है। एक सरणी के विपरीत, किसी व्यक्ति की आवश्यकता के आधार पर किसी भी प्रकार के पेड़ बनाए और बढ़ाए जा सकते हैं।
सी में बाइनरी ट्री कार्यान्वयन
निम्नलिखित एक को लागू करने के लिए चरण-दर-चरण मार्गदर्शिका है बाइनरी ट्री सी में
चरण 1: एक बाइनरी सर्च ट्री घोषित करें
एक स्ट्रक्चर नोड बनाएं जिसमें तीन प्रकार के डेटा हों, जैसे कि डेटा, *लेफ्ट_चाइल्ड, और *राइट_चाइल्ड, जहां डेटा पूर्णांक प्रकार का हो सकता है, और दोनों *लेफ्ट_चाइल्ड और *राइट_चाइल्ड नोड्स को NULL या नहीं घोषित किया जा सकता है।
struct नोड{
int यहाँ आंकड़े ;
struct नोड * right_child ;
struct नोड * बायाँ_बच्चा ;
} ;
चरण 2: बाइनरी सर्च ट्री में नए नोड बनाएं
एक फ़ंक्शन बनाकर एक नया नोड बनाएं जो एक पूर्णांक को तर्क के रूप में स्वीकार करता है और उस मान के साथ बनाए गए नए नोड को सूचक प्रदान करता है। निर्मित नोड के लिए डायनेमिक मेमोरी आवंटन के लिए C में मॉलोक () फ़ंक्शन का उपयोग करें। बाएँ और दाएँ बच्चे को NULL में प्रारंभ करें और नोडनाम वापस करें।
struct नोड * बनाएं ( डेटाटाइप डेटा )
{
struct नोड * नोडनाम = malloc ( का आकार ( struct नोड ) ) ;
नोडनाम -> आंकड़े = कीमत ;
नोडनाम -> बायाँ_बच्चा = नोडनाम -> right_child = व्यर्थ ;
वापस करना नोडनाम ;
}
चरण 3: बाइनरी ट्री में राइट और लेफ्ट चाइल्ड डालें
इन्सर्ट_लेफ्ट और इन्सर्ट_राइट फ़ंक्शन बनाएं जो दो इनपुट स्वीकार करेगा, जो डालने के लिए मान हैं और नोड के लिए पॉइंटर जिससे दोनों बच्चे जुड़े होंगे। एक नया नोड बनाने के लिए क्रिएट फंक्शन को कॉल करें और लौटे हुए पॉइंटर को लेफ्ट चाइल्ड के लेफ्ट पॉइंटर या रूट पेरेंट के राइट चाइल्ड के राइट पॉइंटर को असाइन करें।
struct नोड * डालें_बाएँ ( struct नोड * जड़ , डेटाटाइप डेटा ) {जड़ -> बाएं = बनाएं ( आंकड़े ) ;
वापस करना जड़ -> बाएं ;
}
struct नोड * डालें_दाएं ( struct नोड * जड़ , डेटाटाइप डेटा ) {
जड़ -> सही = बनाएं ( आंकड़े ) ;
वापस करना जड़ -> सही ;
}
चरण 4: ट्रैवर्सल विधियों का उपयोग करके बाइनरी ट्री के नोड्स प्रदर्शित करें
हम सी में ट्रैवर्सल के तीन तरीकों का उपयोग करके पेड़ प्रदर्शित कर सकते हैं। ये ट्रैवर्सल विधियां हैं:
1: प्री-ऑर्डर ट्रैवर्सल
इस ट्रैवर्सल विधि में, हम नोड्स से एक दिशा में जाएंगे पेरेंट_नोड-> लेफ्ट_चाइल्ड-> राइट_चाइल्ड .
खालीपन पूर्व आदेश ( नोड * जड़ ) {अगर ( जड़ ) {
printf ( '%डी \एन ' , जड़ -> आंकड़े ) ;
display_pre_order ( जड़ -> बाएं ) ;
display_pre_order ( जड़ -> सही ) ;
}
}
2: पोस्ट-ऑर्डर ट्रैवर्सल
इस ट्रैवर्सल विधि में, हम नोड्स से एक दिशा में जाएंगे लेफ्ट_चाइल्ड->राइट_चाइल्ड->पैरेंट_नोड-> .
खालीपन डिस्प्ले_पोस्ट_ऑर्डर ( नोड * जड़ ) {अगर ( बाइनरी_ट्री ) {
डिस्प्ले_पोस्ट_ऑर्डर ( जड़ -> बाएं ) ;
डिस्प्ले_पोस्ट_ऑर्डर ( जड़ -> सही ) ;
printf ( '%डी \एन ' , जड़ -> आंकड़े ) ;
}
}
3: इन-ऑर्डर ट्रैवर्सल
इस ट्रैवर्सल विधि में, हम नोड्स से एक दिशा में जाएंगे लेफ्ट_नोड->रूट_चाइल्ड->राइट_चाइल्ड .
खालीपन डिस्प्ले_इन_ऑर्डर ( नोड * जड़ ) {अगर ( बाइनरी_ट्री ) {
डिस्प्ले_इन_ऑर्डर ( जड़ -> बाएं ) ;
printf ( '%डी \एन ' , जड़ -> आंकड़े ) ;
डिस्प्ले_इन_ऑर्डर ( जड़ -> सही ) ;
}
}
चरण 5: बाइनरी ट्री में विलोपन करें
हम बनाए गए को हटा सकते हैं बाइनरी ट्री निम्नानुसार सी में पैरेंट नोड फ़ंक्शन वाले दोनों बच्चों को हटाकर।
खालीपन हटाएं_टी ( नोड * जड़ ) {अगर ( जड़ ) {
हटाएं_टी ( जड़ -> बाएं ) ;
हटाएं_टी ( जड़ -> सही ) ;
मुक्त ( जड़ ) ;
}
}
सी प्रोग्राम ऑफ़ बाइनरी सर्च ट्री
निम्नलिखित सी प्रोग्रामिंग में बाइनरी सर्च ट्री का पूर्ण कार्यान्वयन है:
#शामिल#शामिल
struct नोड {
int यहाँ कीमत ;
struct नोड * बाएं , * सही ;
} ;
struct नोड * नोड1 ( int यहाँ आंकड़े ) {
struct नोड * टीएमपी = ( struct नोड * ) malloc ( का आकार ( struct नोड ) ) ;
टीएमपी -> कीमत = आंकड़े ;
टीएमपी -> बाएं = टीएमपी -> सही = व्यर्थ ;
वापस करना टीएमपी ;
}
खालीपन छपाई ( struct नोड * root_node ) // नोड्स प्रदर्शित करना!
{
अगर ( root_node != व्यर्थ ) {
छपाई ( root_node -> बाएं ) ;
printf ( '%डी \एन ' , root_node -> कीमत ) ;
छपाई ( root_node -> सही ) ;
}
}
struct नोड * इन्सर्ट_नोड ( struct नोड * नोड , int यहाँ आंकड़े ) // नोड्स डालना!
{
अगर ( नोड == व्यर्थ ) वापस करना नोड1 ( आंकड़े ) ;
अगर ( आंकड़े < नोड -> कीमत ) {
नोड -> बाएं = इन्सर्ट_नोड ( नोड -> बाएं , आंकड़े ) ;
} अन्य अगर ( आंकड़े > नोड -> कीमत ) {
नोड -> सही = इन्सर्ट_नोड ( नोड -> सही , आंकड़े ) ;
}
वापस करना नोड ;
}
int यहाँ मुख्य ( ) {
printf ( 'बाइनरी सर्च ट्री का सी कार्यान्वयन! \एन \एन ' ) ;
struct नोड * माता-पिता = व्यर्थ ;
माता-पिता = इन्सर्ट_नोड ( माता-पिता , 10 ) ;
इन्सर्ट_नोड ( माता-पिता , 4 ) ;
इन्सर्ट_नोड ( माता-पिता , 66 ) ;
इन्सर्ट_नोड ( माता-पिता , चार पांच ) ;
इन्सर्ट_नोड ( माता-पिता , 9 ) ;
इन्सर्ट_नोड ( माता-पिता , 7 ) ;
छपाई ( माता-पिता ) ;
वापस करना 0 ;
}
उपरोक्त कोड में, हम पहले घोषणा करते हैं नोड का उपयोग करते हुए struct . फिर हम एक नए नोड को 'के रूप में आरंभ करते हैं' नोड1 ” और गतिशील रूप से उपयोग करके मेमोरी आवंटित करें मॉलोक () सी में डेटा और दो पॉइंटर्स के साथ घोषित नोड का उपयोग करके बच्चे टाइप करें। इसके बाद, हम द्वारा नोड प्रदर्शित करते हैं प्रिंटफ () कार्य करें और इसे में कॉल करें मुख्य() समारोह। फिर सम्मिलन_नोड () फ़ंक्शन बनाया गया है, जहां नोड डेटा न्यूल है तो नोड1 सेवानिवृत्त है, अन्यथा डेटा में रखा गया है नोड (माता-पिता) बाएँ और दाएँ बच्चे के। कार्यक्रम से निष्पादन शुरू होता है मुख्य() फ़ंक्शन, जो बच्चों के रूप में कुछ नमूना नोड्स का उपयोग करके नोड उत्पन्न करता है और फिर नोड सामग्री को प्रिंट करने के लिए इन-ऑर्डर ट्रैवर्सल विधियों का उपयोग करता है।
उत्पादन
निष्कर्ष
डेटा को गैर-रैखिक रूप में रखने के लिए पेड़ों को अक्सर नियोजित किया जाता है। बाइनरी पेड़ एक प्रकार के पेड़ हैं जहां प्रत्येक नोड (माता-पिता) की दो संतानें होती हैं बायां बच्चा और दायां बच्चा। ए बाइनरी ट्री डेटा स्थानांतरित करने और संग्रहीत करने का एक बहुमुखी तरीका है। C में Linked-List की तुलना में यह अधिक कुशल है। उपरोक्त लेख में, हमने a की अवधारणा को देखा है बाइनरी ट्री ए के चरण-दर-चरण कार्यान्वयन के साथ बाइनरी सर्च ट्री सी में