تمثل أشجار البحث الثنائية في بيثون

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()

ETC ، إلخ - كما هو الحال في أي لغة أخرى تستخدم المراجع بدلاً من المؤشرات (مثل Java ، C#، إلخ).

يحرر:

بالطبع ، وجود sillywalk هو سخيف في الواقع ، لأن نفس الوظيفة بالضبط هي مقتطف خارجي من Singe-Liner على رأس walk طريقة:

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

ومع walk يمكنك الحصول على أي وظيفة أخرى على دفق العقد في الطلب ، في حين sillywalk, ، يمكنك الحصول على diddly-squat. ولكن ، مهلا ، OP يقول yield هل "تخويف" (أتساءل كم من الكلمات الرئيسية الثلاثين الأخرى في Python 2.6 تستحق مثل هذه الكلمات المخيفة في حكم البروتوكول الاختياري؟) لذلك آمل print لا!

هذا كل شيء خارج السؤال الفعلي ، على يمثل BSTS: الذي - التي تم الإجابة على السؤال بالكامل في __init__ -- أ payload تعزى إلى الاحتفاظ بحمولة العقدة ، left و right تعزى إلى الإمساك أيضًا None (بمعنى أن هذه العقدة لا تحتوي على أحفاد على هذا الجانب) أو أ Node (الجزء العلوي من الشجرة الفرعية لأحفاد على الجانب المناسب). بطبيعة الحال ، فإن قيود BST هي أن كل سليل يسار لكل عقدة (إن وجدت) لديه حمولة أقل أو متساوية من العقدة المعنية ، كل واحد يمين (مرة أخرى ، إن وجد) لديه حمولة أكبر - أضفت insert فقط لإظهار مدى تافها للحفاظ على هذا القيد ، walk (و الأن sillywalk) لإظهار مدى تافهة الحصول على جميع العقد بترتيب متزايد من الحمولات. مرة أخرى ، الفكرة العامة متطابقة فقط مع الطريقة يمثل BST في أي لغة تستخدم المراجع بدلاً من المؤشرات ، مثل ، على سبيل المثال ، C# و Java.