वृक्ष ट्रैवर्सल - केवल माता-पिता पॉइंटर्स के साथ पत्तियों से शुरू होता है?

Question

क्या यह एक पेड़ रखना अवधारणात्मक रूप से संभव है जहां आप इसे दिए गए पत्ती नोड (रूट नोड के बजाए) शुरू करके इसे रूट करते हैं और रूट पर जाने के लिए पैरेंट पॉइंटर्स का उपयोग करते हैं?

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

मुझे यह कार्यान्वयन दिलचस्प लगता है क्योंकि मैंने ऐसा कुछ नहीं देखा है, लेकिन अगर मैं इसे अभी भी "पेड़" माना जा सकता तो मैं उत्सुक था। मैंने कभी एक पेड़ नहीं देखा है जहां आप जड़ों की जगह पत्तियों पर ट्रैवर्सल शुरू करते हैं। मैंने कभी ऐसा पेड़ नहीं देखा है जहां पेड़ नोड्स में केवल माता-पिता पॉइंटर्स होते हैं और कोई बच्चे पॉइंटर्स नहीं होता है।

Answer 1

हाँ, यह संरचना मौजूद है। इसे अक्सर कहा जाता है।

स्पेगेटी स्टैक "संबंध का एक हिस्सा" का प्रतिनिधित्व करने के लिए उपयोगी हैं। उदाहरण के लिए, यदि आप क्लास पदानुक्रम को ऐसे तरीके से प्रस्तुत करना चाहते हैं जो अपस्टास्टिंग को सक्षम बनाता है, तो आप क्लास पदानुक्रम को स्पेगेटी स्टैक के रूप में प्रस्तुत कर सकते हैं जिसमें प्रत्येक प्रकार के नोड को अपने मूल प्रकार के पॉइंटर को स्टोर किया जाता है। इस तरह, यह पता लगाना आसान है कि कोई अपस्टास्ट नोड से ऊपर की ओर बढ़कर वैध है या नहीं।

वे अक्सर स्कॉइंग जानकारी ट्रैक करने के लिए कंपाइलरों में भी उपयोग किए जाते हैं। प्रत्येक नोड प्रोग्राम में एक गुंजाइश का प्रतिनिधित्व करता है, और प्रत्येक नोड में नोड के लिए एक पॉइंटर होता है जो उसके ऊपर एक स्तर का दायरा दर्शाता है।

आशा है कि इससे मदद मिलती है!

Answer 2

यदि पत्ती नोड्स के A दिए गए हैं, तो ट्रैवर्सल संभव है। अगर केवल एक ही पत्ता नोड दिया जाता है, तो मुझे नहीं पता कि पेड़ को कैसे पार किया जाए। स्यूडोकोड:

// initial step 
add all nodes in A to a queue Q 

//removeNode(Q) returns pointer to node at front of Q 
while((node = removeNode(Q)) != NULL) 
    /* do your operation on node */ 
    add node->parent to Q