Implementa una struttura dati ad albero in Python

1. Implementa un albero da zero in Python
2. Attraversa un albero binario in Python
3. Implementa un albero usando una libreria Python

Un albero è una delle strutture di dati. Una struttura dati non è altro che come organizziamo i dati in memoria. Un albero è una combinazione di nodi (noti anche come vertici) e bordi. Un albero può avere un numero qualsiasi di nodi e bordi. Un nodo è dove memorizziamo i dati e un bordo è un percorso tra 2 nodi. Sono disponibili vari tipi di alberi come albero binario, albero ternario, albero di ricerca binario, albero AVL, ecc.

Tipi di nodi in un albero:

1. Nodo padre: un nodo che ha uno o più figli.
2. Nodo figlio: un nodo che ha un nodo padre.
3. Nodo foglia: un nodo che non ha figli.

In questo articolo, vediamo prima come implementare un albero da zero senza utilizzare alcuna libreria, e successivamente vedremo come implementare un albero con l’aiuto di una libreria Python.

Implementa un albero da zero in Python

Per creare un albero in Python, dobbiamo prima iniziare creando una classe Node che rappresenterà un singolo nodo. Questa classe Node conterrà 3 variabili; la prima è la left che punta al figlio di sinistra, la seconda variabile data che contiene il valore per quel nodo e la variabile right che punta al figlio di destra.

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

Inizializziamo un albero.

root = Node(10)

root.left = Node(34)
root.right = Node(89)
root.left.left = Node(45)
root.left.right = Node(50)

L’albero appare come sotto.

          10
        /    \
       34      89
     /    \ 
    45    50 

Ogni volta che crei un oggetto della classe Node, verrà chiamato il costruttore __init__ e verranno inizializzate tutte le variabili all’interno di quel costruttore. La root contiene il nodo radice dell’albero, che ha un valore di 10, e root.left e root.right usando i quali inseriremo il figlio sinistro con il valore 34 e il destro figlio al nodo radice con il valore 89. Poiché è un albero binario, ogni nodo conterrà al massimo due nodi.

Alla fine, inseriamo altri due nodi nell’albero, cioè 45 e 50, come i figli del nodo 34. Puoi inserire qualsiasi numero di nodi che desideri all’interno di un albero a seconda del tipo di albero che stai creando.

Attraversa un albero binario in Python

Ora abbiamo creato un albero, quindi attraversiamo l’albero per stampare gli elementi dell’albero. Un attraversamento visita ogni nodo in un albero. Ogni nodo in un albero verrà visitato tre volte durante l’attraversamento. Un modo in cui attraversiamo un albero è dall’alto verso il basso e da sinistra a destra.

Traversal pre-ordine

Durante l’attraversamento di un albero, ogni volta che vediamo il nodo per la prima volta, stampiamo quel nodo, quindi eseguiamo la ricorsione sul nodo sinistro e poi sul nodo destro.

def preorder(node):
    if node:
        print(node.data)
        preorder(node.left)
        preorder(node.right)

Produzione:

10 
34 
45 
50 
89

Traversal in ordine

Durante l’esecuzione dell’in-order traversal, eseguiamo prima la ricorsione sul nodo sinistro e poi, mentre visitiamo lo stesso nodo per la seconda volta, stampiamo quel nodo. Quindi eseguiamo la ricorsione sul nodo destro.

def inorder(node):
    if node:
        inorder(node.left)
        print(node.data)
        inorder(node.right)

Produzione:

45 
34 
50 
10 
89

Traversal Post-Ordine

Per il Post-order traversal, eseguiamo la ricorsione sul nodo sinistro e sul nodo destro, quindi mentre visitiamo lo stesso nodo per la terza volta, stampiamo quel nodo.

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.data)

Produzione:

45
50
34
89
10

Implementa un albero usando una libreria Python

Come abbiamo visto, l’implementazione di un albero da zero richiede un po’ di tempo e richiede molto codice. Un modo più semplice per implementare un albero in Python è usare una libreria chiamata anytree. La libreria anytree ti consente di creare un albero senza scrivere un sacco di codice.

Per usare la libreria anytree, dobbiamo prima installarla con l’aiuto del comando seguente.

pip install anytree

Anche qui stiamo creando lo stesso albero che abbiamo creato in precedenza. Ora possiamo importare Node e RenderTree dalla libreria anytree.

from anytree import Node, RenderTree

root = Node(10)

level_1_child_1 = Node(34, parent=root)
level_1_child_2 = Node(89, parent=root)
level_2_child_1 = Node(45, parent=level_1_child_1)
level_2_child_2 = Node(50, parent=level_1_child_2)

for pre, fill, node in RenderTree(root):
    print("%s%s" % (pre, node.name))

# Tree Structure
#          10
#        /    \
#       34      89
#     /    \
#    45    50

Produzione:

10
├── 34
│   └── 45
└── 89
    └── 50

Qui, il Node creerà per noi un nodo che accetta due parametri; il primo è il valore del nodo e il secondo è il nome del nodo padre (questo è un parametro opzionale). Poiché nel nostro albero il nodo root è l’unico nodo che non ha alcun genitore, durante la creazione del nodo root passeremo solo il primo parametro: il valore del nodo e non il secondo parametro. Il metodo RenderTree ci aiuterà a stampare l’intero albero come mostrato nell’output.