Изменения

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

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

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

Навигация