Yra daugiau nei vienas būdas aplankyti visus BST mazgus.

Dvejetainiai medžiai yra viena iš dažniausiai programuojant naudojamų duomenų struktūrų. Dvejetainis paieškos medis (BST) leidžia saugoti duomenis mazgų (pirminio mazgo ir antrinio) pavidalu. mazgas), kad kairysis antrinis mazgas būtų mažesnis už pirminį mazgą, o dešinysis antrinis mazgas didesnis.

Dvejetainiai paieškos medžiai leidžia efektyviai atlikti perėjimo, paieškos, trynimo ir įterpimo operacijas. Šiame straipsnyje sužinosite apie tris būdus, kaip pereiti dvejetainį paieškos medį: išankstinio užsakymo perėjimą, įsakymo eigą ir postorder traversal.

Inorder Traversal

Inorder traversal yra a mazgų perėjimo procesas dvejetainis paieškos medis rekursyviai apdorojant kairįjį pomedį, tada apdorojant šakninį mazgą ir galiausiai rekursyviai apdorojant dešinįjį pomedį. Kadangi ji apdoroja mazgus didėjančia reikšmių tvarka, ši technika vadinama inorder traversal.

Perėjimas – tai kiekvieno medžio duomenų struktūros mazgo apsilankymo procesas tiksliai vieną kartą.

instagram viewer

Inorder Traversal algoritmas

Pakartokite, kad pereitumėte visus BST mazgus:

  1. Rekursyviai pereiti kairįjį pomedį.
  2. Apsilankykite šakniniame mazge.
  3. Rekursyviai pereiti dešinįjį pomedį.

Inorder Traversal vizualizacija

Vaizdinis pavyzdys gali padėti paaiškinti dvejetainio paieškos medžio perėjimą. Šiame paveikslėlyje parodytas dvejetainės paieškos medžio pavyzdžio eilės tvarka:

Šiame dvejetainiame paieškos medyje 56 yra šakninis mazgas. Pirmiausia turite pereiti kairįjį pomedį 32, tada šakninį mazgą 56 ir tada dešinįjį pomedį 62.

32 pomedžiui pirmiausia pereikite per kairįjį pomedį, 28. Šis pomedis neturi vaikų, todėl kitą kartą pereikite per 32 mazgą. Tada pereikite per dešinįjį pomedį 44, kuriame taip pat nėra vaikų. Todėl pomedžio, kurio šaknis yra 32, perėjimo tvarka yra 28 -> 32 -> 44.

Tada apsilankykite šakniniame mazge 56.

Tada pereikite dešinįjį pomedį, kurio šaknys yra 62. Pradėkite perėję jo kairįjį pomedį, kurio šaknys yra 58. Jame nėra vaikų, todėl eikite į 62 mazgą. Galiausiai pereikite per dešinįjį pomedį 88, kuris taip pat neturi vaikų.

Taigi algoritmas lanko medžio mazgus tokia tvarka:

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

Inorder Traversal taikymas

Norėdami gauti mazgo elementų reikšmes didėjančia tvarka, galite naudoti inorder traversal. Norėdami gauti reikšmes mažėjančia tvarka, tiesiog apverskite procesą: apsilankykite dešiniajame pomedyje, tada šakniniame mazge, tada kairiajame pomedyje. Naudodami algoritmą galite rasti išraiškos medžio priešdėlio išraišką.

Išankstinis užsakymas „Traversal“.

Išankstinio užsakymo perkėlimas yra panašus į inorder, tačiau jis apdoroja šakninį mazgą prieš rekursyviai apdorodamas kairįjį pomedį, tada dešinįjį pomedį.

Išankstinio užsakymo judėjimo algoritmas

Pakartokite, kad pereitumėte visus BST mazgus:

  1. Apsilankykite šakniniame mazge.
  2. Rekursyviai pereiti kairįjį pomedį.
  3. Rekursyviai pereiti dešinįjį pomedį.

Išankstinio užsakymo vizualizacija

Toliau pateiktame paveikslėlyje parodytas dvejetainio paieškos medžio išankstinis užsakymas.

Šiame dvejetainiame paieškos medyje pradėkite apdoroti šakninį mazgą 56. Tada pereikite kairiuoju pomedžiu 32, po to dešiniuoju pomedžiu 62.

Kairiajame pomedžiu apdorokite reikšmę šakniniame mazge 32. Tada pereikite kairiuoju pomedžiu 28, tada galiausiai dešiniuoju pomedžiu 44. Tai užbaigia kairiojo pomedžio, kurio šaknys yra 32, perėjimą. Perėjimas vyksta tokia tvarka: 56 -> 32 -> 28 -> 44.

Dešiniajam pomedžiui apdorokite reikšmę šakniniame mazge 62. Tada pereikite kairiuoju pomedžiu 58, tada galiausiai dešiniuoju pomedžiu 88. Vėlgi, nė vienas mazgas neturi vaikų, todėl perėjimas šiuo metu yra baigtas.

Perėjote visą medį tokia tvarka:

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

Išankstinio užsakymo perėjimo taikymas

Norėdami lengviausia medžio kopiją sukurti, galite naudoti išankstinio užsakymo perėjimą.

Postorder Traversal

Postorder traversal – tai dvejetainio paieškos medžio mazgų perėjimo procesas rekursyviai apdorojant kairįjį pomedį, tada rekursyviai apdorojant dešinįjį pomedį ir galiausiai apdorojant šaknies mazgas. Kadangi jis apdoroja šakninį mazgą po abiejų pomedžių, šis metodas vadinamas postorder traversal.

Postorder Traversal algoritmas

Pakartokite, kad pereitumėte visus BST mazgus:

  1. Rekursyviai pereiti kairįjį pomedį.
  2. Rekursyviai pereiti dešinįjį pomedį.
  3. Apsilankykite šakniniame mazge.

Postorder Traversal vizualizacija

Toliau pateiktame paveikslėlyje parodytas dvejetainio paieškos medžio postorder perėjimas:

Pradėkite nuo kairiojo pomedžio 32, tada dešiniuoju pomedžiu 62. Užbaikite apdorodami šakninį mazgą, 56.

Norėdami apdoroti pomedį, kurio šaknis yra 32, pereikite jo kairįjį pomedį, 28. Kadangi 28 neturi vaikų, pereikite prie dešiniojo pomedžio, 44. 44 procesas, nes jis taip pat neturi vaikų. Galiausiai apdorokite šakninį mazgą, 32. Perėjote šį pomedį tvarka 28 -> 44 -> 32.

Apdorokite tinkamą pomedį naudodami tą patį metodą, kad aplankytumėte mazgus tvarka 58 -> 88 → 62.

Galiausiai apdorokite šakninį mazgą 56. Per visą medį pereisite tokia tvarka:

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

Postorder Traversal taikymas

Norėdami ištrinti medį nuo lapo iki šaknies, galite naudoti postorder traversal. Taip pat galite jį naudoti norėdami rasti išraiškos medžio postfix išraišką.

Norėdami aplankyti visus tam tikro mazgo lapų mazgus prieš apsilankydami pačiame mazge, galite naudoti postorder traversal techniką.

Dvejetainės paieškos medžio perėjimų laiko ir erdvės sudėtingumas

Visų trijų važiavimo būdų sudėtingumas yra toks O(n), kur n yra dydis dvejetainis medis. Visų perėjimo metodų erdvės sudėtingumas yra Oi), kur h yra dvejetainio medžio aukštis.

Dvejetainio medžio dydis lygus to medžio mazgų skaičiui. Dvejetainio medžio aukštis yra kraštų skaičius tarp medžio šaknies mazgo ir tolimiausio lapo mazgo.

Python kodas, skirtas dvejetainiam paieškos medžiui

Žemiau yra „Python“ programa, skirta atlikti visas tris dvejetainio medžio paieškos operacijas:

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

Ši programa turėtų sukurti tokią išvestį:

Algoritmai, kuriuos būtina žinoti programuotojams

Algoritmai yra esminė kiekvieno programuotojo kelionės dalis. Labai svarbu, kad programuotojas gerai išmanytų algoritmus. Turėtumėte būti susipažinę su kai kuriais algoritmais, tokiais kaip sujungimo rūšiavimas, greitas rūšiavimas, dvejetainė paieška, linijinė paieška, paieška pagal gylį ir pan.