C'è più di un modo per visitare tutti i nodi in un BST.
Gli alberi binari sono una delle strutture dati più utilizzate nella programmazione. Un albero di ricerca binario (BST) consente l'archiviazione dei dati sotto forma di nodi (nodo padre e nodo figlio nodo) in modo tale che il nodo figlio sinistro sia più piccolo del nodo genitore e il nodo figlio destro lo sia maggiore.
Gli alberi di ricerca binari consentono operazioni di attraversamento, ricerca, cancellazione e inserimento efficienti. In questo articolo imparerai i tre modi per attraversare un albero di ricerca binario: attraversamento in preordine, attraversamento in ordine e attraversamento in ordine successivo.
Attraversamento in ordine
L'attraversamento in ordine è il processo di attraversamento dei nodi di a albero di ricerca binario elaborando in modo ricorsivo il sottoalbero sinistro, quindi elaborando il nodo radice e infine elaborando in modo ricorsivo il sottoalbero destro. Poiché elabora i nodi in ordine di valore crescente, la tecnica è chiamata inorder traversal.
L'attraversamento è il processo di visitare ogni nodo in una struttura dati ad albero esattamente una volta.
Algoritmo di attraversamento in ordine
Ripeti per attraversare tutti i nodi del BST:
- Attraversa in modo ricorsivo il sottoalbero sinistro.
- Visita il nodo radice.
- Attraversa in modo ricorsivo il sottoalbero destro.
Visualizzazione dell'attraversamento in ordine
Un esempio visivo può aiutare a spiegare l'attraversamento dell'albero di ricerca binario. Questa figura mostra l'attraversamento in ordine di un albero di ricerca binario di esempio:
In questo albero di ricerca binario, 56 è il nodo radice. Innanzitutto, devi attraversare il sottoalbero sinistro 32, quindi il nodo radice 56 e quindi il sottoalbero destro 62.
Per il sottoalbero 32, prima attraversa il sottoalbero sinistro, 28. Questo sottoalbero non ha figli, quindi attraversa il nodo 32. Successivamente, attraversa il sottoalbero destro, 44, che non ha figli. Pertanto l'ordine di attraversamento per il sottoalbero con radice in 32 è 28 -> 32 -> 44.
Successivamente, visita il nodo radice, 56.
Quindi, attraversa il sottoalbero destro, radicato a 62. Inizia attraversando il suo sottoalbero sinistro, radicato a 58. Non ha figli, quindi visita il nodo 62 successivo. Infine, attraversa il sottoalbero di destra, 88, anch'esso privo di figli.
Quindi l'algoritmo visita i nodi dell'albero nel seguente ordine:
28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88
Applicazione dell'attraversamento in ordine
È possibile utilizzare l'attraversamento in ordine per ottenere i valori degli elementi del nodo in ordine crescente. Per ottenere i valori in ordine decrescente, è sufficiente invertire il processo: visitare il sottoalbero di destra, quindi il nodo radice, quindi il sottoalbero di sinistra. È possibile utilizzare l'algoritmo per trovare l'espressione del prefisso di un albero delle espressioni.
Preordina l'attraversamento
L'attraversamento in preordine è simile a inorder, ma elabora il nodo radice prima di elaborare in modo ricorsivo il sottoalbero sinistro, quindi il sottoalbero destro.
Algoritmo di Preorder Traversal
Ripeti per attraversare tutti i nodi del BST:
- Visita il nodo radice.
- Attraversa in modo ricorsivo il sottoalbero sinistro.
- Attraversa in modo ricorsivo il sottoalbero destro.
Visualizzazione del Preorder Traversal
La figura seguente mostra l'attraversamento del preordine dell'albero di ricerca binario:
In questo albero di ricerca binario, inizia elaborando il nodo radice, 56. Quindi attraversa il sottoalbero sinistro, 32, seguito dal sottoalbero destro, 62.
Per il sottoalbero sinistro, elabora il valore nel nodo radice, 32. Successivamente, attraversa il sottoalbero sinistro, 28, quindi infine il sottoalbero destro, 44. Questo completa l'attraversamento del sottoalbero sinistro radicato in 32. L'attraversamento avviene nel seguente ordine: 56 -> 32 -> 28 -> 44.
Per il sottoalbero di destra, elabora il valore nel nodo radice, 62. Successivamente, attraversa il sottoalbero sinistro, 58, quindi infine il sottoalbero destro, 88. Ancora una volta, nessuno dei nodi ha figli, quindi l'attraversamento è completo a questo punto.
Hai attraversato l'intero albero nel seguente ordine:
56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88
Applicazione di Preorder Traversal
È possibile utilizzare l'attraversamento del preordine per creare più facilmente una copia dell'albero.
Postorder attraversamento
L'attraversamento in postordine è il processo di attraversamento dei nodi di un albero di ricerca binario in modo ricorsivo elaborando il sottoalbero sinistro, quindi elaborando in modo ricorsivo il sottoalbero destro e infine elaborando il file nodo radice. Poiché elabora il nodo radice dopo entrambi i sottoalberi, questo metodo è chiamato postorder traversal.
Algoritmo di Postorder Traversal
Ripeti per attraversare tutti i nodi del BST:
- Attraversa in modo ricorsivo il sottoalbero sinistro.
- Attraversa in modo ricorsivo il sottoalbero destro.
- Visita il nodo radice.
Visualizzazione di Postorder Traversal
La figura seguente mostra l'attraversamento in postordine dell'albero di ricerca binario:
Inizia attraversando il sottoalbero sinistro, 32, quindi il sottoalbero destro, 62. Termina elaborando il nodo radice, 56.
Per elaborare il sottoalbero, radicato in 32, attraversa il suo sottoalbero sinistro, 28. Poiché 28 non ha figli, spostati nel sottoalbero di destra, 44. Processo 44 poiché non ha figli. Infine, elabora il nodo radice, 32. Hai attraversato questo sottoalbero nell'ordine 28 -> 44 -> 32.
Elabora la sottostruttura corretta utilizzando lo stesso approccio per visitare i nodi nell'ordine 58 -> 88 → 62.
Infine, elabora il nodo radice, 56. Attraverserai l'intero albero in questo ordine:
28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56
Applicazione di Postorder Traversal
È possibile utilizzare l'attraversamento postordine per eliminare un albero dalla foglia alla radice. Puoi anche usarlo per trovare l'espressione postfissa di un albero delle espressioni.
Per visitare tutti i nodi foglia di un certo nodo prima di visitare il nodo stesso, puoi utilizzare la tecnica del postorder traversal.
Complessità spazio-temporale degli attraversamenti dell'albero di ricerca binaria
La complessità temporale di tutte e tre le tecniche di attraversamento è SU), Dove N è la dimensione del albero binario. La complessità spaziale di tutte le tecniche di attraversamento è OH), Dove H è l'altezza dell'albero binario.
La dimensione dell'albero binario è uguale al numero di nodi in quell'albero. L'altezza dell'albero binario è il numero di spigoli tra il nodo radice dell'albero e il suo nodo foglia più lontano.
Codice Python per l'attraversamento dell'albero di ricerca binaria
Di seguito è riportato un programma Python per eseguire tutti e tre gli attraversamenti dell'albero di ricerca binario:
# Node class is used to create individual nodes
# of the Binary Search Tree (BST)
classNode:
def__init__(self, element):
self.left = None
self.right = None
self.value = element# Function to perform the inorder tree traversal
definorder(root):
if root:
# Traverse left subtree
inorder(root.left)# Traverse root
print(str(root.value) + ", ", end='')# Traverse right subtree
inorder(root.right)# Function to perform the postorder tree traversal
defpostorder(root):
if root:
# Traverse left subtree
postorder(root.left)# Traverse right subtree
postorder(root.right)# Traverse root
print(str(root.value) + ", ", end='')# Function to perform the preorder tree traversal
defpreorder(root):
if root:
# Traverse root
print(str(root.value) + ", ", end='')# Traverse left subtree
preorder(root.left)# Traverse right subtree
preorder(root.right)
# Creating nodes of the tree
root = Node(56)
root.left = Node(32)
root.right = Node(62)
root.left.left = Node(28)
root.left.right = Node(44)
root.right.left = Node(58)
root.right.right = Node(88)
print("Inorder Traversal of BST: ")
inorder(root)
print()
print("Preorder Traversal of BST: ")
preorder(root)
print()
print("Postorder Traversal of BST: ")
postorder(root)
Questo programma dovrebbe produrre il seguente output:
Algoritmi indispensabili per i programmatori
Gli algoritmi sono una parte essenziale del viaggio di ogni programmatore. È fondamentale per un programmatore essere esperto di algoritmi. Dovresti avere familiarità con alcuni degli algoritmi come merge sort, quick sort, ricerca binaria, ricerca lineare, ricerca in profondità e così via.