Existuje viac ako jeden spôsob, ako navštíviť všetky uzly v BST.

Binárne stromy sú jednou z najpoužívanejších dátových štruktúr v programovaní. Binárny vyhľadávací strom (BST) umožňuje ukladanie údajov vo forme uzlov (nadradený uzol a podriadený uzol uzol) tak, že ľavý podriadený uzol je menší ako nadradený uzol a pravý podriadený uzol je väčší.

Binárne vyhľadávacie stromy umožňujú efektívne prechádzanie, vyhľadávanie, mazanie a vkladanie. V tomto článku sa dozviete o troch spôsoboch, ako prejsť binárnym vyhľadávacím stromom: prechod pred objednávkami, prechod mimo poradia a prechod postorder.

Inorder Traversal

Neriadený prechod je proces prechodu uzlov a binárny vyhľadávací strom rekurzívnym spracovaním ľavého podstromu, potom spracovaním koreňového uzla a nakoniec rekurzívnym spracovaním pravého podstromu. Keďže spracováva uzly vo vzostupnom poradí hodnôt, táto technika sa nazýva prechod v poradí.

Prechádzanie je proces návštevy každého uzla v stromovej dátovej štruktúre presne raz.

Algoritmus prechodu inorderov

instagram viewer

Opakujte, aby ste prešli všetkými uzlami BST:

  1. Rekurzívne prejdite ľavým podstromom.
  2. Navštívte koreňový uzol.
  3. Rekurzívne prejdite pravým podstromom.

Vizualizácia Inorder Traversal

Vizuálny príklad môže pomôcť vysvetliť prechod binárneho vyhľadávacieho stromu. Tento obrázok ukazuje prechod v poradí príkladu binárneho vyhľadávacieho stromu:

V tomto binárnom vyhľadávacom strome je 56 koreňový uzol. Najprv musíte prejsť ľavý podstrom 32, potom koreňový uzol 56 a potom pravý podstrom 62.

Pre podstrom 32 najprv prejdite ľavým podstromom 28. Tento podstrom nemá žiadne potomky, takže ďalej prejdite cez uzol 32. Ďalej prejdite pravým podstromom 44, ktorý tiež nemá žiadne deti. Preto poradie prechodu pre podstrom zakorenený na 32 je 28 -> 32 -> 44.

Ďalej navštívte koreňový uzol, 56.

Potom prejdite pravým podstromom s koreňom na 62. Začnite prechádzaním jeho ľavého podstromu s koreňom na 58. Nemá žiadne deti, takže navštívte uzol 62. Nakoniec prejdite pravým podstromom 88, ktorý tiež nemá žiadne deti.

Algoritmus teda navštívi uzly stromu v nasledujúcom poradí:

28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88

Aplikácia Inorder Traversal

Pomocou inorder traversal môžete získať hodnoty prvkov uzla v rastúcom poradí. Ak chcete získať hodnoty v zostupnom poradí, jednoducho obráťte proces: navštívte pravý podstrom, potom koreňový uzol a potom ľavý podstrom. Algoritmus môžete použiť na nájdenie predpony výrazu stromu výrazov.

Preorder Traversal

Prechod predobjednávky je podobný ako inorder, ale spracováva koreňový uzol pred rekurzívnym spracovaním ľavého podstromu a potom pravého podstromu.

Algoritmus prechodu predobjednávky

Opakujte, aby ste prešli všetkými uzlami BST:

  1. Navštívte koreňový uzol.
  2. Rekurzívne prejdite ľavým podstromom.
  3. Rekurzívne prejdite pravým podstromom.

Vizualizácia prechodu predobjednávky

Nasledujúci obrázok ukazuje prechod predobjednávky binárneho vyhľadávacieho stromu:

V tomto binárnom vyhľadávacom strome začnite spracovaním koreňového uzla, 56. Potom prejdite ľavým podstromom 32, po ktorom nasleduje pravý podstrom 62.

Pre ľavý podstrom spracujte hodnotu v koreňovom uzle, 32. Ďalej prejdite ľavým podstromom 28 a nakoniec pravým podstromom 44. Tým sa dokončí prechod ľavého podstromu zakoreneného na 32. Prechod prebieha v nasledujúcom poradí: 56 -> 32 -> 28 -> 44.

Pre pravý podstrom spracujte hodnotu v koreňovom uzle, 62. Ďalej prejdite ľavým podstromom, 58, potom nakoniec pravým podstromom, 88. Ani jeden uzol opäť nemá žiadne potomky, takže prechod je v tomto bode dokončený.

Prešli ste celý strom v nasledujúcom poradí:

56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88

Aplikácia Preorder Traversal

Na najjednoduchšie vytvorenie kópie stromu môžete použiť prechod predobjednávky.

Postorder Traversal

Postorder traversal je proces prechádzania uzlov binárneho vyhľadávacieho stromu rekurzívne spracovanie ľavého podstromu, potom rekurzívne spracovanie pravého podstromu a nakoniec spracovanie koreňový uzol. Keďže spracováva koreňový uzol po oboch podstromoch, táto metóda sa nazýva postorder traversal.

Algoritmus Postorder Traversal

Opakujte, aby ste prešli všetkými uzlami BST:

  1. Rekurzívne prejdite ľavým podstromom.
  2. Rekurzívne prejdite pravým podstromom.
  3. Navštívte koreňový uzol.

Vizualizácia Postorder Traversal

Nasledujúci obrázok znázorňuje prechod binárneho vyhľadávacieho stromu postorderom:

Začnite prechádzaním ľavého podstromu, 32, potom pravého podstromu, 62. Dokončite spracovaním koreňového uzla, 56.

Ak chcete spracovať podstrom, zakorenený na 32, prejdite jeho ľavým podstromom 28. Keďže 28 nemá žiadne deti, presuňte sa do správneho podstromu, 44. Proces 44, pretože tiež nemá žiadne deti. Nakoniec spracujte koreňový uzol, 32. Tento podstrom ste prešli v poradí 28 -> 44 -> 32.

Spracujte pravý podstrom pomocou rovnakého prístupu na návštevu uzlov v poradí 58 -> 88 → 62.

Nakoniec spracujte koreňový uzol, 56. Celý strom prejdete v tomto poradí:

28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56

Aplikácia Postorder Traversal

Môžete použiť postorder traversal na odstránenie stromu z listu na koreň. Môžete ho použiť aj na nájdenie postfixového výrazu stromu výrazov.

Ak chcete navštíviť všetky listové uzly určitého uzla pred návštevou samotného uzla, môžete použiť techniku ​​postorder traversal.

Časová a priestorová zložitosť prechodov binárnych vyhľadávacích stromov

Časová náročnosť všetkých troch traverzových techník je O(n), kde n je veľkosť binárny strom. Priestorová zložitosť všetkých techník prechodu je O(h), kde h je výška binárneho stromu.

Veľkosť binárneho stromu sa rovná počtu uzlov v tomto strome. Výška binárneho stromu je počet hrán medzi koreňovým uzlom stromu a jeho najvzdialenejším listovým uzlom.

Kód Python pre prechod binárneho vyhľadávacieho stromu

Nižšie je uvedený program Python na vykonanie všetkých troch prechodov binárneho vyhľadávacieho stromu:

# 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)

Tento program by mal produkovať nasledujúci výstup:

Programátori musia poznať algoritmy

Algoritmy sú nevyhnutnou súčasťou cesty každého programátora. Pre programátora je dôležité dobre sa orientovať v algoritmoch. Mali by ste byť oboznámení s niektorými z algoritmov, ako je zlučovacie triedenie, rýchle triedenie, binárne vyhľadávanie, lineárne vyhľadávanie, hĺbkové prvé vyhľadávanie atď.