सी ++ 11

Question

का उपयोग कर बाइनरी (या मनमाने ढंग से) पेड़ पर एक पुनरावर्तक को कार्यान्वित करना, मैं बाइनरी पेड़ पर एक इटरेटर बनाना चाहता हूं ताकि लूप के लिए श्रेणी-आधारित उपयोग करने में सक्षम हो सकें। मैं समझता हूं कि मुझे पहले() और एंड() फ़ंक्शन को लागू करना चाहिए।

शुरुआत शायद रूट को इंगित करना चाहिए। विनिर्देश के अनुसार, हालांकि, अंत() फ़ंक्शन "अंतिम वैध तत्व के बाद तत्व" लौटाता है। कौन सा तत्व (नोड) वह है? क्या कुछ "अमान्य" जगह को इंगित करना अवैध नहीं होगा?

दूसरी बात ऑपरेटर ++ है। पेड़ में "अगला" तत्व वापस करने का सबसे अच्छा तरीका क्या है? मुझे इस प्रोग्रामिंग के साथ शुरू करने के लिए बस कुछ सलाह चाहिए।

---

मैं अपने प्रश्न का विस्तार/विस्तार करना चाहता हूं *। क्या होगा यदि मैं एक पेड़ पर एक मनमानी धैर्य के साथ पुनरावृत्ति करना चाहता था? प्रत्येक नोड में बच्चों का वेक्टर होता है और शुरूआत() को "वास्तविक" रूट पर इंगित करने दें। मुझे अनन्य_प्टर के नोड्स को स्टोर करने के लिए इटरेटर क्लास के अंदर शायद कतार (पहले चौड़ाई के लिए) को लागू करना होगा, है ना? फिर, जब कतार खाली होती है तो मुझे पता चलेगा कि मैंने सभी नोड्स पारित किए हैं और इस प्रकार ओपेटर ++() कहा जाता है जब इस प्रकार TreeIterator (nullptr) लौटा देना चाहिए। क्या इस का कोई मतलब निकलता है? मैं इसे यथासंभव सरल और केवल पुनरावृत्ति के लिए चाहता हूं।

* या मुझे एक नया धागा बनाना चाहिए?

Answer 1

जहां आपके begin() को बहुत अधिक इंगित करना चाहिए उस क्रम पर निर्भर करता है जिसमें आप अपने पेड़ को पार करना चाहते हैं। रूट का उपयोग समझदार हो सकता है, उदाहरण के लिए, पेड़ की चौड़ाई पहली बार चलने के लिए। end() वास्तव में एक पेड़ नोड पर नहीं बैठता है: यह स्थिति एक्सेस की जाती है और इंगित करती है कि अनुक्रम का अंत तक पहुंच गया है। चाहे यह पेड़ से संबंधित कुछ भी इंगित करता हो, कुछ हद तक निर्भर करता है कि आप किस तरह के पुनरावृत्ति का समर्थन करना चाहते हैं: केवल आगे पुनरावृत्ति का समर्थन करते समय यह केवल अंत को इंगित कर सकता है। जब द्विपक्षीय पुनरावृत्ति का समर्थन भी करते हैं, तो यह जानने की जरूरत है कि अंत से पहले नोड को कैसे ढूंढें।

किसी भी मामले में, जिस स्थान पर इंगित किया गया है वह वास्तव में उपयोग नहीं किया गया है और आपको उपयुक्त संकेतक की आवश्यकता है। फॉरवर्ड पुनरावृत्ति के लिए केवल इटेटरेटर end() सिर्फ एक नाइटरेटर को शून्य पर इंगित कर सकता है और जब आप अंतिम नोड से आगे बढ़ते हैं तो आप केवल इटेटरेटर के पॉइंटर को शून्य पर सेट कर सकते हैं: दो पॉइंटर्स की तुलना करने वाली समानता true उत्पन्न करेगी, यह दर्शाती है कि आप पहुंच गए हैं समाप्त। जब बिडरेक्शनल पुनरावृत्ति का समर्थन करना चाहते हैं तो आपको किसी प्रकार के लिंक रिकॉर्ड की आवश्यकता होगी जिसका उपयोग पिछले नोड पर नेविगेट करने के लिए किया जा सकता है, लेकिन किसी मूल्य को स्टोर करने की आवश्यकता नहीं है।

आदेशित संबंधित कंटेनर (std::map<K, V>, std:set<V>, आदि) आंतरिक रूप से किसी प्रकार के पेड़ (उदाहरण के लिए, एक लाल/काला-पेड़) के रूप में कार्यान्वित होते हैं। begin() इटरेटर बाएं सबसे अधिक नोड के साथ शुरू होता है और end() इटरेटर सही-नोड के बाद स्थिति को संदर्भित करता है।operator++() बस के अधिकार के लिए अगले नोड पाता वर्तमान:

• अगर इटरेटर एक सही चाइल्ड नोड के बिना एक नोड पर बैठता है, यह के माध्यम से माता-पिता की श्रृंखला के साथ चलता है जब तक कि वह अपने बच्चे तक पहुंच गया एक माता पिता पाता है पेड़ की बाएं शाखा
• यदि यह सही बच्चे नोड के साथ नोड पर बैठता है तो यह बच्चे के पास जाता है और फिर दाएं बच्चे के बाएं बच्चों के अनुक्रम के नीचे (यदि कोई हो) सही उपट्री में बाएं सबसे अधिक बच्चे को ढूंढने के लिए ।

जाहिर है, यदि आप अपने पेड़ को बाएं से दाएं नहीं चलते हैं, बल्कि, उदाहरण के लिए, ऊपर से नीचे तक, आपको एक अलग एल्गोरिदम की आवश्यकता होगी। मेरे लिए सबसे आसान तरीका कागज के टुकड़े पर एक पेड़ खींचना है और देखें कि अगले नोड को कैसे प्राप्त करें।

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

Answer 2

एक पेड़ के लिए एक इटरेटर हालांकि यह संभावना एक सूचक में शामिल होंगे, बस एक सूचक की तुलना में अधिक होने जा रहा है:,

struct TreeIterator { 
    TreeIterator(TreeNode *node_ptr) : node_ptr(node_ptr) { } 
    TreeIterator &operator++(); 
    TreeIterator operator++(int); 
    bool operator==(const TreeIterator &) const; 

    private: 
    TreeNode *node_ptr; 
}; 

TreeIterator begin(const Tree &tree) { ... } 
TreeIterator end(const Tree &tree) { ... } 

आप अपने अंत() फ़ंक्शन वापसी कुछ खास बना सकते हैं TreeIterator(nullptr)

की तरह

आपका प्रारंभिक इटरेटर पॉइंट क्या है जो आप चाहते हैं कि ट्रैवर्सल के प्रकार पर निर्भर करेगा। यदि आप चौड़ाई कर रहे हैं- पहले ट्रैवर्सल, तो जड़ से शुरू करना समझ में आता है।

Answer 3

आरबीटी के एसजीआई कार्यान्वयन को देखें (यह std::set/std::map ... कंटेनर के लिए आधार है)।

http://www.sgi.com/tech/stl/stl_tree.h

आपको लगता है कि शुरू देखेंगे() वाम-पंथी नोड है।

आपको लगता है कि अंत देखेंगे() एक विशेष "खाली" नोड हैडर जो सुपर जड़ है है - मैं एक असली जड़ मतलब (पूर्व निर्धारित ही अगर पेड़ खाली नहीं है) ने अपने चाइल्ड नोड है।

operator ++ सही बच्चे को जाना है और फिर इस बच्चे को बाएं नोड को ढूंढना है। यदि ऐसा बच्चा मौजूद नहीं है - हम दाएं पैरेंट नोड के बाएं पैरेंट पर जाते हैं। इस उदाहरण में के रूप में (लाल लाइनों को छोड़ चाल, नीले समाप्त हो जाता हैं यात्रा के दिए गए चरणों):

कोड एसजीआई से नकल:

void _M_increment() 
    { 
    if (_M_node->_M_right != 0) { 
     _M_node = _M_node->_M_right; 
     while (_M_node->_M_left != 0) 
     _M_node = _M_node->_M_left; 
    } 
    else { 
     _Base_ptr __y = _M_node->_M_parent; 
     while (_M_node == __y->_M_right) { 
     _M_node = __y; 
     __y = __y->_M_parent; 
     } 
     if (_M_node->_M_right != __y) 
     _M_node = __y; 
    } 
    } 

जब एक पेड़ रिक्त है - begin() शीर्षलेख का सबसे बाएं है - इसलिए यह हेडर है - end() हेडर भी है - इसलिए begin() == end()। याद रखें - आपकी पुनरावृत्ति योजना खाली पेड़ों के लिए इस स्थिति begin() == end() से मेल खाना चाहिए।

यह बहुत ही स्मार्ट पुनरावृत्ति योजना प्रतीत होता है।

बेशक आप आप स्वयं योजना परिभाषित कर सकते हैं - लेकिन सबक सीखा end() प्रयोजन के लिए विशेष नोड है।