rappresentano alberi di ricerca binari in Python
-
27-09-2019 - |
Domanda
come rappresento gli alberi di ricerca binari in Python?
Soluzione
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 - fondamentalmente come in qualsiasi altro linguaggio che utilizza riferimenti anziché puntatori (come Java, C#, ecc.).
Modificare:
Naturalmente, l'esistenza stessa di sillywalk
è davvero sciocco, perché esattamente la stessa funzionalità è uno snippet esterno a fodera singola sopra il file walk
metodo:
for x in tree.walk(): print(x.payload)
e con walk
puoi ottenere praticamente qualsiasi altra funzionalità sul flusso dei nodi in ordine, mentre, con sillywalk
, puoi ottenere quasi un tozzo.Ma, ehi, dice l'OP yield
è "intimidatorio" (mi chiedo quante delle altre 30 parole chiave di Python 2.6 meritano parole così spaventose a giudizio dell'OP? -) quindi spero print
non lo è!
Tutto questo va completamente oltre la vera domanda, su che rappresentano BST: Quello la risposta alla domanda è completa nel __init__
-- UN payload
attributo per contenere il carico utile del nodo, left
E right
attributo da contenere None
(il che significa che questo nodo non ha discendenti da quel lato) o a Node
(la parte superiore del sottoalbero dei discendenti sul lato appropriato).Naturalmente, il vincolo BST è che ogni discendente sinistro di ciascun nodo (se presente) ha un carico utile inferiore o uguale a quello del nodo in questione, ogni discendente destro (di nuovo, se presente) ha un carico utile maggiore - ho aggiunto insert
giusto per mostrare quanto sia banale mantenere quel vincolo, walk
(e adesso sillywalk
) per mostrare quanto sia banale ottenere tutti i nodi in ordine crescente di payload.Ancora una volta, l'idea generale è identica a quella che faresti tu rappresentare un BST in qualsiasi linguaggio che utilizzi riferimenti anziché puntatori, come, ad esempio, C# e Java.