Изменения

Перейти к: навигация, поиск

Дерево поиска, наивная реализация

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

Навигация