243
правки
Изменения
→Проверка того, что заданное дерево является деревом поиска
Для того чтобы решить эту задачу, применим [[Обход в глубину, цвета вершин|обход в глубину]]. Запустим от корня рекурсивную логическую функцию, которая выведет <tex>\mathtt{true}</tex>, если дерево является BST и <tex>\mathtt{false}</tex> в противном случае. Чтобы дерево не являлось BST, в нём должна быть хотя бы одна вершина, которая не попадает под определение дерева поиска. То есть достаточно найти всего одну такую вершину, чтобы выйти из рекурсии и вернуть значение <tex>\mathtt{false}</tex>. Если же, дойдя до листьев, функция не встретит на своём пути такие вершины, она вернёт значение <tex>\mathtt{true}</tex>.
'''bool''' check(v : '''Node''', min: '''integerint''', max: '''integerint'''): <font color="green">// min и max — минимально и максимально допустимые значения в вершинах поддерева.</font>
'''if''' v.left != ''null''
'''if''' v.left.key > v.key '''or''' v.left.key < min
