Python - Albero binario

L'albero rappresenta i nodi collegati dai bordi. È una struttura dati non lineare. Ha le seguenti proprietà.

• Un nodo è contrassegnato come nodo radice.
• Ogni nodo diverso dalla radice è associato a un nodo padre.
• Ogni nodo può avere un numero arbiatry di chid node.

Creiamo una struttura dati ad albero in python utilizzando il concetto di nodo del sistema operativo discusso in precedenza. Designiamo un nodo come nodo radice e quindi aggiungiamo più nodi come nodi figlio. Di seguito è riportato il programma per creare il nodo radice.

Crea radice

Creiamo semplicemente una classe Node e aggiungiamo assegna un valore al nodo. Questo diventa albero con solo un nodo radice.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data


    def PrintTree(self):
        print(self.data)

root = Node(10)

root.PrintTree()

Quando il codice sopra viene eseguito, produce il seguente risultato:

10

Inserimento in un albero

Per inserire in un albero usiamo la stessa classe di nodi creata sopra e ad essa aggiungiamo un metodo di inserimento Il metodo di inserimento confronta il valore del nodo con il nodo genitore e decide di aggiungerlo come nodo sinistro o come nodo destro. Infine, il metodo PrintTree viene utilizzato per stampare l'albero.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
# Compare the new value with the parent node
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)

root.PrintTree()

Quando il codice sopra viene eseguito, produce il seguente risultato:

3 6 12 14

Attraversando un albero

L'albero può essere attraversato decidendo una sequenza per visitare ogni nodo. Come possiamo vedere chiaramente, possiamo iniziare da un nodo, quindi visitare prima il sottoalbero sinistro e poi il sottoalbero destro. Oppure possiamo anche visitare prima il sottoalbero destro e poi il sottoalbero sinistro. Di conseguenza, esistono nomi diversi per questi metodi di attraversamento dell'albero. Li studiamo in dettaglio nel capitolo che implementa gli algoritmi di tree traversal qui. Algoritmi di attraversamento dell'albero