एक पेड़ चलना, माता-पिता पहले

Question

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

Answer 1

छद्म कोड:

NodesToVisit = some stack or some list 
NodesToVisit.Push(RootNode) 

While NodesToVisit.Length > 0 
{ 
    CurNode = NodesToVisit.Pop() 
    For each Child C in CurNode 
     NodesToVisit.Push(C) 
    Visit(CurNode) (i.e. do whatever needs to be done) 
} 

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

• केवल "चर" ढेर पर धकेल दिया जाता है; स्टैक पर कोई "स्टैक फ्रेम" और संबंधित रिटर्न पता नहीं है, केवल "वापसी पता" थोड़ी देर के लिए निहित है, और इसका एक उदाहरण भी है।
• "स्टैक" का उपयोग एक सूची के रूप में किया जा सकता है जिससे किसी भी तरीके से तर्क को तोड़ने के बिना, सूची में कहीं भी "फ्रेम" कहीं भी लिया जा सकता है।

Answer 2

रूट (स्तर 0) पर नोड्स की एक सूची बनाएं, बदले में प्रत्येक नोड पर फिर से चलें और सीधे बच्चों की तलाश करें (जिनके पैरेंट नोड वह नोड है जिसे हम वर्तमान में देख रहे हैं) (स्तर 1), जब समाप्त हो गया स्तर 0 को पुनरावृत्त स्तर 1 पर ले जाएं, और तब तक जब तक आपके पास कोई अवकाश नोड्स न हो।

Answer 3

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

Answer 4

स्यूडोकोड में:

currentList = list(root) 
nextList = list() 
while currentList.count > 0: 
    foreach node in currentList: 
     nextList.add(node.children) 
    currentList = nextList 

Answer 5

आप में अग्रिम आदेश ट्रावर्सल के लिए देख रहे हैं। मुझे लगता है कि आप इसे कतार के साथ गैर-पुनरावर्ती कर सकते हैं:। छद्म कोड में:

खाली कतार बनाएं, फिर रूट नोड को दबाएं।

while nonempty(q) 
    node = pop(q) 
    visit(node) 
    foreach child(node) 
    push(q,child) 

Answer 6

Breadth First Search

Answer 7

आप रूट नोड में शुरू, और केवल नोड्स आप पहले से ही आने वाले लोगों की माता-पिता/बच्चों पर जाते हैं, वहाँ कोई रास्ता नहीं पेड़ पार करने के लिए ऐसी है कि आप अपने पूर्वजों जाने से पहले एक नोड की यात्रा है।

किसी भी तरह का ट्रैवर्सल, गहराई पहले (रिकर्सिव/स्टैक आधारित), चौड़ाई पहले (कतार आधारित), गहराई से सीमित, या सिर्फ उन्हें एक अनियमित सेट से बाहर खींचकर काम करेगा।

"सर्वोत्तम" विधि पेड़ पर निर्भर करती है। ब्रेड पहले कुछ शाखाओं के साथ एक बहुत लंबे पेड़ के लिए अच्छी तरह से काम करेगा। गहराई पहले कई शाखाओं के साथ पेड़ों के लिए अच्छी तरह से काम करेगा।

चूंकि नोड्स में वास्तव में उनके माता-पिता के पॉइंटर्स होते हैं, इसलिए एक स्थिर-स्मृति एल्गोरिदम भी होता है, लेकिन यह बहुत धीमा है।

Answer 8

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

Answer 9

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

संदर्भ: कोई ढेर, निरंतर अंतरिक्ष: http://en.wikipedia.org/wiki/Iterative_deepening

Answer 10

यहाँ एक सही मायने में गैर पुनरावर्ती तरीका है। यह अजगर कोड मानता है कि प्रत्येक नोड बच्चों की एक सूची है, और इतना है कि 'सूचकांक' समारोह पहचान तुलना कर रहा है नोड वस्तुओं समानता परिभाषित नहीं करते कि,:

def walkTree(root, visit_func): 
    cur = root 
    nextChildIndex = 0 

    while True: 
     visit_func(cur) 

     while nextChildIndex >= len(cur.children) and cur is not root: 
      nextChildIndex = cur.parent.children.index(cur) + 1 
      cur = cur.parent 

     if nextChildIndex >= len(cur.children): 
      break 

     cur = cur.children[nextChildIndex] 
     nextChildIndex = 0 

मुझे यकीन है कि यह पॉलिश किया जा सकता है कर रहा हूँ थोड़ा, पढ़ने के लिए और अधिक संक्षिप्त और आसान बना दिया, लेकिन यह बात है।