Kõigi BST sõlmede külastamiseks on rohkem kui üks viis.

Binaarsed puud on programmeerimises üks enim kasutatavaid andmestruktuure. Binaarne otsingupuu (BST) võimaldab salvestada andmeid sõlmede kujul (vanemasõlm ja alamsõlm sõlm) nii, et vasak alamsõlm on väiksem kui emasõlm ja parem alamsõlm on väiksem suurem.

Binaarsed otsingupuud võimaldavad tõhusalt läbida, otsida, kustutada ja sisestada. Sellest artiklist saate teada kolme binaarse otsingupuu läbimise viisi kohta: eeltellimuse läbimine, tellimuse läbimine ja järeltellimuse läbimine.

Tellimuse läbimine

Järjekorra läbimine on a sõlmede läbimise protsess binaarne otsingupuu vasakpoolset alampuud rekursiivselt töödeldes, seejärel juursõlme ja lõpuks parempoolset alampuud rekursiivselt. Kuna see töötleb sõlmpunkte väärtuste kasvavas järjekorras, nimetatakse seda tehnikat inorder traversaaliks.

Läbimine on protsess, mille käigus külastatakse puu andmestruktuuri iga sõlme täpselt üks kord.

Inorderi läbimise algoritm

Korrake BST kõigi sõlmede läbimiseks:

instagram viewer
  1. Vasaku alampuu rekursiivne läbimine.
  2. Külastage juursõlme.
  3. Parempoolse alampuu rekursiivne läbimine.

Inorderi läbimise visualiseerimine

Visuaalne näide võib aidata selgitada binaarse otsingupuu läbimist. See joonis näitab binaarse otsingupuu näite järjestikust läbimist:

Selles binaarses otsingupuus on 56 juursõlm. Esiteks peate läbima vasakpoolse alampuu 32, seejärel juursõlme 56 ja seejärel parema alampuu 62.

Alampuu 32 jaoks läbige esmalt vasakpoolne alampuu 28. Sellel alampuul ei ole lapsi, seega läbige järgmisena 32 sõlme. Järgmisena läbige parempoolne alampuu 44, millel pole samuti lapsi. Seetõttu on 32 juures juurdunud alampuu läbimise järjekord 28 -> 32 -> 44.

Järgmisena külastage juursõlme 56.

Seejärel läbige parempoolne alampuu, mille juur on 62. Alustage selle vasakpoolse alampuu läbimisega, mille juur on 58. Sellel ei ole lapsi, seega külastage järgmisena 62 sõlme. Lõpuks läbige parempoolne alampuu 88, millel pole samuti lapsi.

Algoritm külastab puu sõlmi järgmises järjekorras:

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

Inorder Traversal'i rakendamine

Sõlmeelementide väärtuste saamiseks kasvavas järjekorras saate kasutada inorder traversal. Väärtuste saamiseks kahanevas järjekorras muutke protsess lihtsalt vastupidiseks: külastage parempoolset alampuud, seejärel juursõlme ja seejärel vasakut alampuud. Algoritmi abil saate leida avaldisepuu eesliite avaldise.

Ettetellige läbimine

Eeltellimuse läbimine sarnaneb inorderiga, kuid see töötleb juursõlme, enne kui rekursiivselt töötleb vasakut alampuud ja seejärel paremat alampuud.

Eeltellimuse läbimise algoritm

Korrake BST kõigi sõlmede läbimiseks:

  1. Külastage juursõlme.
  2. Vasaku alampuu rekursiivne läbimine.
  3. Parempoolse alampuu rekursiivne läbimine.

Ettetellimuse läbimise visualiseerimine

Järgmine joonis näitab binaarse otsingupuu eeltellimuse läbimist:

Selles binaarses otsingupuus alustage juursõlme 56 töötlemisest. Seejärel läbige vasakpoolne alampuu 32, millele järgneb parem alampuu 62.

Vasaku alampuu puhul töötle väärtust juursõlmes 32. Järgmisena läbige vasakpoolne alampuu 28 ja lõpuks parempoolne alampuu 44. See lõpetab 32 juures oleva vasakpoolse alampuu läbimise. Läbimine toimub järgmises järjekorras: 56 -> 32 -> 28 -> 44.

Parema alampuu jaoks töötle väärtust juursõlmes 62. Järgmisena läbige vasakpoolne alampuu 58, seejärel lõpuks parempoolne alampuu 88. Jällegi, kummalgi sõlmel pole lapsi, nii et läbimine on praeguseks lõpule viidud.

Olete kogu puu läbinud järgmises järjekorras:

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

Ettetellimuse läbimise rakendamine

Puust koopia loomiseks saate kasutada ettetellimise läbimist.

Postorder Traversal

Järelkäimine on binaarse otsingupuu sõlmede rekursiivse läbimise protsess vasaku alampuu töötlemine, seejärel parempoolse alampuu rekursiivne töötlemine ja lõpuks alampuu töötlemine juursõlm. Kuna see töötleb juursõlme mõlema alampuu järel, nimetatakse seda meetodit postorder traversaliks.

Postorder läbimise algoritm

Korrake BST kõigi sõlmede läbimiseks:

  1. Vasaku alampuu rekursiivne läbimine.
  2. Parempoolse alampuu rekursiivne läbimine.
  3. Külastage juursõlme.

Postorderi läbimise visualiseerimine

Järgmisel joonisel on kujutatud binaarse otsingupuu postorder läbimist:

Alustage vasakpoolse alampuu 32 läbimisega, seejärel parema alampuuga 62. Lõpetage juursõlme töötlemine, 56.

Alampuu töötlemiseks, mille juur on 32, läbige selle vasakpoolne alampuu 28. Kuna 28-l ei ole lapsi, liigu parempoolsesse alampuusse, 44. Protsess 44, kuna sellel pole ka lapsi. Lõpuks töödelge juursõlm 32. Olete selle alampuu läbinud järjekorras 28 -> 44 -> 32.

Töötlege õiget alampuud, kasutades sama lähenemisviisi sõlmede külastamiseks järjekorras 58 -> 88 → 62.

Lõpuks töödelge juursõlm 56. Läbite kogu puu järgmises järjekorras:

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

Postorder Traversal'i rakendamine

Saate kasutada postorder läbimist, et kustutada puu lehest juureni. Samuti saate seda kasutada avaldisepuu postfiksi avaldise leidmiseks.

Teatud sõlme kõigi lehtede sõlmede külastamiseks enne sõlme enda külastamist võite kasutada järelkäimise tehnikat.

Binaarse otsingupuu läbimiste aja ja ruumi keerukus

Kõigi kolme läbimise tehnika ajaline keerukus on Peal), kus n on suurus kahendpuu. Kõigi läbimistehnikate ruumiline keerukus on O(h), kus h on kahendpuu kõrgus.

Binaarse puu suurus võrdub selle puu sõlmede arvuga. Binaarse puu kõrgus on puu juuresõlme ja selle kaugeima lehesõlme vaheliste servade arv.

Pythoni kood binaarse otsingupuu läbimiseks

Allpool on Pythoni programm kõigi kolme binaarse otsingupuu läbimise tegemiseks:

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

See programm peaks tootma järgmise väljundi:

Algoritmid, mida programmeerijad peavad teadma

Algoritmid on iga programmeerija teekonna oluline osa. Programmeerija jaoks on ülioluline, et ta tunneks hästi algoritme. Peaksite olema tuttav mõne algoritmiga, nagu liitmissortimine, kiirsortimine, binaarne otsing, lineaarne otsing, sügavuse esimene otsing jne.