Iterative पेड़ चलने

Question

यह काफी समय हो गया है के बाद से मैं एक सुझाव द्वारा डाटा संरचनाओं और एल्गोरिदम कॉलेज में ले लिया है, तो मैं हैरान था हाल ही में है कि प्रत्यावर्तन रास्ता (टीएम) पेड़ ट्रेवर्सल करने के लिए नहीं हो सकता। कुछ कारणों से पुनरावृत्त, कतार आधारित ट्रैवर्सल ऐसी तकनीक नहीं रही है जिसका मैंने कभी उपयोग किया है।

क्या, यदि कोई है, तो पुनरावृत्त बनाम पुनरावर्ती ट्रैवर्सल के फायदे हैं? मैं किस परिस्थिति में दूसरे की बजाय एक का उपयोग कर सकता हूं?

Answer 1

यदि आप पहली बार चौड़ाई कर रहे हैं तो प्राकृतिक कार्यान्वयन नोड्स को कतार में धक्का देना है, रिकर्सन का उपयोग न करें।

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

#A tree is a tuple of an int and a tree. 
t = (1, (2,(4, (6), (7, (9)))), (3, (5, (8)))) 
def bfs(t): 
    to_visit = [t] 
    while len(to_visit) > 0: 
     c = to_visit[0] 
     if type(c) is int: 
      print c 
     else: 
      print c[0] 
      to_visit.append(c[1]) 
      if len(c) > 2: to_visit.append(c[2]) 
     to_visit = to_visit[1:] 

def dfs(t): 
    if type(t) is int: 
     print t 
     return 
    print t[0] 
    dfs(t[1]) 
    if len(t) > 2: dfs(t[2]) 

bfs(t) 
dfs(t) 

Answer 2

यह तुम क्या करने की गहराई-प्रथम या चौड़ाई-पहले ट्रेवर्सल चाहते हैं पर निर्भर करता है:

कुछ त्वरित अजगर अंतर को वर्णन करने। गहराई पहले रिकर्सन के माध्यम से लागू करने के लिए सबसे आसान है। ब्रेडथ-प्रथम के साथ आपको भविष्य में विस्तार करने के लिए नोड्स की कतार रखने की आवश्यकता है।

Answer 3

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

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

Answer 4

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

अगर कोई पेड़ नहीं है लेकिन एक अच्छी तरह से जुड़ा हुआ ग्राफ है, तो पहले से ही देखे गए नोड्स का ट्रैक रखने के लिए बस एक हैश है।

Answer 5

रिकर्सिव के साथ जाएं, क्योंकि आप वास्तव में एक स्टैक ओवरफ़्लो त्रुटि प्राप्त कर सकते हैं, और यह सब के बाद stackoverflow.com है।