Постоји више од једног начина да посетите све чворове у БСТ-у.

Бинарна стабла су једна од најчешће коришћених структура података у програмирању. Бинарно стабло претраге (БСТ) омогућава складиштење података у облику чворова (родитељски и подређени чвор чвор) тако да је леви подређени чвор мањи од родитељског чвора, а десни подређени чвор већи.

Бинарна стабла претраге омогућавају ефикасне операције преласка, претраживања, брисања и уметања. У овом чланку ћете научити о три начина да се пређе кроз бинарно стабло претраге: прелазак по наруџбини, прелазак у редослед и обилазак постордера.

Инордер Траверсал

Прелазак у нередовном реду је процес преласка чворова а бинарно стабло претраге рекурзивном обрадом левог подстабла, затим обрадом коренског чвора и на крају рекурзивном обрадом десног подстабла. Пошто обрађује чворове у растућем редоследу вредности, техника се назива обилажење у инордеру.

Прелазак је процес посете сваког чвора у структури података стабла тачно једном.

Алгоритам преласка у редослед

instagram viewer

Поновите да бисте прошли кроз све чворове БСТ-а:

  1. Рекурзивно прелазите лево подстабло.
  2. Посетите основни чвор.
  3. Рекурзивно прелази преко десног подстабла.

Визуелизација преласка у редослед

Визуелни пример може помоћи да се објасни обилазак бинарног стабла претраге. Ова слика показује нередовно прелажење примера бинарног стабла претраге:

У овом стаблу бинарне претраге, 56 је основни чвор. Прво треба да пређете лево подстабло 32, затим коренски чвор 56, а затим десно подстабло 62.

За подстабло 32, прво пређите лево подстабло, 28. Ово подстабло нема потомство, па затим пређите преко 32 чвора. Затим пређите десно подстабло, 44, које такође нема деце. Стога је редослед преласка за подстабло са кореном на 32 28 -> 32 -> 44.

Затим посетите основни чвор, 56.

Затим пређите десно подстабло, укорењено на 62. Почните тако што ћете прећи његово лево подстабло, укорењено на 58. Нема деце, па посетите 62 чвор следеће. Коначно, пређите десно подстабло, 88, које такође нема деце.

Дакле, алгоритам посећује чворове стабла следећим редоследом:

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

Примена Инордер Траверсал

Можете да користите прелазак у редослед да бисте добили вредности елемената чвора у растућем редоследу. Да бисте добили вредности у опадајућем редоследу, једноставно обрните процес: посетите десно подстабло, затим коренски чвор, а затим лево подстабло. Можете користити алгоритам да пронађете израз префикса стабла израза.

Преордер Траверсал

Обилажење унапред по редоследу је слично инордеру, али обрађује коренски чвор пре него што рекурзивно обрађује лево подстабло, а затим десно подстабло.

Алгоритам преласка наруџбине

Поновите да бисте прошли кроз све чворове БСТ-а:

  1. Посетите основни чвор.
  2. Рекурзивно прелазите лево подстабло.
  3. Рекурзивно прелази преко десног подстабла.

Визуелизација преласка наруџбине

Следећа слика приказује обилазак бинарног стабла претраге у претпродаји:

У овом стаблу бинарне претраге почните са обрадом коренског чвора, 56. Затим пређите лево подстабло, 32, а затим десно подстабло, 62.

За лево подстабло, обрадите вредност у коренском чвору, 32. Затим пређите преко левог подстабла, 28, а затим на крају десног подстабла, 44. Овим се завршава обилазак левог подстабла укорењеног на 32. Прелазак се дешава следећим редоследом: 56 -> 32 -> 28 -> 44.

За десно подстабло, обрадите вредност у коренском чвору, 62. Затим пређите преко левог подстабла, 58, а затим на крају десног подстабла, 88. Опет, ниједан чвор нема деце, тако да је прелазак завршен у овом тренутку.

Прешли сте преко целог стабла следећим редоследом:

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

Примена Преордер Траверсал

Можете да користите прелазак у претпродаји да бисте најлакше направили копију стабла.

Постордер Траверсал

Обилажење постордера је процес рекурзивног преласка чворова бинарног стабла претраге обрада левог подстабла, затим рекурзивна обрада десног подстабла и на крају обрада коренски чвор. Пошто обрађује коренски чвор после оба подстабла, овај метод се зове постордер траверсал.

Алгоритам преласка Постордера

Поновите да бисте прошли кроз све чворове БСТ-а:

  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

Примена Постордер Траверсал-а

Можете користити постордер траверсал да обришете дрво од листа до корена. Такође можете да га користите да пронађете постфикс израз стабла израза.

Да бисте посетили све лисне чворове одређеног чвора пре него што посетите сам чвор, можете користити технику обиласка постордера.

Временска и просторна сложеност обилажења стабла бинарног претраживања

Временска сложеност све три технике преласка је На), где н је величина бинарно дрво. Просторна сложеност свих техника преласка је О(х), где х је висина бинарног стабла.

Величина бинарног стабла једнака је броју чворова у том стаблу. Висина бинарног стабла је број ивица између коренског чвора дрвета и његовог најудаљенијег лисног чвора.

Питхон код за обилазак стабла бинарног претраживања

Испод је Питхон програм за обављање сва три обиласка бинарног стабла претраге:

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

Овај програм би требало да произведе следеће резултате:

Алгоритми које морате знати за програмере

Алгоритми су суштински део путовања сваког програмера. За програмера је кључно да буде добро упућен у алгоритме. Требало би да сте упознати са неким од алгоритама као што су сортирање спајањем, брзо сортирање, бинарна претрага, линеарна претрага, претрага по дубини, и тако даље.