Egynél több módja van a BST összes csomópontjának meglátogatásának.
A bináris fák az egyik leggyakrabban használt adatstruktúra a programozásban. A bináris keresési fa (BST) lehetővé teszi az adatok csomópontok (szülőcsomópont és gyermek) formájában történő tárolását csomópont) úgy, hogy a bal oldali gyermekcsomópont kisebb, mint a szülőcsomópont, a jobb oldali gyermekcsomópont pedig kisebb nagyobb.
A bináris keresőfák hatékony bejárást, keresést, törlést és beillesztést tesznek lehetővé. Ebből a cikkből megismerheti a bináris keresési fa bejárásának három módját: előrendelési bejárás, inorder bejárás és utólagos bejárás.
Inorder bejárás
Az inorder bejárás a csomópontok bejárásának folyamata bináris keresőfa a bal oldali részfa rekurzív feldolgozásával, majd a gyökércsomópont feldolgozásával, végül pedig a jobb oldali részfa rekurzív feldolgozásával. Mivel a csomópontokat növekvő értékrendben dolgozza fel, ezt a technikát inorder bejárásnak nevezik.
A bejárás az a folyamat, amikor egy fa adatstruktúra minden egyes csomópontját pontosan egyszer látogatják meg.
Az Inorder Bejárás algoritmusa
Ismételje meg a műveletet a BST összes csomópontjának bejárásához:
- Rekurzív bejárás a bal oldali részfán.
- Látogassa meg a gyökér csomópontot.
- Rekurzív bejárás a jobb oldali részfán.
Az Inorder bejárás vizualizálása
Egy vizuális példa segíthet megmagyarázni a bináris keresési fa bejárását. Ez az ábra egy példa bináris keresési fa sorrend szerinti bejárását mutatja:
Ebben a bináris keresési fában az 56 a gyökércsomópont. Először a 32-es bal oldali részfán, majd az 56-os gyökércsomóponton, majd a 62-es jobb oldali részfán kell áthaladnia.
A 32-es részfához először menjen át a 28-as bal oldali részfán. Ennek a részfának nincs gyermeke, ezért a következő lépésben menjen át a 32-es csomóponton. Ezután menjen át a jobb oldali részfán, a 44-es, amelynek szintén nincs gyermeke. Ezért a 32-ben gyökerező részfa bejárási sorrendje 28 -> 32 -> 44.
Ezután keresse fel az 56-os gyökércsomópontot.
Ezután menjen át a jobb oldali részfán, amelynek gyökere 62. Kezdje azzal, hogy bejárja a bal oldali részfát, amelynek gyökere 58. Nincsenek gyermekei, ezért keresse fel a 62-es csomópontot. Végül menjen át a jobb oldali részfán, a 88-ason, amelynek szintén nincs gyermeke.
Tehát az algoritmus a következő sorrendben keresi fel a fa csomópontjait:
28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88
Az Inorder bejárás alkalmazása
Az inorder bejárás segítségével a csomópontelemek értékeit növekvő sorrendben kaphatja meg. Ha az értékeket csökkenő sorrendben szeretné megkapni, egyszerűen fordítsa meg a folyamatot: keresse fel a jobb oldali részfát, majd a gyökércsomópontot, majd a bal oldali részfát. Az algoritmus segítségével megkeresheti egy kifejezésfa prefix kifejezését.
Előrendelési bejárás
Az előrendelési bejárás hasonló az inorderhez, de feldolgozza a gyökércsomópontot, mielőtt rekurzívan feldolgozná a bal oldali részfát, majd a jobb oldali részfát.
Az előrendelési bejárás algoritmusa
Ismételje meg a műveletet a BST összes csomópontjának bejárásához:
- Látogassa meg a gyökér csomópontot.
- Rekurzív bejárás a bal oldali részfán.
- Rekurzív bejárás a jobb oldali részfán.
Előrendelési bejárás megjelenítése
A következő ábra a bináris keresési fa előrendelési bejárását mutatja:
Ebben a bináris keresési fában kezdje az 56 gyökércsomópont feldolgozásával. Ezután menjen át a bal oldali részfán (32), majd a jobb oldali részfán (62).
A bal oldali részfa esetében dolgozza fel a gyökércsomópontban lévő értéket, 32. Ezután menjen át a bal oldali részfán (28), majd végül a jobb oldali részfán (44). Ezzel befejeződik a 32-es gyökerű bal oldali részfa bejárása. A bejárás a következő sorrendben történik: 56 -> 32 -> 28 -> 44.
A jobb oldali részfa esetében dolgozza fel a gyökércsomópontban lévő értéket, a 62-es értéket. Ezután menjen át a bal oldali részfán (58), majd végül a jobb oldali részfán (88). Egyik csomópontnak sincsenek gyermekei, így a bejárás ezen a ponton befejeződött.
A teljes fát a következő sorrendben járta be:
56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88
Előrendelési bejárás alkalmazása
Az előrendelési bejárás segítségével a legegyszerűbben készíthet másolatot a fáról.
Postorder Traversal
Az utólagos bejárás egy bináris keresési fa csomópontjainak rekurzív bejárásának folyamata a bal oldali részfa feldolgozása, majd a jobb oldali részfa rekurzív feldolgozása, végül a feldolgozás gyökércsomópont. Mivel mindkét részfa után a gyökércsomópontot dolgozza fel, ezt a módszert postorder bejárásnak nevezik.
Az utólagos bejárás algoritmusa
Ismételje meg a műveletet a BST összes csomópontjának bejárásához:
- Rekurzív bejárás a bal oldali részfán.
- Rekurzív bejárás a jobb oldali részfán.
- Látogassa meg a gyökér csomópontot.
A Postorder Bejárás vizualizálása
Az alábbi ábra a bináris keresési fa utólagos bejárását mutatja:
Kezdje azzal, hogy bejárja a bal oldali részfát (32), majd a jobb oldali részfát (62). Fejezze be a gyökércsomópont feldolgozásával, 56.
A 32-ben gyökerező részfa feldolgozásához menjen át a bal oldali részfán, a 28-ason. Mivel 28-nak nincs gyereke, lépjen a jobb oldali részfára, a 44-re. 44. folyamat, mivel ennek sincsenek gyermekei. Végül dolgozza fel a gyökércsomópontot, 32. Ezt a részfát 28 -> 44 -> 32 sorrendben járta be.
Ugyanezzel a megközelítéssel dolgozza fel a megfelelő részfát a csomópontok meglátogatásához 58 -> 88 → 62 sorrendben.
Végül dolgozza fel a gyökércsomópontot, 56. A teljes fán a következő sorrendben fog haladni:
28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56
A Postorder Traversal alkalmazása
A postorder bejárás segítségével törölheti a fát a levéltől a gyökérig. Használhatja egy kifejezésfa postfix kifejezésének megkeresésére is.
Egy bizonyos csomópont összes levélcsomópontjának meglátogatásához magát a csomópontot megelőzően használhatja az utólagos bejárási technikát.
A bináris keresőfa bejárásainak idő és tér összetettsége
Mindhárom bejárási technika időbeli összetettsége az Tovább), ahol n a mérete a bináris fa. Az összes bejárási technika térbeli összetettsége az O(h), ahol h a bináris fa magassága.
A bináris fa mérete megegyezik a fában lévő csomópontok számával. A bináris fa magassága a fa gyökércsomópontja és a legtávolabbi levélcsomópont közötti élek száma.
Python kód a bináris keresőfa bejárásához
Az alábbiakban egy Python program található mindhárom bináris keresési fa bejárásának végrehajtására:
# 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)
Ennek a programnak a következő kimenetet kell produkálnia:
Kötelező algoritmusok programozók számára
Az algoritmusok minden programozó utazásának elengedhetetlen részét képezik. A programozó számára kulcsfontosságú, hogy jól ismerje az algoritmusokat. Ismernie kell néhány olyan algoritmust, mint az egyesítési rendezés, a gyors rendezés, a bináris keresés, a lineáris keresés, a mélységi keresés és így tovább.