Как обойти двоичное дерево поиска
Существует несколько способов посетить все узлы BST.
Двоичные деревья — одна из наиболее часто используемых структур данных в программировании. Двоичное дерево поиска (BST) позволяет хранить данные в виде узлов (родительский узел и дочерний узел), так что левый дочерний узел меньше родительского узла, а правый дочерний узел больше.
Двоичные деревья поиска позволяют эффективно выполнять операции обхода, поиска, удаления и вставки. В этой статье вы узнаете о трех способах обхода двоичного дерева поиска: обход в предварительном порядке, обход в обратном порядке и обход в обратном порядке.
Обход по порядку
Неупорядоченный обход — это процесс обхода узлов двоичного дерева поиска путем рекурсивной обработки левого поддерева, затем обработки корневого узла и, наконец, рекурсивной обработки правого поддерева. Поскольку он обрабатывает узлы в порядке возрастания значений, этот метод называется обходом по порядку.
Обход — это процесс посещения каждого узла древовидной структуры данных ровно один раз.
Алгоритм обхода порядка
Повторите, чтобы пройти все узлы BST:
- Рекурсивно обойти левое поддерево.
- Посетите корневой узел.
- Рекурсивно обойти правое поддерево.
Визуализация обхода порядка
Наглядный пример может помочь объяснить обход двоичного дерева поиска. На этом рисунке показан обход по порядку примера двоичного дерева поиска:
В этом двоичном дереве поиска 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:
- Посетите корневой узел.
- Рекурсивно обойти левое поддерево.
- Рекурсивно обойти правое поддерево.
Визуализация обхода предзаказа
На следующем рисунке показан предварительный обход двоичного дерева поиска:
В этом двоичном дереве поиска начните с обработки корневого узла 56. Затем просмотрите левое поддерево 32, а затем правое поддерево 62.
Для левого поддерева обработайте значение в корневом узле, 32. Затем пройдите левое поддерево, 28, затем, наконец, правое поддерево, 44. Это завершает обход левого поддерева с корнем в 32. Обход происходит в следующем порядке : 56 -> 32 -> 28 -> 44.
Для правого поддерева обработайте значение в корневом узле, 62. Затем пройдите левое поддерево, 58, затем, наконец, правое поддерево, 88. Опять же, ни один из узлов не имеет дочерних элементов, поэтому обход завершен на этом этапе.
Вы прошли все дерево в следующем порядке:
56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88
Применение обхода предзаказа
Вы можете использовать предварительный обход, чтобы проще всего создать копию дерева.
Обход постзаказа
Обход постпорядка — это процесс обхода узлов двоичного дерева поиска путем рекурсивной обработки левого поддерева, затем рекурсивной обработки правого поддерева и, наконец, обработки корневого узла. Поскольку он обрабатывает корневой узел после обоих поддеревьев, этот метод называется обходом в обратном порядке.
Алгоритм обхода постпорядка
Повторите, чтобы пройти все узлы BST:
- Рекурсивно обойти левое поддерево.
- Рекурсивно обойти правое поддерево.
- Посетите корневой узел.
Визуализация обхода постпорядка
На следующем рисунке показан обратный обход двоичного дерева поиска:
Начните с обхода левого поддерева 32, затем правого поддерева 62. Завершите обработкой корневого узла 56.
Чтобы обработать поддерево с корнем 32, просмотрите его левое поддерево 28. Поскольку у 28 нет дочерних элементов, перейдите к правому поддереву 44. Обработайте 44, поскольку у него также нет дочерних элементов. Наконец, обработайте корневой узел 32. Вы прошли это поддерево в порядке 28 -> 44 -> 32.
Обработайте правое поддерево, используя тот же подход, чтобы посетить узлы в порядке 58 → 88 → 62.
Наконец, обработайте корневой узел 56. Вы пройдете все дерево в следующем порядке:
28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56
Применение обхода постордеров
Вы можете использовать обратный порядок обхода, чтобы удалить дерево от листа до корня. Вы также можете использовать его для поиска постфиксного выражения дерева выражений.
Чтобы посетить все конечные узлы определенного узла перед посещением самого узла, вы можете использовать технику обхода в обратном порядке.
Временная и пространственная сложность обхода двоичного дерева поиска
Временная сложность всех трех методов обхода равна O(n), где n — размер двоичного дерева. Пространственная сложность всех методов обхода равна O(h), где h — высота двоичного дерева.
Размер двоичного дерева равен количеству узлов в этом дереве. Высота двоичного дерева — это количество ребер между корневым узлом дерева и его самым дальним листовым узлом.
Код Python для обхода дерева двоичного поиска
Ниже приведена программа Python для выполнения всех трех обходов двоичного дерева поиска:
# Node class is used to create individual nodes
# of the Binary Search Tree (BST)
class Node:
def __init__(self, element):
self.left = None
self.right = None
self.value = element
# Function to perform the inorder tree traversal
def inorder(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
def postorder(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
def preorder(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)
Эта программа должна выдать следующий результат:
Алгоритмы, которые необходимо знать программистам
Алгоритмы являются неотъемлемой частью пути каждого программиста. Для программиста крайне важно хорошо разбираться в алгоритмах. Вы должны быть знакомы с некоторыми алгоритмами, такими как сортировка слиянием, быстрая сортировка, двоичный поиск, линейный поиск, поиск в глубину и т. д.