Ir vairāk nekā viens veids, kā apmeklēt visus BST mezglus.

Binārie koki ir viena no programmēšanā visbiežāk izmantotajām datu struktūrām. Binārais meklēšanas koks (BST) ļauj uzglabāt datus mezglu veidā (vecmezgls un pakārtots mezgls mezgls) tā, lai kreisais pakārtots mezgls būtu mazāks par vecākmezglu un labais pakārtots mezgls būtu mazāks lielāks.

Binārie meklēšanas koki nodrošina efektīvas šķērsošanas, meklēšanas, dzēšanas un ievietošanas darbības. Šajā rakstā jūs uzzināsit par trim veidiem, kā šķērsot bināro meklēšanas koku: priekšpasūtīšanas šķērsošana, pasūtījuma šķērsošana un postorder šķērsošana.

Pasūtījuma šķērsošana

Kārtības šķērsošana ir a mezglu šķērsošanas process binārā meklēšanas koks rekursīvi apstrādājot kreiso apakškoku, pēc tam apstrādājot saknes mezglu un visbeidzot rekursīvi apstrādājot labo apakškoku. Tā kā tas apstrādā mezglus augošā vērtību secībā, paņēmienu sauc par inorder traversal.

Traversēšana ir process, kurā katrs koka datu struktūras mezgls tiek apmeklēts tieši vienu reizi.

instagram viewer

Inorder Traversal algoritms

Atkārtojiet, lai šķērsotu visus BST mezglus:

  1. Rekursīvi šķērsojiet kreiso apakškoku.
  2. Apmeklējiet saknes mezglu.
  3. Rekursīvi šķērsojiet labo apakškoku.

Inorder Traversal vizualizācija

Vizuāls piemērs var palīdzēt izskaidrot binārā meklēšanas koka šķērsošanu. Šajā attēlā parādīta binārā meklēšanas koka piemēra šķērsošana secībā:

Šajā binārajā meklēšanas kokā 56 ir saknes mezgls. Vispirms jums jāšķērso kreisais apakškoks 32, tad saknes mezgls 56 un tad labais apakškoks 62.

Apakškokam 32 vispirms šķērsojiet kreiso apakškoku 28. Šim apakškokam nav bērnu, tāpēc nākamais šķērsojiet 32 ​​mezglu. Pēc tam šķērsojiet labo apakškoku 44, kuram arī nav bērnu. Tāpēc apbraukšanas secība apakškokam, kura sakne ir 32, ir 28 -> 32 -> 44.

Pēc tam apmeklējiet saknes mezglu 56.

Pēc tam šķērsojiet labo apakškoku, kura sakne ir 62. Sāciet, šķērsojot tā kreiso apakškoku, kura sakne ir 58. Tam nav bērnu, tāpēc apmeklējiet 62. mezglu. Visbeidzot, šķērsojiet labo apakškoku 88, kuram arī nav bērnu.

Tātad algoritms apmeklē koka mezglus šādā secībā:

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

Inorder Traversal piemērošana

Varat izmantot inorder traversal, lai iegūtu mezglu elementu vērtības augošā secībā. Lai iegūtu vērtības dilstošā secībā, vienkārši apgrieziet procesu: apmeklējiet labo apakškoku, tad saknes mezglu un pēc tam kreiso apakškoku. Varat izmantot algoritmu, lai atrastu izteiksmes koka prefiksa izteiksmi.

Iepriekšpasūtīšanas šķērsošana

Priekšpasūtīšanas šķērsošana ir līdzīga inorder, taču tā apstrādā saknes mezglu, pirms rekursīvi apstrādā kreiso apakškoku un pēc tam labo apakškoku.

Iepriekšpasūtīšanas šķērsošanas algoritms

Atkārtojiet, lai šķērsotu visus BST mezglus:

  1. Apmeklējiet saknes mezglu.
  2. Rekursīvi šķērsojiet kreiso apakškoku.
  3. Rekursīvi šķērsojiet labo apakškoku.

Iepriekšēja pasūtījuma izbraukšanas vizualizācija

Nākamajā attēlā parādīta binārā meklēšanas koka priekšpasūtīšanas caurlaide:

Šajā binārajā meklēšanas kokā sāciet ar saknes mezgla apstrādi 56. Pēc tam šķērsojiet kreiso apakškoku 32, kam seko labo apakškoku 62.

Kreisajam apakškokam apstrādājiet vērtību saknes mezglā 32. Pēc tam šķērsojiet kreiso apakškoku 28, tad visbeidzot labo apakškoku 44. Tas pabeidz kreisā apakškoka šķērsošanu, kas sakņojas 32. Pāreja notiek šādā secībā: 56 -> 32 -> 28 -> 44.

Labajam apakškokam apstrādājiet vērtību saknes mezglā 62. Pēc tam šķērsojiet kreiso apakškoku 58, tad visbeidzot labo apakškoku 88. Atkal, nevienam mezglam nav bērnu, tāpēc šķērsošana šajā brīdī ir pabeigta.

Jūs esat šķērsojis visu koku šādā secībā:

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

Priekšpasūtīšanas šķērsošanas pielietošana

Varat izmantot priekšpasūtīšanas šķērsošanu, lai visvieglāk izveidotu koka kopiju.

Postorder Traversal

Postorder šķērsošana ir process, kurā rekursīvi šķērso binārā meklēšanas koka mezglus apstrādājot kreiso apakškoku, pēc tam rekursīvi apstrādājot labo apakškoku un beidzot apstrādājot saknes mezgls. Tā kā tā apstrādā saknes mezglu pēc abiem apakškokiem, šo metodi sauc par postorder traversal.

Postorder Traversal algoritms

Atkārtojiet, lai šķērsotu visus BST mezglus:

  1. Rekursīvi šķērsojiet kreiso apakškoku.
  2. Rekursīvi šķērsojiet labo apakškoku.
  3. Apmeklējiet saknes mezglu.

Postorder Traversal vizualizācija

Nākamajā attēlā ir parādīta binārā meklēšanas koka šķērsošana pēc kārtas:

Sāciet, šķērsojot kreiso apakškoku 32, pēc tam labo apakškoku 62. Pabeidziet, apstrādājot saknes mezglu, 56.

Lai apstrādātu apakškoku, kura sakne ir 32, šķērsojiet tā kreiso apakškoku 28. Tā kā 28 nav bērnu, pārejiet uz labo apakškoku, 44. 44. process, jo tam arī nav bērnu. Visbeidzot, apstrādājiet saknes mezglu, 32. Jūs esat šķērsojis šo apakškoku secībā 28 -> 44 -> 32.

Apstrādājiet labo apakškoku, izmantojot to pašu pieeju, lai apmeklētu mezglus secībā 58 -> 88 → 62.

Visbeidzot apstrādājiet saknes mezglu 56. Jūs šķērsosit visu koku šādā secībā:

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

Postorder Traversal pielietošana

Varat izmantot postorder traversal, lai dzēstu koku no lapas līdz saknei. Varat arī to izmantot, lai atrastu izteiksmes koka postfix izteiksmi.

Lai apmeklētu visus noteikta mezgla lapu mezglus pirms paša mezgla apmeklējuma, varat izmantot postorder traversal tehniku.

Binārās meklēšanas koka pārvietošanās laika un telpas sarežģītība

Visu trīs šķērsošanas metožu laika sarežģītība ir O(n), kur n ir izmērs binārais koks. Visu šķērsošanas metožu kosmosa sarežģītība ir O(h), kur h ir binārā koka augstums.

Binārā koka izmērs ir vienāds ar mezglu skaitu šajā kokā. Binārā koka augstums ir malu skaits starp koka saknes mezglu un tā tālāko lapas mezglu.

Python kods binārās meklēšanas koka šķērsošanai

Zemāk ir Python programma, lai veiktu visas trīs binārās meklēšanas koka šķērsošanas:

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

Šai programmai jārada šāda izvade:

Algoritmi, kas programmētājiem jāzina

Algoritmi ir būtiska katra programmētāja ceļojuma sastāvdaļa. Programmētājam ir ļoti svarīgi labi pārzināt algoritmus. Jums ir jāzina daži algoritmi, piemēram, sapludināšanas kārtošana, ātrā kārtošana, binārā meklēšana, lineārā meklēšana, dziļuma pirmā meklēšana utt.