Comment représenter les arbres de recherche binaire en python?représente les arbres de recherche binaire en python
Répondre
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.
Vous devriez l'espacer un peu, c'est assez difficile à lire tous ensemble comme ça. – detly
@Alex Rendement !!!! : | Je suis sûr qu'il y a une solution moins intimidante que cela pour un débutant comme moi. –
@Bunny, Python a en effet très peu de mots-clés (31, à partir de la 2.6) - lesquels parmi ceux-ci trouvez-vous "intimidant"? Quoi qu'il en soit, je vais ajouter une méthode de marche complètement idiote et inutile (fonctionnant essentiellement comme "marcher" mais d'une manière incroyablement limitée) si cela vous rend heureux (et ajouter des espaces pour rendre @detly heureux aussi) - éditer le A en conséquence. –
- 1. Arbres de recherche binaire
- 2. arbres de recherche binaire dans ruby
- 3. Énumérer les arbres de recherche
- 4. arbres de recherche binaires randomisés
- 5. arbre de recherche binaire de sortie unpredicted en python
- 6. L'arbre de recherche binaire en python ne fonctionnait pas
- 7. Dictionnaire Python - recherche binaire d'une clé?
- 8. tableau binaire en python
- 9. Arbres d'expression C# - Recherche de valeur dynamique
- 10. recherche d'un arbre binaire
- 11. arbre de recherche binaire
- 12. arbre de recherche binaire
- 13. Python: manipuler des sous-arbres
- 14. Arbre de recherche binaire en Java
- 15. Comprendre les arbres de fusion?
- 16. Supprimer dans l'arborescence de recherche binaire?
- 17. comment imprimer des arbres sur la console?
- 18. Implémenter la recherche binaire dans les objets
- 19. Outils de recherche d'analyse binaire
- 20. Solveur de programmation linéaire binaire en Python
- 21. Conversion Python de chaîne binaire en hexadécimal
- 22. recherche séquentielle ou binaire
- 23. Les arbres d'expression dans NHibernate
- 24. Convertir décimal en binaire en python
- 25. Variation de recherche binaire C#
- 26. arbre recherche binaire
- 27. recherche binaire question
- 28. Comment manipuler les arbres d'analyse?
- 29. Les arbres dans Haskell
- 30. javascript implémentation de l'arbre de recherche binaire
Pouvez-vous être plus précis? Qu'essayez-vous de faire? –
J'essaie de construire un arbre de recherche binaire pour l'apprentissage. –