Python - Algoritmi di attraversamento degli alberi
L'attraversamento è un processo per visitare tutti i nodi di un albero e può anche stampare i loro valori. Poiché tutti i nodi sono collegati tramite bordi (collegamenti), iniziamo sempre dal nodo radice (testa). Cioè, non possiamo accedere in modo casuale a un nodo in un albero. Ci sono tre modi che usiamo per attraversare un albero:
- Attraversamento in ordine
- Preordina Traversal
- Post-order Traversal
Attraversamento in ordine
In questo metodo di attraversamento, viene visitato prima il sottoalbero sinistro, quindi la radice e successivamente il sottoalbero destro. Dobbiamo sempre ricordare che ogni nodo può rappresentare una sottostruttura stessa.
Nel programma python sottostante, usiamo la classe Node per creare segnaposto per il nodo radice e per i nodi sinistro e destro. Quindi creiamo una funzione di inserimento per aggiungere dati all'albero. Infine, la logica di attraversamento di Inorder viene implementata creando un elenco vuoto e aggiungendo prima il nodo sinistro seguito dal nodo radice o padre. Infine viene aggiunto il nodo sinistro per completare la traversata in ordine. Notare che questo processo viene ripetuto per ogni sottoalbero finché tutti i nodi non vengono attraversati.
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
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()
# Inorder traversal
# Left -> Root -> Right
def inorderTraversal(self, root):
res = []
if root:
res = self.inorderTraversal(root.left)
res.append(root.data)
res = res + self.inorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))Quando il codice sopra viene eseguito, produce il seguente risultato:
[10, 14, 19, 27, 31, 35, 42]Preordina Traversal
In questo metodo di attraversamento, viene visitato per primo il nodo radice, quindi la sottostruttura sinistra e infine la sottostruttura destra.
Nel programma python sottostante, usiamo la classe Node per creare segnaposto per il nodo radice e per i nodi sinistro e destro. Quindi creiamo una funzione di inserimento per aggiungere dati all'albero. Infine, la logica di attraversamento del preordine viene implementata creando un elenco vuoto e aggiungendo prima il nodo radice seguito dal nodo sinistro. Alla fine viene aggiunto il nodo destro per completare l'attraversamento del preordine. Notare che questo processo viene ripetuto per ogni sottoalbero finché tutti i nodi non vengono attraversati.
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
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()
# Preorder traversal
# Root -> Left ->Right
def PreorderTraversal(self, root):
res = []
if root:
res.append(root.data)
res = res + self.PreorderTraversal(root.left)
res = res + self.PreorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))Quando il codice sopra viene eseguito, produce il seguente risultato:
[27, 14, 10, 19, 35, 31, 42]Post-order Traversal
In questo metodo di attraversamento, il nodo radice viene visitato per ultimo, da cui il nome. Per prima cosa attraversiamo la sottostruttura sinistra, quindi la sottostruttura destra e infine il nodo radice.
Nel programma python sottostante, usiamo la classe Node per creare segnaposto per il nodo radice e per i nodi sinistro e destro. Quindi creiamo una funzione di inserimento per aggiungere dati all'albero. Infine, la logica di attraversamento post-ordine viene implementata creando un elenco vuoto e aggiungendo prima il nodo sinistro seguito dal nodo destro. Alla fine viene aggiunto il nodo principale o principale per completare l'attraversamento post-ordine. Notare che questo processo viene ripetuto per ogni sottoalbero finché tutti i nodi non vengono attraversati.
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
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()
# Postorder traversal
# Left ->Right -> Root
def PostorderTraversal(self, root):
res = []
if root:
res = self.PostorderTraversal(root.left)
res = res + self.PostorderTraversal(root.right)
res.append(root.data)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))Quando il codice sopra viene eseguito, produce il seguente risultato:
[10, 19, 14, 31, 42, 35, 27]