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