Изменения

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

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

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

Навигация