Nodi e Riferimenti¶

Il nostro secondo metodo per rappresentare un albero usa nodi e riferimenti. In questo caso definiamo una classe che ha attributi per la radice e per i sottoalberi sinistro e destro. Dal momento che questa rappresentazione segue più fedelmente il paradigma di programmazione orientato agli oggetti, useremo questa rappresentazione in seguito.

Usando nodi e riferimenti, potremmo pensare a un albero come quello mostrato in Figura 2.

Figura 2: Un semplice albero che usa nodi e riferimenti

Cominceremo con una classe semplice per i nodi e i riferimenti come mostrato in Listing 4. La cosa importante da ricordare riguardo questa implementazione è che gli attributi left e right diventeranno riferimenti a altre istanze della classe BinaryTree. Per esempio, quando inseriamo un nuovo figlio sinistro nell’albero creiamo un’altra istanza di BinaryTree e modifichiamo self.leftChild nella radice per riferirci al nuovo albero.

Listing 4

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

Notiamo che Listing 4, il costruttore si aspetta un oggetto da memorizzare nella radice. Dal momento che possiamo memorizzare qualsiasi oggetto nella radice, come in una lista, l’oggetto da memorizzare può essere di qualsiasi tipo e riferirsi a qualsiasi oggetto. Seguendo gli esempi precedenti, memorizzeremo il nome dei nodi come valore della radice. Usando nodi e riferimenti per rappresentare l’albero in Figura 2, creeremo sei istanze della classe BinaryTree class.

Osserviamo le funzioni di cui abbiamo bisogno per costruire l’albero oltre la radice. Per aggiungere il figlio sinistro, creeremo un nuovo oggetto albero binario imposteremo l’attributo left della radice per riferirci a questo nuovo oggetto. Il codice per insertLeft è mostrato in Listing 5.

Listing 5

1
2
3
4
5
6
7

def insertLeft(self,newNode):
    if self.leftChild == None:
        self.leftChild = BinaryTree(newNode)
    else:
        t = BinaryTree(newNode)
        t.leftChild = self.leftChild
        self.leftChild = t

Dobbiamo considerare due casi per l’inserimento. Il primo caso è caratterizzato da un nodo senza figlio sinistro. Quando non c’è figlio sinistro, semplicemente aggiungiamo un nodo all’albero. Il secondo caso è caratterizzato da un nodo che ha già un figlio sinistro non vuoto. In questo secondo caso, inseriamo un nodo, spingendo il figlio esistente giù di un livello. Questo caso corrisponde al ramo else sulla linea 4 di Listing 5.

Il codice insertRight considera un insieme di casi simmetrico. Non c’è un figlio destro, oppure dobbiamo inserire il nodo tra la radice e un figlio destro esistente.. Il codice di inserimento è mostrato in Listing 6.

Listing 6

def insertRight(self,newNode):
    if self.rightChild == None:
        self.rightChild = BinaryTree(newNode)
    else:
        t = BinaryTree(newNode)
        t.rightChild = self.rightChild
        self.rightChild = t

Per completare la definizione della struttura dati, scriviamo metodi di accesso in Listing 7 per la radice e i sottoalberi sinistro e destro.

Listing 7

def getRightChild(self):
    return self.rightChild

def getLeftChild(self):
    return self.leftChild

def setRootVal(self,obj):
    self.key = obj

def getRootVal(self):
    return self.key

Adesso che abbiamo tutte le informazioni necessarie per manipolare un albero binario, qui di seguito mostriamo come usarle. Costruiamo un semplice albero che ha il nodo a come radice. Aggiungiamo i nodi b e c come figli. ActiveCode 1 crea l’albero e controlla alcuni dei valori memorizzati in key, left e right. Notiamo che entrambi i figli sinistro e destro della radice sono essi stessi istanze distinte della classe BinaryTree. Come detto nella definizione originale ricorsiva di albero, questo ci permette di trattare tutti i figli allo stesso modo e nello stesso modo in cui trattiamo la radice, ovvero come un albero binario..

Per estendere quanto abbiamo visto a alberi con un numero arbitrario di figli, basta rimpiazzare self.leftChild e self.rightChild con una lista self.children, che può avere un numero arbitrario di elementi, consentendo dunque alla radice di avere un numero arbitrario di figli.