Есть несколько способов посетить все узлы в BST.

Двоичные деревья — одна из наиболее часто используемых структур данных в программировании. Двоичное дерево поиска (BST) позволяет хранить данные в виде узлов (родительский узел и дочерний узел). node) таким образом, что левый дочерний узел меньше родительского узла, а правый дочерний узел больше.

Двоичные деревья поиска позволяют эффективно выполнять операции обхода, поиска, удаления и вставки. В этой статье вы узнаете о трех способах обхода бинарного дерева поиска: обход в прямом порядке, обход в обратном порядке и обход в обратном порядке.

Неупорядоченный обход

Неупорядоченный обход — это процесс обхода узлов бинарное дерево поиска путем рекурсивной обработки левого поддерева, затем обработки корневого узла и, наконец, рекурсивной обработки правого поддерева. Поскольку он обрабатывает узлы в порядке возрастания значений, этот метод называется неупорядоченным обходом.

Обход — это процесс посещения каждого узла в древовидной структуре данных ровно один раз.

instagram viewer

Алгоритм неупорядоченного обхода

Повторите, чтобы обойти все узлы BST:

  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

Применение упорядоченного обхода

Вы можете использовать неупорядоченный обход, чтобы получить значения элементов узла в порядке возрастания. Чтобы получить значения в порядке убывания, просто выполните обратный процесс: посетите правое поддерево, затем корневой узел, затем левое поддерево. Вы можете использовать алгоритм, чтобы найти выражение префикса дерева выражений.

Обход предзаказа

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

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

Повторите, чтобы обойти все узлы 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

Применение обхода предварительного заказа

Вы можете использовать предварительный обход, чтобы проще всего создать копию дерева.

Почтовый обход

Обход в обратном порядке — это процесс обхода узлов бинарного дерева поиска рекурсивно. обработка левого поддерева, затем рекурсивная обработка правого поддерева и, наконец, обработка корневой узел. Поскольку он обрабатывает корневой узел после обоих поддеревьев, этот метод называется обходом в обратном порядке.

Алгоритм обхода постпорядка

Повторите, чтобы обойти все узлы 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

Применение обратного обхода

Вы можете использовать обход в обратном порядке, чтобы удалить дерево от листа до корня. Вы также можете использовать его для поиска постфиксного выражения дерева выражений.

Чтобы посетить все листовые узлы определенного узла перед посещением самого узла, вы можете использовать технику обратного обхода.

Временная и пространственная сложность обхода бинарного дерева поиска

Временная сложность всех трех методов обхода равна На), где н размер бинарное дерево. Пространственная сложность всех методов обхода равна Ой), где час высота бинарного дерева.

Размер бинарного дерева равен количеству узлов в этом дереве. Высота бинарного дерева — это количество ребер между корневым узлом дерева и его самым дальним конечным узлом.

Код 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)

Эта программа должна выдать следующий результат:

Обязательные алгоритмы для программистов

Алгоритмы — неотъемлемая часть пути каждого программиста. Для программиста крайне важно хорошо разбираться в алгоритмах. Вы должны быть знакомы с некоторыми алгоритмами, такими как сортировка слиянием, быстрая сортировка, бинарный поиск, линейный поиск, поиск в глубину и так далее.