HOWTO · Python
Implementa una struttura dati ad albero in Python
In questo articolo vedremo come implementare una struttura dati ad albero in Python.
In questa pagina
Un albero organizza i dati in nodi collegati da archi. Ogni arco collega un nodo padre a un nodo figlio; un nodo senza figli è una foglia. Esistono alberi binari, ternari, alberi binari di ricerca e alberi AVL; in un albero binario, ogni nodo può avere al massimo due figli. Questa guida costruisce un piccolo albero binario con una classe Node personalizzata, lo visita in tre ordini depth-first e presenta anytree come alternativa basata su una libreria.
Implementare da zero una struttura ad albero in Python
Un nodo di un semplice albero binario deve contenere il proprio valore e i riferimenti ai due nodi figli. La classe Node qui sotto memorizza il valore in data; left e right iniziano con None e possono poi fare riferimento ai nodi figli. Collegando questi oggetti si crea l’albero.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
root = Node(10)
root.left = Node(34)
root.right = Node(89)
root.left.left = Node(45)
root.left.right = Node(50)
Qui root è il padre di 34 e 89. I nodi 45 e 50 sono figli di 34; 89, 45 e 50 sono foglie. Questa struttura è specificamente un albero binario, perché ogni nodo ha al massimo due riferimenti ai figli. Altri tipi di albero possono richiedere una rappresentazione diversa, ad esempio una raccolta di figli anziché gli attributi fissi left e right.
Visitare un albero binario in Python
Una visita elabora ogni nodo una sola volta; l’ordine dipende dal momento in cui si visita il nodo rispetto alle chiamate ricorsive. La visita in preordine elabora il nodo corrente prima dei sottoalberi sinistro e destro. In ordine, elabora prima il sottoalbero sinistro, poi il nodo corrente e infine quello destro. In postordine, elabora entrambi i sottoalberi prima del nodo corrente. L’esempio completo qui sotto costruisce lo stesso albero e stampa ciascun ordine.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def preorder(node):
if node:
print(node.data)
preorder(node.left)
preorder(node.right)
def inorder(node):
if node:
inorder(node.left)
print(node.data)
inorder(node.right)
def postorder(node):
if node:
postorder(node.left)
postorder(node.right)
print(node.data)
root = Node(10)
root.left = Node(34)
root.right = Node(89)
root.left.left = Node(45)
root.left.right = Node(50)
print("Pre-order:")
preorder(root)
print("In-order:")
inorder(root)
print("Post-order:")
postorder(root)
Le chiamate ricorsive seguono gli stessi riferimenti left e right creati nella prima sezione. Per usare un altro albero, mantieni le funzioni di visita e sostituisci la costruzione dei nodi: la posizione scelta per la visita determina l’ordine dei valori.
Implementare un albero con una libreria Python
Per alberi con molti nodi o funzionalità che vanno oltre questo piccolo esempio di albero binario, anytree mette a disposizione le relazioni tra i nodi e uno strumento per visualizzarli. Installala nell’ambiente del progetto con pip install anytree. Nella sua API, Node accetta il nome del nodo come argomento posizionale; per collegare un figlio, passa parent=root come argomento con nome. RenderTree scorre la gerarchia e fornisce il prefisso usato per visualizzare ogni livello.
Per ottenere la stessa struttura mostrata sopra, si può usare il seguente schema: root = Node("10"), seguito da Node("34", parent=root) e Node("89", parent=root). Crea Node("45", parent=left_child) e Node("50", parent=left_child) per collocare entrambe le foglie sotto 34; quindi scorri la struttura con for pre, fill, node in RenderTree(root) e stampa pre + node.name. Questi frammenti descrivono l’API della libreria, ma non è fornita evidenza della loro esecuzione.