Obstaja več kot en način za obisk vseh vozlišč v BST.
Binarna drevesa so ena najpogosteje uporabljenih podatkovnih struktur v programiranju. Binarno iskalno drevo (BST) omogoča shranjevanje podatkov v obliki vozlišč (nadrejeno vozlišče in podrejeno vozlišče). vozlišče), tako da je levo podrejeno vozlišče manjše od nadrejenega vozlišča in desno podrejeno vozlišče večji.
Binarna iskalna drevesa omogočajo učinkovite operacije prečkanja, iskanja, brisanja in vstavljanja. V tem članku boste izvedeli o treh načinih prečkanja binarnega iskalnega drevesa: prečkanje pred vrstnim redom, prečkanje po vrstnem redu in prečkanje po vrstnem redu.
Prehod po vrstnem redu
Neurejeno prečkanje je proces prečkanja vozlišč a binarno iskalno drevo z rekurzivno obdelavo levega poddrevesa, nato obdelavo korenskega vozlišča in na koncu rekurzivno obdelavo desnega poddrevesa. Ker obdeluje vozlišča v naraščajočem vrstnem redu vrednosti, se tehnika imenuje prečkanje po vrstnem redu.
Prehod je postopek obiska vsakega vozlišča v drevesni podatkovni strukturi natanko enkrat.
Algoritem prečkanja po vrstnem redu
Ponovite, da prečkate vsa vozlišča BST:
- Rekurzivno prečkaj levo poddrevo.
- Obiščite korensko vozlišče.
- Rekurzivno prečkaj desno poddrevo.
Vizualizacija prečkanja vrstnega reda
Vizualni primer lahko pomaga razložiti prečkanje binarnega iskalnega drevesa. Ta slika prikazuje prečkanje po vrstnem redu primera binarnega iskalnega drevesa:
V tem binarnem iskalnem drevesu je 56 korensko vozlišče. Najprej morate prečkati levo poddrevo 32, nato korensko vozlišče 56 in nato desno poddrevo 62.
Za poddrevo 32 najprej prečkajte levo poddrevo, 28. To poddrevo nima podrejenih elementov, zato nato prečkajte vozlišče 32. Nato prečkajte desno poddrevo, 44, ki prav tako nima otrok. Zato je vrstni red prečkanja za poddrevo, zakoreninjeno na 32, 28 -> 32 -> 44.
Nato obiščite korensko vozlišče, 56.
Nato prečkajte desno poddrevo, zakoreninjeno na 62. Začnite s prečkanjem njegovega levega poddrevesa, zakoreninjenega na 58. Nima otrok, zato obiščite vozlišče 62. Končno prečkajte desno poddrevo, 88, ki prav tako nima otrok.
Torej algoritem obišče vozlišča drevesa v naslednjem vrstnem redu:
28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88
Uporaba Inorder Traversal
Za pridobitev vrednosti elementov vozlišča v naraščajočem vrstnem redu lahko uporabite prečkanje po vrstnem redu. Če želite vrednosti dobiti v padajočem vrstnem redu, preprosto obrnite postopek: obiščite desno poddrevo, nato korensko vozlišče in nato levo poddrevo. Algoritem lahko uporabite za iskanje predponskega izraza izraznega drevesa.
Prehod pred naročilom
Prehod pred vrstnim redom je podoben vrstnemu redu, vendar obdela korensko vozlišče, preden rekurzivno obdela levo poddrevo in nato desno poddrevo.
Algoritem prečkanja prednaročila
Ponovite, da prečkate vsa vozlišča BST:
- Obiščite korensko vozlišče.
- Rekurzivno prečkaj levo poddrevo.
- Rekurzivno prečkaj desno poddrevo.
Vizualizacija prečkanja prednaročila
Naslednja slika prikazuje prehod pred naročilom binarnega iskalnega drevesa:
V tem binarnem iskalnem drevesu začnite z obdelavo korenskega vozlišča, 56. Nato prečkajte levo poddrevo, 32, ki mu sledi desno poddrevo, 62.
Za levo poddrevo obdelajte vrednost v korenskem vozlišču, 32. Nato prečkajte levo poddrevo, 28, nato pa končno desno poddrevo, 44. S tem se zaključi prečkanje levega poddrevesa s koreninami 32. Prehod poteka v naslednjem vrstnem redu: 56 -> 32 -> 28 -> 44.
Za desno poddrevo obdelajte vrednost v korenskem vozlišču, 62. Nato prečkajte levo poddrevo, 58, nato pa končno desno poddrevo, 88. Ponovno, nobeno vozlišče nima otrok, tako da je prečkanje na tej točki končano.
Prehodili ste celotno drevo v naslednjem vrstnem redu:
56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88
Uporaba prednaročila Traversal
Za najlažje ustvarjanje kopije drevesa lahko uporabite prehod pred naročilom.
Prehod po naročilu
Prehod po naročilu je postopek rekurzivnega prečkanja vozlišč binarnega iskalnega drevesa obdelava levega poddrevesa, nato rekurzivna obdelava desnega poddrevesa in končno obdelava korensko vozlišče. Ker obdeluje korensko vozlišče za obema poddrevesoma, se ta metoda imenuje postorder traversal.
Algoritem prehoda po naročilu
Ponovite, da prečkate vsa vozlišča BST:
- Rekurzivno prečkaj levo poddrevo.
- Rekurzivno prečkaj desno poddrevo.
- Obiščite korensko vozlišče.
Vizualizacija prehoda po naročilu
Naslednja slika prikazuje prehod po naročilu binarnega iskalnega drevesa:
Začnite s prečkanjem levega poddrevesa, 32, nato desnega poddrevesa, 62. Končajte z obdelavo korenskega vozlišča, 56.
Če želite obdelati poddrevo, zakoreninjeno na 32, prečkajte njegovo levo poddrevo, 28. Ker 28 nima otrok, se premaknite na desno poddrevo, 44. Proces 44, saj prav tako nima otrok. Na koncu obdelajte korensko vozlišče, 32. To poddrevo ste prečkali v vrstnem redu 28 -> 44 -> 32.
Obdelajte desno poddrevo z enakim pristopom za obisk vozlišč v vrstnem redu 58 -> 88 → 62.
Na koncu obdelajte korensko vozlišče, 56. Celotno drevo boste prečkali v tem vrstnem redu:
28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56
Uporaba Postorder Traversal
Za brisanje drevesa od listov do korenin lahko uporabite postorder traversal. Uporabite ga lahko tudi za iskanje postfiksnega izraza izraznega drevesa.
Če želite obiskati vsa listna vozlišča določenega vozlišča, preden obiščete samo vozlišče, lahko uporabite tehniko prehoda po naročilu.
Časovna in prostorska kompleksnost prehodov binarnega iskalnega drevesa
Časovna zahtevnost vseh treh tehnik prečkanja je O(n), kje n je velikost binarno drevo. Prostorska kompleksnost vseh tehnik prečkanja je O(h), kje h je višina binarnega drevesa.
Velikost binarnega drevesa je enaka številu vozlišč v tem drevesu. Višina binarnega drevesa je število robov med korenskim vozliščem drevesa in njegovim najbolj oddaljenim listnim vozliščem.
Koda Python za binarno iskanje po drevesu
Spodaj je program Python za izvajanje vseh treh binarnih iskalnih prehodov drevesa:
# 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)
Ta program bi moral dati naslednje rezultate:
Algoritmi, ki jih morajo poznati programerji
Algoritmi so bistveni del poti vsakega programerja. Za programerja je ključno, da dobro pozna algoritme. Morali bi poznati nekatere algoritme, kot so razvrščanje z združitvijo, hitro razvrščanje, binarno iskanje, linearno iskanje, iskanje najprej v globino itd.
