Postoji više od jednog načina za posjet svim čvorovima u BST-u.
Binarna stabla jedna su od najčešće korištenih struktura podataka u programiranju. Binarno stablo pretraživanja (BST) omogućuje pohranjivanje podataka u obliku čvorova (roditeljski čvor i podređeni čvor čvor) tako da je lijevi podređeni čvor manji od roditeljskog čvora, a desni podređeni čvor je veća.
Binarna stabla pretraživanja omogućuju učinkovite operacije obilaska, pretraživanja, brisanja i umetanja. U ovom ćete članku naučiti o tri načina obilaska binarnog stabla pretraživanja: obilaženje unaprijed, obilaženje po redu i obilaženje nakon reda.
Inorder Traversal
Inorder traversal je proces obilaženja čvorova a binarno stablo pretraživanja rekurzivnom obradom lijevog podstabla, zatim obradom korijenskog čvora i konačno rekurzivnom obradom desnog podstabla. Budući da obrađuje čvorove uzlaznim redoslijedom vrijednosti, tehnika se naziva obilaskom po redoslijedu.
Putovanje je proces posjećivanja svakog čvora u podatkovnoj strukturi stabla točno jednom.
Algoritam obilaska po redoslijedu
Ponovite za prelazak svih čvorova BST-a:
- Rekurzivno prijeći lijevo podstablo.
- Posjetite korijenski čvor.
- Rekurzivno prijeći desno podstablo.
Vizualizacija obilaska po neredu
Vizualni primjer može pomoći u objašnjenju obilaska stabla binarnog pretraživanja. Ova slika prikazuje obilazak po redoslijedu primjera stabla binarnog pretraživanja:
U ovom stablu binarnog pretraživanja, 56 je korijenski čvor. Najprije morate prijeći lijevo podstablo 32, zatim korijenski čvor 56, a zatim desno podstablo 62.
Za podstablo 32, prvo prijeđite lijevo podstablo, 28. Ovo podstablo nema djece, pa sljedeći put prijeđite preko 32 čvora. Zatim prijeđite desnim podstablom, 44, koje također nema djece. Stoga je redoslijed obilaska za podstablo ukorijenjeno na 32 28 -> 32 -> 44.
Zatim posjetite korijenski čvor, 56.
Zatim prijeđite desnim podstablom, ukorijenjenim na 62. Počnite tako što ćete prijeći lijevo podstablo, ukorijenjeno na 58. Nema djece, pa posjetite 62 čvor sljedeći. Na kraju, prijeđite desnim podstablom, 88, koje također nema djece.
Dakle, algoritam posjećuje čvorove stabla sljedećim redoslijedom:
28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88
Primjena Inorder Traversal
Možete koristiti obilazak po redoslijedu da biste dobili vrijednosti elemenata čvora u rastućem redoslijedu. Da biste dobili vrijednosti u opadajućem redoslijedu, jednostavno obrnite postupak: posjetite desno podstablo, zatim korijenski čvor, zatim lijevo podstablo. Možete koristiti algoritam za pronalaženje prefiksnog izraza stabla izraza.
Prolaz prednarudžbe
Prolaz prednarudžbe sličan je obilasku po redoslijedu, ali obrađuje korijenski čvor prije rekurzivne obrade lijevog podstabla, a zatim desnog podstabla.
Algoritam obilaska prednarudžbi
Ponovite za prelazak svih čvorova BST-a:
- Posjetite korijenski čvor.
- Rekurzivno prijeći lijevo podstablo.
- Rekurzivno prijeći desno podstablo.
Vizualizacija obilaska prednarudžbi
Sljedeća slika prikazuje obilazak prednarudžbe stabla binarnog pretraživanja:
U ovom stablu binarnog pretraživanja počnite s obradom korijenskog čvora, 56. Zatim prijeđite lijevo podstablo, 32, a zatim desno podstablo, 62.
Za lijevo podstablo, obradite vrijednost u korijenskom čvoru, 32. Zatim prijeđite lijevo podstablo, 28, zatim konačno desno podstablo, 44. Ovo dovršava obilazak lijevog podstabla ukorijenjenog na 32. Prolazak se odvija sljedećim redoslijedom: 56 -> 32 -> 28 -> 44.
Za desno podstablo, obradite vrijednost u korijenskom čvoru, 62. Zatim prijeđite lijevo podstablo, 58, zatim konačno desno podstablo, 88. Opet, niti jedan čvor nema djecu, tako da je obilazak dovršen u ovom trenutku.
Prešli ste cijelo stablo sljedećim redoslijedom:
56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88
Primjena Preorder Traversal
Za najlakšu izradu kopije stabla možete upotrijebiti prolazak unaprijed.
Postorder Traversal
Postorder traversal je proces rekurzivnog obilaženja čvorova stabla binarnog pretraživanja obrada lijevog podstabla, zatim rekurzivna obrada desnog podstabla i na kraju obrada korijenski čvor. Budući da obrađuje korijenski čvor nakon oba podstabla, ova se metoda naziva postorder traversal.
Algoritam postorder traversal
Ponovite za prelazak svih čvorova BST-a:
- Rekurzivno prijeći lijevo podstablo.
- Rekurzivno prijeći desno podstablo.
- Posjetite korijenski čvor.
Vizualizacija postorder traversal
Sljedeća slika prikazuje postorder obilaženje stabla binarnog pretraživanja:
Počnite tako što ćete prijeći lijevo podstablo, 32, zatim desno podstablo, 62. Završite obradom korijenskog čvora, 56.
Da biste obradili podstablo, ukorijenjeno na 32, prijeđite preko njegovog lijevog podstabla, 28. Budući da 28 nema djece, pomaknite se na desno podstablo, 44. Proces 44 jer također nema djece. Na kraju, obradite korijenski čvor, 32. Prešli ste ovo podstablo redoslijedom 28 -> 44 -> 32.
Obradite desno podstablo koristeći isti pristup za posjet čvorovima u redoslijedu 58 -> 88 → 62.
Na kraju, obradite korijenski čvor, 56. Preći ćete cijelo stablo ovim redoslijedom:
28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56
Primjena Postorder Traversal
Možete koristiti postorder traversal za brisanje stabla od lista do korijena. Također ga možete koristiti za pronalaženje postfiksnog izraza stabla izraza.
Za posjet svim lisnim čvorovima određenog čvora prije posjeta samom čvoru, možete upotrijebiti tehniku postorder traversal.
Vremenska i prostorna složenost obilaska stabla binarnog pretraživanja
Vremenska složenost sve tri tehnike obilaska je Na), gdje n je veličina binarno stablo. Prostorna složenost svih tehnika obilaska je Oh), gdje h je visina binarnog stabla.
Veličina binarnog stabla jednaka je broju čvorova u tom stablu. Visina binarnog stabla je broj bridova između korijenskog čvora stabla i njegovog najudaljenijeg lisnog čvora.
Python kod za obilazak stabla binarnog pretraživanja
Ispod je Python program za izvođenje sva tri obilaska stabla binarnog pretraživanja:
# 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)
Ovaj bi program trebao proizvesti sljedeće rezultate:
Algoritmi koje programeri moraju znati
Algoritmi su bitan dio putovanja svakog programera. Ključno je da programer dobro poznaje algoritme. Trebali biste biti upoznati s nekim algoritmima kao što je sortiranje spajanjem, brzo sortiranje, binarno pretraživanje, linearno pretraživanje, prvo pretraživanje u dubinu i tako dalje.
