représentent des arbres binaires de recherche en python

Question

Comment puis-je représenter des arbres binaires de recherche en python?

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, etc -. Essentiellement comme dans toute autre langue qui utilise des références plutôt que des pointeurs (tels que Java, C #, etc.)

Modifier :

Bien sûr, l'existence même de sillywalk est ridicule en effet, parce que la même fonctionnalité est un extrait externe roussir-liner au-dessus de la méthode walk:

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

et walk vous pouvez obtenir à peu près toute autre fonctionnalité sur les nœuds en ordre courant, alors que, avec sillywalk, vous pouvez obtenir à peu près diddly-squat. Mais, bon, l'OP dit yield est « intimidante » (Je me demande combien d'autres 30 mots-clés Python 2.6 méritent ces mots alarmistes dans le jugement de l'OP -)! Donc j'espère print est pas

Ceci est d'autant complètement au-delà de la question réelle, sur représentant BSTS: que La question est tout à fait répondu à la __init__ - un attribut payload pour maintenir la charge utile du noeud, left et attribut right à la main soit None (sens, ce noeud n'a pas de descendants de ce côté) ou un Node (la partie supérieure du sous-arbre des descendants sur le côté approprié). Bien sûr, la contrainte de BST est que tous les descendants gauche de chaque noeud (le cas échéant) a une charge utile inférieure ou égale à celle du nœud en question, chacun droit (encore une fois, le cas échéant) a une charge utile plus - j'ai ajouté insert juste pour montrer comment il est trivial de maintenir cette contrainte, walk (et maintenant sillywalk) pour montrer comment il est trivial d'obtenir tous les noeuds dans l'ordre croissant des charges utiles. Encore une fois, l'idée générale est juste identique à la façon dont vous souhaitez représentent un BST dans toutes les langues qui utilise des références plutôt que des pointeurs, comme, par exemple, C # et Java.