243
правки
Изменения
→Проверка того, что заданное дерево является деревом поиска
|definition = Определить, является ли заданное двоичное дерево деревом поиска.
}}
[[Файл:Not_enoughNot_Enough.png|right|thumb|301px|Пример дерева, для которого недостаточно проверки лишь его соседей]]
Для того чтобы решить эту задачу, применим [[Обход в глубину, цвета вершин|обход в глубину]]. Запустим от корня рекурсивную логическую функцию, которая выведет <tex>\mathtt{true}</tex>, если дерево является BST и <tex>\mathtt{false}</tex> в противном случае. Чтобы дерево не являлось BST, в нём должна быть хотя бы одна вершина, которая не попадает под определение дерева поиска. То есть достаточно найти всего одну такую вершину, чтобы выйти из рекурсии и вернуть значение <tex>\mathtt{false}</tex>. Если же, дойдя до листьев, функция не встретит на своём пути такие вершины, она вернёт значение <tex>\mathtt{true}</tex>.
