मूल अवधारणा
एक बाइनरी ट्री को एक ऐसे पेड़ के रूप में परिभाषित किया जाता है जिसमें किसी भी नोड में दो से अधिक बच्चे नहीं हो सकते। किसी भी नोड की उच्चतम डिग्री दो होती है। यह इंगित करता है कि बाइनरी ट्री की डिग्री या तो शून्य या एक या दो होती है।
उपरोक्त अंजीर में, बाइनरी ट्री में एक जड़ और दो उप ट्री ट्रीलेफ्ट और ट्रीराइट होते हैं। बाइनरी ट्री के बाईं ओर के सभी नोड्स को लेफ्ट सबट्री के रूप में दर्शाया जाता है और बाइनरी ट्री के दाईं ओर के सभी नोड्स को राइट सबट्री के रूप में संदर्भित किया जाता है।
कार्यान्वयन
एक बाइनरी ट्री में अधिकतम दो बच्चे होते हैं; हम उन्हें डायरेक्ट पॉइंटर्स असाइन कर सकते हैं। ट्री नोड्स की घोषणा डबल लिंक्ड सूचियों की संरचना के समान है, जिसमें एक नोड एक संरचना है जिसमें प्रमुख जानकारी और अन्य नोड्स के लिए दो पॉइंटर्स (बाएं और दाएं) शामिल हैं।
बाइनरी ट्री नोड घोषणा
typedef struct tree_node *tree_ptr;
struct tree_node
{
element_type element1;
tree_ptr left1; tree_ptr right1;
};
typedef tree_ptr TREE; बाइनरी ट्री के प्रकार
सख्त बाइनरी ट्री
कड़ाई से बाइनरी ट्री को एक बाइनरी ट्री के रूप में परिभाषित किया गया है जहां सभी नोड्स में या तो शून्य या दो बच्चे होंगे। इसमें किसी भी नोड में एक बच्चा शामिल नहीं है।
तिरछा पेड़
एक तिरछा पेड़ को एक बाइनरी ट्री के रूप में परिभाषित किया जाता है जिसमें पत्ती को छोड़कर प्रत्येक नोड में केवल एक चाइल्ड नोड होता है। तिरछा वृक्ष दो प्रकार का होता है, अर्थात बायां तिरछा बाइनरी ट्री और दायां तिरछा बाइनरी ट्री।
बाएं तिरछा बाइनरी ट्री
एक बाएं तिरछा पेड़ में नोड केवल बाएं बच्चे से जुड़ा होता है। यह एक बाइनरी ट्री है जिसमें केवल लेफ्ट सबट्री होते हैं।
दायां तिरछा बाइनरी ट्री
एक दायां तिरछा पेड़ में नोड केवल सही बच्चे से जुड़ा होता है। यह एक बाइनरी ट्री है जिसमें केवल राइट सबट्री होते हैं।
पूर्ण बाइनरी ट्री या उचित बाइनरी ट्री
एक बाइनरी ट्री को पूर्ण बाइनरी ट्री के रूप में परिभाषित किया जाता है यदि सभी पत्ते समान स्तर पर हों और प्रत्येक नॉन लीफ नोड में ठीक दो बच्चे हों और इसमें सभी स्तरों में उच्चतम संभव संख्या में नोड्स हों। ऊंचाई के एक पूर्ण बाइनरी ट्री में अधिकतम 2h+1 - 1 नोड होते हैं।
पूर्ण बाइनरी ट्री
प्रत्येक नॉन लीफ नोड में ठीक दो बच्चे होते हैं लेकिन सभी पत्तियों का एक ही स्तर पर होना आवश्यक नहीं है। एक पूर्ण बाइनरी ट्री को एक के रूप में परिभाषित किया जाता है, जहां अंतिम स्तर को छोड़कर सभी स्तरों में नोड्स की संख्या सबसे अधिक होती है। अंतिम स्तर के तत्वों को बाएँ से दाएँ दिशा में भरा जाना चाहिए।
लगभग पूर्ण बाइनरी ट्री
लगभग पूर्ण बाइनरी ट्री को एक ऐसे पेड़ के रूप में परिभाषित किया जाता है जिसमें प्रत्येक नोड जिसमें एक दायां बच्चा होता है, उसका एक बायां बच्चा भी होता है। बायां बच्चा होने के लिए दायां बच्चा पैदा करने के लिए नोड की ज़रूरत नहीं है
सामान्य वृक्ष और बाइनरी ट्री के बीच अंतर
सामान्य वृक्ष
- सामान्य वृक्ष में बच्चों की संख्या की कोई सीमा नहीं होती।
- सामान्य वृक्षों में किसी भी व्यंजक का मूल्यांकन करना कठिन होता है।
बाइनरी ट्री
- एक बाइनरी ट्री में अधिकतम दो बच्चे होते हैं
- बाइनरी ट्री में व्यंजक का मूल्यांकन सरल है।
पेड़ों का अनुप्रयोग
- अंकगणितीय व्यंजक का हेरफेर
- प्रतीक तालिका का निर्माण
- सिंटैक्स का विश्लेषण
- व्याकरण लिखना
- अभिव्यक्ति वृक्ष का निर्माण