डेटा स्ट्रक्चर में बाइनरी ट्री प्रतिनिधित्व

यहां हम देखेंगे कि कंप्यूटर की मेमोरी में बाइनरी ट्री को कैसे दर्शाया जाए। प्रतिनिधित्व के लिए दो अलग-अलग तरीके हैं। ये सरणी और लिंक्ड लिस्ट का उपयोग करके हैं।

मान लीजिए हमारे पास ऐसा एक ट्री है:

सरणी प्रतिनिधित्व लेवल ऑर्डर फैशन का उपयोग करके एलिमेंट्स को स्कैन करके ट्री डेटा को स्टोर करता है। तो यह नोड्स को लेवल दर लेवल स्टोर करता है। यदि कुछ एलिमेंट गायब है, तो यह उसके लिए खाली स्थान छोड़ देता है। उपरोक्त ट्री का प्रतिनिधित्व नीचे दिए अनुसार है:

इंडेक्स 1 रूट को रखता है, इसके दो चिल्ड्रन 5 और 16 हैं, उन्हें स्थान 2 और 3 पर रखा गया है। कुछ चिल्ड्रन गायब हैं, इसलिए उनकी जगह खाली छोड़ दी गई है।

इस प्रतिनिधित्व में हम एक नोड के दो चिल्ड्रन की स्थिति को इस सूत्र का उपयोग करके आसानी से प्राप्त कर सकते हैं:

$$child_{1}=2*parent$$

$$child_{2}=(2*parent)+1$$

चाइल्ड से पैरेंट इंडेक्स प्राप्त करने के लिए हमें इस सूत्र का पालन करना होगा:

$$parent=\begin{bmatrix}\frac{child}{2} \end{bmatrix}$$

यह दृष्टिकोण अच्छा है, और हम आसानी से पैरेंट और चाइल्ड का इंडेक्स ढूंढ सकते हैं, लेकिन यह मेमोरी कुशल नहीं है। यह कई स्थानों पर कब्जा करेगा जिसका कोई उपयोग नहीं है। यह प्रतिनिधित्व पूर्ण बाइनरी ट्री या फुल बाइनरी ट्री के लिए अच्छा है।

दूसरा दृष्टिकोण लिंक्ड लिस्ट का उपयोग करके है। हम प्रत्येक एलिमेंट के लिए नोड बनाते हैं। यह नीचे दिए अनुसार दिखेगा: