Има повече от един начин да посетите всички възли в BST.

Двоичните дървета са една от най-използваните структури от данни в програмирането. Двоично дърво за търсене (BST) позволява съхраняването на данни под формата на възли (родителски възел и дъщерен възел), така че левият дъщерен възел е по-малък от родителския възел, а десният дъщерен възел е по-голяма.

Двоичните дървета за търсене позволяват ефективни операции за обхождане, търсене, изтриване и вмъкване. В тази статия ще научите за трите начина за обхождане на двоично дърво за търсене: обхождане преди поръчка, обхождане по ред и обхождане след поръчка.

Обхождане по ред

Обхождането по ред е процесът на преминаване на възли на a двоично дърво за търсене чрез рекурсивна обработка на лявото поддърво, след това обработка на коренния възел и накрая рекурсивна обработка на дясното поддърво. Тъй като обработва възли във възходящ ред на стойността, техниката се нарича обхождане по ред.

Обхождането е процес на посещение на всеки възел в дървовидна структура от данни точно веднъж.

instagram viewer

Алгоритъм за обхождане по ред

Повторете, за да преминете през всички възли на BST:

  1. Рекурсивно преминаване през лявото поддърво.
  2. Посетете основния възел.
  3. Рекурсивно преминаване през дясното поддърво.

Визуализация на Inorder Traversal

Визуален пример може да помогне да се обясни обхождането на дървото за двоично търсене. Тази фигура показва обхождането по ред на примерно двоично дърво за търсене:

В това двоично дърво за търсене 56 е основният възел. Първо, трябва да прекосите лявото поддърво 32, след това основния възел 56 и след това дясното поддърво 62.

За поддървото 32, първо пресечете лявото поддърво, 28. Това поддърво няма деца, така че следващото пресичане на 32 възел. След това преминете през дясното поддърво, 44, което също няма деца. Следователно редът на преминаване за поддървото с корен в 32 е 28 -> 32 -> 44.

След това посетете основния възел, 56.

След това преминете през дясното поддърво, вкоренено на 62. Започнете, като преминете през лявото му поддърво, вкоренено на 58. Той няма деца, така че посетете възела 62 следващия. Накрая преминете през дясното поддърво, 88, което също няма деца.

Така че алгоритъмът посещава възлите на дървото в следния ред:

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

Приложение на Inorder Traversal

Можете да използвате обхождане по ред, за да получите стойностите на възловите елементи във възходящ ред. За да получите стойностите в низходящ ред, просто обърнете процеса: посетете дясното поддърво, след това основния възел, след това лявото поддърво. Можете да използвате алгоритъма, за да намерите префиксния израз на изразно дърво.

Обхождане на предварителна поръчка

Обхождането на предварителната поръчка е подобно на inorder, но обработва основния възел, преди рекурсивно да обработи лявото поддърво, след това дясното поддърво.

Алгоритъм за обхождане на предварителна поръчка

Повторете, за да преминете през всички възли на BST:

  1. Посетете основния възел.
  2. Рекурсивно преминаване през лявото поддърво.
  3. Рекурсивно преминаване през дясното поддърво.

Визуализация на обхождането на предварителната поръчка

Следващата фигура показва обхождането с предварителна поръчка на дървото за двоично търсене:

В това двоично дърво за търсене започнете с обработка на коренния възел, 56. След това пресечете лявото поддърво, 32, последвано от дясното поддърво, 62.

За лявото поддърво обработете стойността в основния възел, 32. След това преминете през лявото поддърво, 28, и накрая през дясното поддърво, 44. Това завършва обхождането на лявото поддърво с корен в 32. Преминаването става в следния ред: 56 -> 32 -> 28 -> 44.

За дясното поддърво обработете стойността в основния възел, 62. След това преминете през лявото поддърво, 58, и накрая през дясното поддърво, 88. Отново, нито един възел няма деца, така че преминаването е завършено в този момент.

Вие преминахте през цялото дърво в следния ред:

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

Приложение на Preorder Traversal

Можете да използвате обхождане с предварителна поръчка, за да създадете най-лесно копие на дървото.

Преминаване след поръчка

Обхождането след поръчка е процес на рекурсивно преминаване на възли на дърво за двоично търсене обработка на лявото поддърво, след това рекурсивна обработка на дясното поддърво и накрая обработка на коренов възел. Тъй като обработва коренния възел след двете поддървета, този метод се нарича преход след поръчката.

Алгоритъм за преминаване след поръчка

Повторете, за да преминете през всички възли на BST:

  1. Рекурсивно преминаване през лявото поддърво.
  2. Рекурсивно преминаване през дясното поддърво.
  3. Посетете основния възел.

Визуализация на прехода след поръчка

Следващата фигура показва прехода след поръчка на дървото за двоично търсене:

Започнете, като преминете през лявото поддърво, 32, след това през дясното поддърво, 62. Завършете с обработка на коренния възел, 56.

За да обработите поддървото, вкоренено в 32, пресечете лявото му поддърво, 28. Тъй като 28 няма деца, преминете към дясното поддърво, 44. Процес 44, тъй като той също няма деца. Накрая обработете основния възел, 32. Вие преминахте през това поддърво в реда 28 -> 44 -> 32.

Обработете дясното поддърво, като използвате същия подход, за да посетите възли в реда 58 -> 88 → 62.

Накрая обработете основния възел, 56. Ще прекосите цялото дърво в този ред:

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

Приложение на Postorder Traversal

Можете да използвате postorder traversal, за да изтриете дърво от листа до корена. Можете също да го използвате, за да намерите постфиксния израз на изразно дърво.

За да посетите всички листови възли на определен възел, преди да посетите самия възел, можете да използвате техниката за преминаване след поръчка.

Времева и пространствена сложност на обхождането на двоично дърво за търсене

Времевата сложност и на трите техники за преминаване е На), където н е размерът на двоично дърво. Пространствената сложност на всички техники за преминаване е O(h), където ч е височината на двоичното дърво.

Размерът на двоичното дърво е равен на броя на възлите в това дърво. Височината на двоичното дърво е броят на ръбовете между коренния възел на дървото и неговия най-отдалечен листен възел.

Код на Python за обхождане на двоично дърво за търсене

По-долу е дадена програма на Python за извършване на трите обхождания на дървото за двоично търсене:

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

Тази програма трябва да генерира следния резултат:

Алгоритми, които трябва да знаете за програмисти

Алгоритмите са съществена част от пътя на всеки програмист. От решаващо значение е програмистът да е добре запознат с алгоритмите. Трябва да сте запознати с някои от алгоритмите като сортиране чрез сливане, бързо сортиране, двоично търсене, линейно търсене, първо търсене в дълбочина и т.н.