Rappresentazione di alberi binari
Gli alberi binari sono una struttura dati fondamentale, ampiamente utilizzata nell’informatica. Sono particolarmente utili per la creazione di algoritmi efficienti, ad esempio per la ricerca, l’ordinamento e l’attraversamento dei dati.
Gli alberi binari sono composti da nodi, ognuno dei quali può avere al massimo due figli: uno sinistro e uno destro. Ciascuno di questi figli può a sua volta avere i propri figli sinistro e destro, e la struttura si propaga finché non ci sono più nodi nell’albero.
Il nodo più in alto in un albero binario viene chiamato radice (root), mentre gli elementi più in basso sono noti come foglie (leaves) dell’albero.
Questa semplice idea rende possibile rappresentare un gran numero di differenti tipi di dati in modo efficiente ed è anche facile da implementare in vari linguaggi di programmazione:
class Node: # Oggetto Node che contiene i dati di ciascun nodo
def __init__(self, value): # Il valore da conservare in ogni nodo (può essere qualsiasi cosa)
self.left = None # Inizialmente sia left che right sono None
self.right = None
self.value = value # Tiene il valore in un oggetto
# Creazione manuale di tutti i nodi
root = Node(1)
root.left, root.right = Node(2), Node(3)
root.left.left, root.left.right = Node(4), Node(5)
root.left.right.left, root.left.right.right = Node(7), Node(8)
root.right.right = Node(6)
# Possiamo quindi attraversare ricorsivamente l’intero albero binario
# Calcoliamo la somma di tutti i nodi
def treesum(node: Node | None) -> int:
if node is None:
return 0
# Restituisci la somma del sottoalbero sinistro, del sottoalbero destro e del nodo corrente
return treesum(node.left) + treesum(node.right) + node.value
print(treesum(root)) # Stampa 36In questo esempio, attraversiamo tutti i nodi a partire dalla
root. Se il nodo corrente è None, significa che abbiamo raggiunto la fine del sottoalbero lungo quel percorso, e quindi possiamo restituire 0 come somma. Altrimenti, calcoliamo la somma del sottoalbero sinistro, del sottoalbero destro e del nodo corrente, sommando tutto insieme.Sfida: crea manualmente un albero binario
Osservando l’albero binario raffigurato nell’immagine, ti viene chiesto di crearlo manualmente.
Scrivi il codice che costruisca l’albero binario. Non è necessario stampare nulla, poiché questa parte è gestita in automatico.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB