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.

instagram viewer

Az Inorder Bejárás algoritmusa

Ismételje meg a műveletet a BST összes csomópontjának bejárásához:

  1. Rekurzív bejárás a bal oldali részfán.
  2. Látogassa meg a gyökér csomópontot.
  3. 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:

  1. Látogassa meg a gyökér csomópontot.
  2. Rekurzív bejárás a bal oldali részfán.
  3. 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:

  1. Rekurzív bejárás a bal oldali részfán.
  2. Rekurzív bejárás a jobb oldali részfán.
  3. 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.