पूर्ण बाइनरी ट्री बनाम पूर्ण बाइनरी ट्री
बाइनरी ट्री एक ऐसा पेड़ है जहां प्रत्येक नोड में एक या दो बच्चे होते हैं। एक बाइनरी ट्री में, एक नोड में दो से अधिक बच्चे नहीं हो सकते। बाइनरी ट्री में बच्चों को "बाएं" और "दाएं" बच्चों के नाम से जाना जाता है। चाइल्ड नोड्स में उनके माता-पिता का संदर्भ होता है। एक पूर्ण बाइनरी ट्री एक बाइनरी ट्री है जिसमें अंतिम स्तर को छोड़कर बाइनरी ट्री का हर स्तर पूरी तरह से भरा होता है। अधूरे स्तर में, नोड्स सबसे बाईं ओर की स्थिति से शुरू होते हैं। एक पूर्ण बाइनरी ट्री एक ऐसा पेड़ है जिसमें पेड़ के पत्तों को छोड़कर पेड़ के प्रत्येक नोड में दो बच्चे होते हैं।
पूर्ण बाइनरी ट्री क्या है?
पूर्ण बाइनरी ट्री एक बाइनरी ट्री है जिसमें पेड़ के प्रत्येक नोड में बिल्कुल शून्य या दो बच्चे होते हैं। दूसरे शब्दों में, पत्तियों को छोड़कर पेड़ के प्रत्येक नोड में ठीक दो बच्चे होते हैं। नीचे दिया गया चित्र 1 एक पूर्ण बाइनरी ट्री को दर्शाता है। एक पूर्ण बाइनरी ट्री में, नोड्स की संख्या (n), लैव्स की संख्या (l) और आंतरिक नोड्स की संख्या (i) एक विशेष तरीके से संबंधित होती है जैसे कि यदि आप उनमें से किसी एक को जानते हैं तो आप अन्य दो को निर्धारित कर सकते हैं। मान इस प्रकार हैं:
1. यदि एक पूर्ण बाइनरी ट्री में i आंतरिक नोड हैं:
– पत्तों की संख्या l=i+1
– नोड्स की कुल संख्या n=2i+1
2. यदि एक पूर्ण बाइनरी ट्री में n नोड्स हैं:
– आंतरिक नोड्स की संख्या i=(n-1)/2
– पत्तों की संख्या l=(n+1)/2
3. यदि एक पूर्ण बाइनरी ट्री में l पत्ते हैं:
– नोड्स की कुल संख्या n=2l-1
– आंतरिक नोड्स की संख्या i=l-1
पूर्ण बाइनरी ट्री क्या है?
जैसा कि चित्र 2 में दिखाया गया है, एक पूर्ण बाइनरी ट्री एक बाइनरी ट्री है जिसमें अंतिम स्तर को छोड़कर पेड़ का हर स्तर पूरी तरह से भरा होता है। साथ ही, अंतिम स्तर में, नोड्स को सबसे बाईं ओर से शुरू करके संलग्न किया जाना चाहिए। ऊँचाई h का एक पूर्ण बाइनरी ट्री निम्नलिखित शर्तों को पूरा करता है:
– रूट नोड से, अंतिम स्तर से ऊपर का स्तर h-1 ऊंचाई के पूर्ण बाइनरी ट्री का प्रतिनिधित्व करता है
- अंतिम स्तर में एक या अधिक नोड्स में 0 या 1 बच्चे हो सकते हैं
– यदि a, b अंतिम स्तर से ऊपर के स्तर में दो नोड हैं, तो a में b से अधिक बच्चे हैं यदि और केवल यदि a, b के बाईं ओर स्थित हो
पूर्ण बाइनरी ट्री और पूर्ण बाइनरी ट्री में क्या अंतर है?
पूर्ण बाइनरी ट्री और पूर्ण बाइनरी ट्री में स्पष्ट अंतर है। जबकि एक पूर्ण बाइनरी ट्री एक बाइनरी ट्री है जिसमें प्रत्येक नोड में शून्य या दो बच्चे होते हैं, एक पूर्ण बाइनरी ट्री एक बाइनरी ट्री होता है जिसमें अंतिम स्तर को छोड़कर बाइनरी ट्री का हर स्तर पूरी तरह से भरा होता है। कुछ विशेष डेटा संरचनाएं जैसे ढेर को पूर्ण बाइनरी ट्री होने की आवश्यकता होती है, जबकि उन्हें पूर्ण बाइनरी ट्री होने की आवश्यकता नहीं होती है। एक पूर्ण बाइनरी ट्री में, यदि आप कुल नोड्स की संख्या या लेव्स की संख्या या आंतरिक नोड्स की संख्या जानते हैं, तो आप अन्य दो को बहुत आसानी से पा सकते हैं। लेकिन एक पूर्ण बाइनरी ट्री में इन तीन विशेषताओं से संबंधित कोई विशेष गुण नहीं होता है।
