Я участвую в 30-дневном соревновании по программированию на Python, и в этой статье я попытаюсь выяснить, является ли бинарное дерево бинарным деревом поиска.
Что такое бинарное дерево?
- дерево, в котором каждый узел имеет не более 2 дочерних элементов
Что такое бинарное дерево поиска?
- Значение каждого узла в левом поддереве узла меньше значения данных этого узла.
- Значение каждого узла в правом поддереве узла больше, чемзначение данных этого узла.
Я также рассмотрел структуры данных, в частности, деревья/обход дерева в предыдущей статье:
Проблема:
Решение:
######################### SOLUTION I #########################################
def is_binary_search_tree(root):
"""
Determines whether a binary tree is a binary search tree.
Args:
root: The root node of the binary tree.
Returns:
True if the binary tree is a binary search tree, False otherwise.
"""
def is_bst_helper(node, min_val, max_val):
if node is None:
return True
if node.value < min_val or node.value > max_val:
return False
return (is_bst_helper(node.left, min_val, node.value-1) and
is_bst_helper(node.right, node.value+1, max_val))
return is_bst_helper(root, float('-inf'), float('inf'))
######################### SOLUTION II #########################################
def check_binary_search_tree(root):
"""
Determines whether a binary tree is a binary search tree.
Args:
root: The root node of the binary tree.
Returns:
True if the binary tree is a binary search tree, False otherwise.
"""
if root == None:
return True
else:
if root.left:
leftData = traversingTree(root.left,[])
if root.data <= max(leftData):
return False
if root.right:
rightData = traversingTree(root.right,[])
if root.data >= min(rightData):
return False
return (is_binary_search_tree(root.left, min_val, root.data) and \\
is_binary_search_tree(root.right, root.data, max_val))
def traversingTree(root, datas):
"""
Used to travers the tree both on the left side and on the right branch.
"""
if root == None:
return
else:
datas.append(root.data)
traversingTree(root.left,datas)
traversingTree(root.right,datas)
return datas
Объяснение и заключение:
Решение I:
Эта версия кода принимает те же аргументы, что и функция is_bst_helper, со значениями по умолчанию отрицательная бесконечность и положительная бесконечность для min_val и max_val соответственно.
Что для первой итерации, конечно, означает, что вы никогда не найдете меньшее или большее значение для min_val или max_val.
Сначала функция проверяет, находится ли атрибут data узла root в пределах допустимого диапазона, определенного min_val и max_val.
Если нет, функция возвращает False.
В противном случае функция рекурсивно проверяет левое и правое поддеревья текущего узла, чтобы убедиться, что они также удовлетворяют Требования к упорядочению бинарного дерева поиска.
Если и левое, и правое поддеревья являются бинарными деревьями поиска, функция возвращает True.
В противном случае функция возвращает False.
Решение II:
Для второго решения логика такая же, однако мы будем рекурсивно и одновременно проходить каждую ветвь дерева, начиная с корневого узла.
Если мы находим какой-либо левый узел больше, чем узел данных, мы возвращаем False.
Если мы находим какой-либо правый узел меньше, чем узел данных, мы возвращаем False.
мы делаем это, пока не проверим самый дальний узел.
