पायथन - वृक्ष ट्रैवर्सल प्रश्न

Question

मुझे पेड़ के ट्रैवर्सल के साथ कठिन समय है, और इसलिए इसे प्लेग की तरह से बचें ... सामान्य रूप से।

मैं एक वर्ग है कि तरह-की है (यहाँ थोड़ा सरलीकृत संस्करण है, लेकिन कार्यात्मक रूप में एक ही) की तरह:

class Branch(object): 
    def __init__(self, title, parent=None): 
     self.title = title 
     self.parent = parent 

मैं Branch उदाहरणों में से एक गुच्छा, के रूप में प्रत्येक के शीर्षक का एक शब्दकोश है कुंजियाँ:

tree = {'Foo Branch': foo, 'Sub-Foo Branch': sub_foo, 'Bar Branch': bar} 

अब, मुझे पता है ट्रेवर्सल कुशल (जैसे MPTT, एट अल), विशेष रूप से डेटाबेस चालित परियोजनाओं के साथ उपयोग के लिए कर रही है जहां दक्षता मामलों के लिए जटिल एल्गोरिदम देखते हैं कि अधिकांश। मैं डेटाबेस का उपयोग नहीं कर रहा हूं, केवल साधारण स्मृति-स्मृति वस्तुओं में।

एक Branch की title देखते हुए, मैं तो tree से उस शाखा के सभी सन्तान (बच्चों, बच्चों के बच्चों, तो पर) के list प्राप्त करने की आवश्यकता,:

1. आप अभी भी एक का उपयोग कर की सिफारिश करेंगे, जटिल (मेरे अलगो-कम मस्तिष्क के लिए :) मेरे मामले में दक्षता के लिए एमपीटीटी की तरह एल्गोरिदम, या एक समारोह में इसे प्राप्त करने का एक आसान तरीका है?
2. यदि हां, तो आप कौन सी सिफारिश करेंगे, यह जानकर कि मैं डेटाबेस का उपयोग नहीं कर रहा हूं?
3. क्या आप एक उदाहरण प्रदान कर सकते हैं, या यह सोचने से बहुत बड़ा है?

नोट: यह होमवर्क असाइनमेंट नहीं है। मैं स्कूल में नहीं हूँ मैं वास्तव में एल्गोरिदम पर यह बुरा हूँ। मैंने एक परियोजना के लिए Django एमपीटीटी का उपयोग किया है जिसके लिए डीबी-संग्रहित पेड़ की आवश्यकता है ... लेकिन फिर भी इसे बहुत अच्छी तरह से समझ में नहीं आता है।

Answer 1

http://en.wikipedia.org/wiki/Depth-first_search

http://en.wikipedia.org/wiki/Tree_traversal

दो गुजरता में इस प्रकार आप पार:

• पहले पास: उचित कुंजी के साथ क्वेरी नोड के लिए खोजें। (यदि आप सभी पूरे पेड़ में नोड्स के एक hashmap है यह कदम अनावश्यक है, तो आप इस (अच्छा है) तो यह चरण आवश्यक नहीं है।)

• दूसरा पास: एल्गोरिथ्म का एक संशोधित संस्करण कॉल क्वेरी नोड पर, लेकिन इस बार, जब भी आप नोड पर जाते हैं, तो इसे उपज दें (या इसे एक गैर-संचय संचयक चर में संलग्न करें)।

हालांकि आपकी स्थिति थोड़ा अजीब है, क्योंकि आम तौर पर पेड़ों में बच्चों को पॉइंटर्स भी होते हैं, जैसे कि डबल-लिंक्ड सूची की तरह। दुर्भाग्य से हम उस जानकारी नहीं है ... लेकिन सौभाग्य से यह है कि सूचना जोड़ना आसान है:

nodes = tree.values() 
for node in nodes: 
    if node.parent: 
     if not hasattr(node.parent, 'children'): 
      node.parent.children = [] 
     node.parent.children +=[ node ] 

अब हम हमारे उदाहरण के साथ आगे बढ़ना कर सकते हैं:

def traverse(root, callback): 
    """ 
     Peform callback on all nodes in depth-first order 
     e.g. traverse(root, lambda x:print(x)) 
    """ 
    yield root, callback(root) 
    for child in root.children: 
     traverse(child) 

def getAllDescendents(title): 
    queryNode = titlesToNodes[title] #what you call 'tree' 
    for node,blah in traverse(queryNode, lambda x:None): 
     yield node