On olemassa useampi kuin yksi tapa vierailla kaikissa BST: n solmuissa.

Binääripuut ovat yksi ohjelmoinnin eniten käytetyistä tietorakenteista. Binäärihakupuu (BST) mahdollistaa tietojen tallentamisen solmujen muodossa (emosolmu ja lapsi solmu) siten, että vasen lapsisolmu on pienempi kuin pääsolmu ja oikea lapsisolmu on suurempi.

Binäärihakupuut mahdollistavat tehokkaat läpikulku-, haku-, poisto- ja lisäystoiminnot. Tässä artikkelissa opit kolmesta tavasta kulkea binäärihakupuun läpi: ennakkotilaus, tilausläpikulku ja postorder traversal.

Inorder Traversal

Inorder-läpikulku on prosessi a: n solmujen läpikulkua varten binäärihakupuu käsittelemällä rekursiivisesti vasenta alipuuta, sitten käsittelemällä juurisolmua ja lopuksi käsittelemällä rekursiivisesti oikeanpuoleista alipuuta. Koska se käsittelee solmut nousevassa arvojärjestyksessä, tekniikkaa kutsutaan inorder traversaliksi.

Traversing on prosessi, jossa käydään jokaisessa puutietorakenteen solmussa täsmälleen kerran.

Inorder Traversal -algoritmi

instagram viewer

Toista BST: n kaikkien solmujen läpikulku:

  1. Rekursiivisesti vasemman alipuun poikki.
  2. Vieraile juurisolmussa.
  3. Kierrä rekursiivisesti oikeanpuoleisen alipuun läpi.

Inorder Traversalin visualisointi

Visuaalinen esimerkki voi auttaa selittämään binäärihakupuun läpikulkua. Tämä kuva esittää esimerkin binaarihakupuun järjestyksen läpikulkua:

Tässä binäärihakupuussa 56 on juurisolmu. Ensin sinun täytyy kulkea vasen alipuu 32, sitten juurisolmu 56 ja sitten oikea alipuu 62.

Alipuun 32 kohdalla aja ensin vasemman alipuun 28 poikki. Tällä alipuulla ei ole lapsia, joten kulje seuraavaksi 32-solmun läpi. Siirry seuraavaksi oikeanpuoleisen alipuun 44 läpi, jolla ei myöskään ole lapsia. Siksi alipuun läpikulkujärjestys, jonka juuret ovat 32, on 28 -> 32 -> 44.

Vieraile seuraavaksi juurisolmussa 56.

Siirry sitten oikeanpuoleisen alipuun läpi, jonka juuret ovat 62. Aloita kulkemalla sen vasen alipuu, jonka juuret ovat 58. Sillä ei ole lapsia, joten käy seuraavaksi 62-solmussa. Lopuksi poikki oikeanpuoleinen alipuu, 88, jolla ei myöskään ole lapsia.

Joten algoritmi vierailee puun solmuissa seuraavassa järjestyksessä:

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

Inorder Traversalin soveltaminen

Voit käyttää inorder traversalia saadaksesi solmuelementtien arvot kasvavassa järjestyksessä. Jos haluat saada arvot laskevassa järjestyksessä, käännä prosessi päinvastaiseksi: käy oikeanpuoleisessa alipuussa, sitten juurisolmussa ja sitten vasemmassa alipuussa. Algoritmin avulla voit etsiä lausekepuun etuliitelausekkeen.

Ennakkotilaa Traversal

Ennakkotilauksen läpikäyminen on samanlainen kuin inorder, mutta se käsittelee juurisolmun ennen kuin käsittelee rekursiivisesti vasemman alipuun ja sitten oikean alipuun.

Ennakkotilauksen läpikäymisen algoritmi

Toista BST: n kaikkien solmujen läpikulku:

  1. Vieraile juurisolmussa.
  2. Rekursiivisesti vasemman alipuun poikki.
  3. Kierrä rekursiivisesti oikeanpuoleisen alipuun läpi.

Ennakkotilauksen läpikäymisen visualisointi

Seuraava kuva esittää binaarihakupuun ennakkotilauksen läpikulkua:

Aloita tässä binäärihakupuussa käsittelemällä juurisolmu 56. Siirrä sitten vasen alipuu 32, jota seuraa oikea alipuu, 62.

Käsittele vasemman alipuun arvo juurisolmussa 32. Kierrä seuraavaksi vasen alipuu 28 ja lopuksi oikea alipuu 44. Tämä viimeistelee vasemman alipuun läpikäynnin, jonka juuret ovat 32. Läpikulku tapahtuu seuraavassa järjestyksessä: 56 -> 32 -> 28 -> 44.

Oikean alipuun kohdalla käsittele arvo juurisolmussa 62. Kierrä seuraavaksi vasen alipuu 58 ja lopuksi oikea alipuu 88. Jälleen kummallakaan solmulla ei ole lapsia, joten läpikulku on valmis tässä vaiheessa.

Olet kulkenut koko puun läpi seuraavassa järjestyksessä:

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

Ennakkotilauksen läpikäymisen soveltaminen

Ennakkotilauksen kautta voit luoda kopion puusta helpoimmin.

Postorder Traversal

Postorder traversal on prosessi, jossa binäärihakupuun solmut kulkevat rekursiivisesti prosessoimalla vasemman alipuun, käsittelemällä sitten rekursiivisesti oikean alipuun ja lopuksi käsittelemällä alipuuta juurisolmu. Koska se käsittelee juurisolmun molempien alipuiden jälkeen, tätä menetelmää kutsutaan postorder traversaliksi.

Postorder Traversal -algoritmi

Toista BST: n kaikkien solmujen läpikulku:

  1. Rekursiivisesti vasemman alipuun poikki.
  2. Kierrä rekursiivisesti oikeanpuoleisen alipuun läpi.
  3. Vieraile juurisolmussa.

Postorder Traversalin visualisointi

Seuraava kuva esittää binaarihakupuun postorder-läpikulkua:

Aloita kulkemalla vasen alipuu 32 ja sitten oikea alipuu 62. Viimeistele käsittelemällä juurisolmu, 56.

Käsittele alipuu, jonka juuret ovat 32, kulkemalla sen vasemman alipuun 28 läpi. Koska 28:lla ei ole lapsia, siirry oikeaan alipuuhun, 44. Prosessi 44, koska sillä ei myöskään ole lapsia. Lopuksi käsittele juurisolmu, 32. Olet kulkenut tämän alipuun läpi järjestyksessä 28 -> 44 -> 32.

Käsittele oikea alipuu käyttämällä samaa lähestymistapaa käydäksesi solmuissa järjestyksessä 58 -> 88 → 62.

Lopuksi käsittele juurisolmu 56. Kuljet koko puun läpi tässä järjestyksessä:

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

Postorder Traversalin soveltaminen

Voit käyttää postorder traversal -toimintoa poistaaksesi puun lehdestä juureen. Voit käyttää sitä myös löytääksesi lausekepuun postfix-lausekkeen.

Voit käydä tietyn solmun kaikissa lehtisolmuissa ennen itse solmussa käymistä käyttämällä postorder traversal -tekniikkaa.

Binaarihakupuun läpikulkujen aika ja tila monimutkaisuus

Kaikkien kolmen läpikulkutekniikan aikamonimutkaisuus on Päällä), missä n on koko binääripuu. Kaikkien läpikulkutekniikoiden tilan monimutkaisuus on Vai niin), missä h on binääripuun korkeus.

Binääripuun koko on sama kuin kyseisen puun solmujen lukumäärä. Binääripuun korkeus on puun juurisolmun ja sen kaukaisimman lehtisolmun välisten reunojen lukumäärä.

Python-koodi binaarihakupuun läpikäymiseen

Alla on Python-ohjelma, joka suorittaa kaikki kolme binaarihakupuun läpikulkua:

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

Tämän ohjelman pitäisi tuottaa seuraava tulos:

Ohjelmoijien pakolliset algoritmit

Algoritmit ovat olennainen osa jokaisen ohjelmoijan matkaa. On erittäin tärkeää, että ohjelmoija tuntee hyvin algoritmit. Sinun pitäisi olla perehtynyt joihinkin algoritmeihin, kuten yhdistämislajittelu, pikalajittelu, binäärihaku, lineaarinen haku, syvyys ensimmäinen haku ja niin edelleen.