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

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

मान लीजिए हमारे पास एक ऐसा पेड़ है -

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

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

इस निरूपण में हम इस सूत्र का उपयोग करके आसानी से एक नोड के दो बच्चों की स्थिति प्राप्त कर सकते हैं -

$$child_{1}=2*अभिभावक$$

$$child_{2}=\lgroup2*parent\rgroup+1$$

बच्चे से मूल अनुक्रमणिका प्राप्त करने के लिए हमें इस सूत्र का पालन करना होगा -

$$पैरेंट=\शुरू{bmatrix}\frac{child}{2} \end{bmatrix}$$

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

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