representar árboles binarios de búsqueda en pitón

Question

¿Cómo represento árboles binarios de búsqueda 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 -. Básicamente, como en cualquier otro idioma que utiliza referencias en lugar de punteros (como Java, C #, etc)

Editar

Por supuesto, la propia existencia de sillywalk es tonto de hecho, debido a exactamente la misma funcionalidad es un fragmento externo singe-liner en la parte superior del método walk:

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

y con walk puede obtener casi cualquier otra funcionalidad en el flujo de nodos en orden, mientras que, con sillywalk, puede obtener casi diddly-squat. Pero, bueno, el PO dice yield está "intimidante" (Me pregunto cuántos de Python 2.6 otras 30 palabras clave merecen tales palabras susto en el juicio de la OP -?)! Así que estoy esperando print no es

Todo esto es totalmente más allá de la cuestión real, en representando BSTs: que pregunta se responde por completo en el __init__ - un atributo payload para sostener la carga útil del nodo, left y el atributo right para sostener ya sea None (sentido, este nodo no tiene descendientes de ese lado) o un Node (la parte superior de la sub-árbol de descendientes en el lado apropiado). Por supuesto, la restricción BST es que cada descendiente izquierda de cada nodo (si lo hay) tiene una carga útil menor o igual que la del nodo en cuestión, cada uno derecho (de nuevo, en su caso) tiene una carga útil mayor - añadí insert sólo para mostrar lo trivial que es mantener esa restricción, walk (y ahora sillywalk) para mostrar cómo es trivial que es conseguir que todos los nodos con el fin de aumentar la carga útil. Una vez más, la idea general es idéntica a la forma en que le representa a la BST en cualquier lenguaje que utiliza referencias en lugar de punteros, como, por ejemplo, C # y Java.