Representar árvores de busca binária em Python

Question

Como represento árvores de pesquisa binária em 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 - basicamente como em qualquer outro idioma que use referências em vez de ponteiros (como java, c#etc.).

Editar:

Claro, a própria existência de sillywalk é realmente bobo, porque exatamente a mesma funcionalidade é um trecho externo de liner-liner em cima do walk método:

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

e com walk Você pode obter praticamente qualquer outra funcionalidade no fluxo de nós em ordem, enquanto, com sillywalk, você pode obter quase-squat. Mas, ei, o OP diz yield "Intimidating" (eu me pergunto quantos das outras 30 palavras-chave do Python 2.6 merecem palavras tão assustadoras no julgamento do OP?-) Então, espero print não é!

Tudo isso está completamente além da questão real, em representando BSTs: este a pergunta é totalmente respondida no __init__ -- uma payload atributo para segurar a carga útil do nó, left e right atributo para segurar também None (ou seja, este nó não tem descendentes desse lado) ou um Node (o topo da sub-árvore de descendentes do lado apropriado). Obviamente, a restrição BST é que todo descendente esquerdo de cada nó (se houver) tem uma carga útil menos ou igual que a do nó em questão, cada direito (novamente, se houver) tem uma carga útil maior - adicionei insert só para mostrar como é trivial manter essa restrição, walk (e agora sillywalk) para mostrar como é trivial obter todos os nós em uma ordem crescente de cargas úteis. Novamente, a ideia geral é apenas idêntica à maneira como você representar Um BST em qualquer idioma que use referências em vez de ponteiros, como, por exemplo, C# e Java.