मूल अवधारणा (Basic Concept)
बाइनरी ट्री को एक ऐसे ट्री के रूप में परिभाषित किया जाता है जिसमें कोई भी नोड दो से अधिक बच्चे (Children) नहीं रख सकता। किसी भी नोड की उच्चतम डिग्री (Degree) दो होती है। इसका अर्थ है कि बाइनरी ट्री की डिग्री शून्य, एक या दो हो सकती है।
उपरोक्त आकृति में, बाइनरी ट्री में एक रूट (Root) और दो सबट्री TreeLeft और TreeRight होते हैं। बाइनरी ट्री के बाईं ओर के सभी नोड्स को लेफ्ट सबट्री (Left Subtrees) कहा जाता है और दाईं ओर के सभी नोड्स को राइट सबट्री (Right Subtrees) कहा जाता है।
कार्यान्वयन (Implementation)
बाइनरी ट्री में अधिकतम दो बच्चे होते हैं; हम उन्हें डायरेक्ट पॉइंटर्स असाइन कर सकते हैं। ट्री नोड्स की घोषणा डबल लिंक्ड लिस्ट (Doubly Linked Lists) के समान संरचना में होती है, जिसमें एक नोड एक संरचना होती है जिसमें कुंजी जानकारी (Key Information) और दो पॉइंटर्स (Left और Right) अन्य नोड्स के लिए होते हैं।
बाइनरी ट्री नोड घोषणा (Binary Tree Node Declaration)
typedef struct tree_node *tree_ptr;
struct tree_node {
element_type element1;
tree_ptr left1;
tree_ptr right1;
};
typedef tree_ptr TREE;
बाइनरी ट्री के प्रकार (Types of Binary Tree)
स्ट्रिक्टली बाइनरी ट्री (Strictly Binary Tree)
स्ट्रिक्टली बाइनरी ट्री को एक ऐसे बाइनरी ट्री के रूप में परिभाषित किया जाता है जहां सभी नोड्स के या तो शून्य या दो बच्चे होते हैं। इसमें किसी भी नोड में एक बच्चा शामिल नहीं होता।
स्क्यू ट्री (Skew Tree)
स्क्यू ट्री को एक ऐसे बाइनरी ट्री के रूप में परिभाषित किया जाता है जिसमें लीफ (Leaf) को छोड़कर हर नोड का केवल एक चाइल्ड नोड होता है। स्क्यू ट्री दो प्रकार के होते हैं: लेफ्ट स्क्यूड बाइनरी ट्री (Left Skewed Binary Tree) और राइट स्क्यूड बाइनरी ट्री (Right Skewed Binary Tree)।
लेफ्ट स्क्यूड बाइनरी ट्री (Left Skewed Binary Tree)
एक लेफ्ट स्क्यू ट्री में नोड केवल लेफ्ट चाइल्ड से जुड़ा होता है। यह एक बाइनरी ट्री है जिसमें केवल लेफ्ट सबट्री होती हैं।
राइट स्क्यूड बाइनरी ट्री (Right Skewed Binary Tree)
एक राइट स्क्यू ट्री में नोड केवल राइट चाइल्ड से जुड़ा होता है। यह एक बाइनरी ट्री है जिसमें केवल राइट सबट्री होती हैं।
फुल बाइनरी ट्री या प्रॉपर बाइनरी ट्री (Full Binary Tree or Proper Binary Tree)
एक बाइनरी ट्री को फुल बाइनरी ट्री के रूप में परिभाषित किया जाता है यदि सभी लीफ एक ही स्तर (Level) पर हों और हर नॉन-लीफ नोड के ठीक दो बच्चे हों और इसमें सभी स्तरों पर अधिकतम संभव नोड्स हों। ऊंचाई h के फुल बाइनरी ट्री में अधिकतम 2^(h+1) - 1 नोड्स होते हैं।
कम्पलीट बाइनरी ट्री (Complete Binary Tree)
हर नॉन-लीफ नोड के ठीक दो बच्चे होते हैं लेकिन सभी लीफ का एक ही स्तर पर होना आवश्यक नहीं है। कम्पलीट बाइनरी ट्री को इस तरह परिभाषित किया जाता है जहां अंतिम स्तर को छोड़कर सभी स्तरों में अधिकतम संख्या में नोड्स हों। अंतिम स्तर के एलिमेंट्स को बाएं से दाएं दिशा में भरा जाना चाहिए।
ऑलमोस्ट कम्पलीट बाइनरी ट्री (Almost Complete Binary Tree)
एक ऑलमोस्ट कम्पलीट बाइनरी ट्री को एक ऐसे ट्री के रूप में परिभाषित किया जाता है जिसमें प्रत्येक नोड जिसका राइट चाइल्ड होता है, उसका लेफ्ट चाइल्ड भी होता है। लेफ्ट चाइल्ड होने का मतलब यह नहीं कि नोड का राइट चाइल्ड होना आवश्यक है।
जनरल ट्री और बाइनरी ट्री के बीच अंतर (Differences between General Tree and Binary Tree)
जनरल ट्री (General Tree)
- जनरल ट्री में बच्चों की संख्या की कोई सीमा नहीं होती।
- जनरल ट्री में किसी एक्सप्रेशन का मूल्यांकन करना कठिन होता है।
बाइनरी ट्री (Binary Tree)
- बाइनरी ट्री में अधिकतम दो बच्चे होते हैं।
- बाइनरी ट्री में एक्सप्रेशन का मूल्यांकन सरल होता है।
ट्री के अनुप्रयोग (Application of Trees)
- अंकगणितीय एक्सप्रेशन का हेरफेर (Manipulation of Arithmetic Expression)
- सिंबल टेबल का निर्माण (Construction of Symbol Table)
- सिंटैक्स का विश्लेषण (Analysis of Syntax)
- ग्रामर लिखना (Writing Grammar)
- एक्सप्रेशन ट्री का निर्माण (Creation of Expression Tree)
