पाइथन

Question

में बाइनरी खोज पेड़ का प्रतिनिधित्व करता है मैं पाइथन में बाइनरी खोज पेड़ का प्रतिनिधित्व कैसे करूं?

Answer 1

class Node(object): 

    def __init__(self, payload): 
    self.payload = payload 
    self.left = self.right = 0 

    # this concludes the "how to represent" asked in the question. Once you 
    # represent a BST tree like this, you can of course add a variety of 
    # methods to modify it, "walk" over it, and so forth, such as: 

    def insert(self, othernode): 
    "Insert Node `othernode` under Node `self`." 
    if self.payload <= othernode.payload: 
     if self.left: self.left.insert(othernode) 
     else: self.left = othernode 
    else: 
     if self.right: self.right.insert(othernode) 
     else: self.right = othernode 

    def inorderwalk(self): 
    "Yield this Node and all under it in increasing-payload order." 
    if self.left: 
     for x in self.left.inorderwalk(): yield x 
    yield self 
    if self.right: 
     for x in self.right.inorderwalk(): yield x 

    def sillywalk(self): 
    "Tiny, silly subset of `inorderwalk` functionality as requested." 
    if self.left: 
     self.left.sillywalk() 
    print(self.payload) 
    if self.right: 
     self.right.sillywalk() 

आदि, आदि - मूल रूप से किसी भी अन्य भाषा (जैसे जावा, सी #, आदि) के संकेत के बजाय संदर्भ का उपयोग करता है की तरह।

संपादित:

बेशक

, sillywalk के अस्तित्व, वास्तव में मूर्खतापूर्ण है, क्योंकि वास्तव में ही कार्यक्षमता एक झुलसाना-लाइनर walk विधि के शीर्ष पर बाहरी टुकड़ा है:

for x in tree.walk(): print(x.payload) 

और walk के साथ आप नोड्स-इन-ऑर्डर स्ट्रीम पर किसी भी अन्य कार्यक्षमता के बारे में प्राप्त कर सकते हैं, जबकि sillywalk के साथ, आप केवल डीडली-स्क्वाट के बारे में प्राप्त कर सकते हैं। लेकिन, हे, ओपी का कहना है कि yield "डरावना" है (मुझे आश्चर्य है कि कितने पायथन 2.6 के अन्य 30 कीवर्ड ओपी के फैसले में ऐसे डरावने शब्दों के लायक हैं?)) तो मुझे उम्मीद है कि print नहीं है!

यह पूरी तरह से वास्तविक सवाल से परे सभी है, BSTs का प्रतिनिधित्व करने पर: कि सवाल पूरी तरह __init__ में उत्तर दिया जाता है - एक payload विशेषता नोड के पेलोड धारण करने के लिए, left और right विशेषता या तो None (जिसका अर्थ है धारण करने के लिए , इस नोड में उस तरफ कोई वंशज नहीं है) या Node (उचित तरफ वंश के उप-पेड़ के शीर्ष)। बेशक, बीएसटी बाधा यह है कि प्रत्येक नोड (यदि कोई है) के प्रत्येक बाएं वंशज को नोड के मुकाबले कम या बराबर पेलोड होता है, तो हर सही एक (फिर, अगर कोई है) में अधिक पेलोड होता है - मैंने insert जोड़ा यह दिखाने के लिए कि उस बाधा को बनाए रखने के लिए कितना छोटा है, walk (और अब sillywalk) यह दिखाने के लिए कि सभी नोड्स पेलोड के क्रम में बढ़ने के लिए कितना छोटा है। दोबारा, सामान्य विचार उसी तरह से समान है जिस तरह से आप किसी भी भाषा में बीएसटी का प्रतिनिधित्व करते हैं जो पॉइंटर्स के बजाए संदर्भों का उपयोग करता है, उदाहरण के लिए, सी # और जावा।