représente les arbres de recherche binaire en python

Question

Comment représenter les arbres de recherche binaire 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 sur le dessus de la méthode walk:

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

et avec walk vous pouvez obtenir à peu près n'importe quelle autre fonctionnalité sur le flux de noeuds dans l'ordre, tandis qu'avec sillywalk, vous pouvez obtenir à peu près diddly-squat. Mais, hé, l'OP dit yield est "intimidant" (je me demande combien d'autres 30 mots-clés de Python 2.6 méritent de tels mots d'effroi dans le jugement d'OP? -) ainsi j'espère que print n'est pas!

Tout cela est tout à fait au-delà de la question réelle, sur représentant BSTS: que question est entièrement répondu à l'__init__ - un attribut payload pour maintenir la charge utile du noeud, left et right attribut à détenir soit None (ce qui signifie , ce noeud n'a pas de descendants de ce côté) ou un Node (le haut du sous-arbre des descendants du côté approprié). Bien sûr, la contrainte BST est que chaque descendant gauche de chaque nœud (le cas échéant) a une charge utile inférieure ou égale à celle du nœud en question, chaque droite (une fois de plus) a une plus grande charge utile - j'ai ajouté insert juste pour montrer combien il est trivial de maintenir cette contrainte, walk (et maintenant sillywalk) pour montrer à quel point il est trivial d'obtenir tous les nœuds dans l'ordre croissant des charges utiles. Encore une fois, l'idée générale est juste identique à la façon dont vous représentez un BST dans n'importe quel langage qui utilise des références plutôt que des pointeurs, comme, par exemple, C# et Java.