सी ++ एसटीएल कक्षा std :: नक्शा लागू करता है ओ (लॉग (एन)) एक बाइनरी पेड़ का उपयोग करके देखो। लेकिन पेड़ के साथ, यह तुरंत स्पष्ट नहीं है कि एक पुनरावर्तक कैसे काम करेगा। एक पेड़ संरचना में ++ ऑपरेटर वास्तव में क्या मतलब है? जबकि "अगले तत्व" की अवधारणा में एक सरणी में एक स्पष्ट कार्यान्वयन है, मेरे लिए यह एक पेड़ में इतना स्पष्ट नहीं है। एक पेड़ इटरेटर कैसे लागू करेगा?std :: map iterator कैसे काम करता है?
एक इनऑर्डर ट्रैवर्सल (शायद दूसरों के लिए भी काम करता है) के लिए, यदि आपके पास अपने नोड्स में पैरेंट पॉइंटर है तो आप एक गैर-पुनरावर्ती ट्रैवर्सल कर सकते हैं। अपने इटरेटर में केवल दो पॉइंटर्स स्टोर करना संभव होना चाहिए: आपको जहां आप हैं, वहां संकेत दें कि आप शायद (मैं अब शोध नहीं कर रहा हूं) को "पिछले" पॉइंटर की तरह कुछ चाहिए ताकि आप समझ सकें आपकी वर्तमान आंदोलन दिशा (यानी मुझे बाएं उपट्री में जाने की ज़रूरत है, या क्या मैं उससे वापस आ गया)।
"पिछला" शायद हो जाएगा की तरह कुछ "जनक", हम बस नोड डाल दी है; "बाएं" अगर हम बाएं उपट्री से वापस आ रहे हैं, तो "दाएं" अगर हम दाएं उपट्री से वापस आ रहे हैं, और "स्वयं" अगर आखिरी नोड हम लौट आए तो हमारा अपना ही था।
एक कार्यान्वयन यह जान सकता है कि नोड पॉइंटर्स शब्द-संरेखित हैं और दूसरे सूचक का उपयोग करने के बजाय, राज्य को संग्रहीत करने के लिए नोड पॉइंटर के निचले बिट्स का दुरुपयोग करते हैं। – MSalters
मुझे लगता है कि मुझे यही चाहिए। अनिवार्य रूप से मैं एक सामान्य वृक्ष वर्ग के लिए एक इटरेटर बनाने की कोशिश कर रहा हूं और यह एन-आरी अनियंत्रित पेड़ के लिए काम करता प्रतीत होता है। – Avi
मानचित्र में सभी तत्वों के सेट पर विचार करें जो वर्तमान तत्व से कम नहीं हैं जो वर्तमान तत्व भी नहीं हैं। "अगला तत्व" तत्वों के उस सेट से तत्व है जो उस सेट के सभी अन्य तत्वों से कम है।
मानचित्र का उपयोग करने के लिए, आपके पास एक कुंजी होनी चाहिए। और उस कुंजी को "कम से कम" ऑपरेशन को लागू करना होगा। यह नक्शा बनने के तरीके को निर्धारित करता है, जैसे कि खोज, जोड़, निकालना, वृद्धि, और कमी संचालन कुशल हैं।
आम तौर पर नक्शा आंतरिक रूप से किसी प्रकार का पेड़ उपयोग करता है।
आप स्रोत को स्टार्टर के रूप में देख सकते हैं: http://www.sgi.com/tech/stl/stl_map.h – amit
एक विशिष्ट [स्व-संतुलन बाइनरी खोज पेड़] देखें (http: // en.wikipedia.org/wiki/Red%E2%80%93black_tree)। किसी एल्गोरिदम को देखना आसान है जो किसी दिए गए नोड से अगले बच्चे को सही बच्चों को देखकर या पेड़ के नीचे और नीचे जाकर मिलता है। कभी-कभी आपको कई बार कूदना पड़ता है, लेकिन यह अभी भी निरंतर स्थिर समय है (क्योंकि पेड़ की ऊंचाई तत्वों की संख्या का लघुगणक है)। –
यह विकिपीडिया लेख आपके कुछ प्रश्नों का उत्तर दे सकता है: [वृक्ष ट्रैवर्सल] (http://en.wikipedia.org/wiki/Tree_traversal)। असल में, आपके द्वारा उपयोग किए जाने वाले ट्रैवर्सल के आधार पर "अगला" तत्व भिन्न हो सकता है। 'Std :: map' के मामले में, पेड़ क्रम में (सबसे छोटे तत्व से सबसे महान) में घुमाया जाता है। –