212
правок
Изменения
→Псевдокод
====Псевдокод====
Для удобства опишем класс решения этой задачи нам понадобятся стандартные функции '''NodegetMax'''(вершина). В поле и '''maxgetMin''' будем хранить максимальное значение в данном поддереве, которые возвращают максимум и минимум в поле '''min''' минимальное значение, а поля '''l''' и '''r''' хранят ссылки на левого и правого сыновей дереве поиска соответственно.
<code>
'''boolean''' isSearchTree(Node v):
'''if''' (v.l == null && v.r == null) <font color = "green">// Если текущая вершина - лист</font>
'''return''' true;
'''if''' (isSearchTree(v.l) && isSearchTree(v.r) && getMax(v.l) < v.val && getMin(v.r) > v.val) <font color = "green">
// getMax и getMin запускаются только, если оба поддерева являются деревьями поиска </font>
'''return''' true; <font color = "green">// Поддерево является деревом поиска</font>
'''else'''
'''return''' false;
</code>
===Поиск максимального целого поддерева, являющегося деревом поиска===
Под размером дерева будем понимать количество вершин в нем. Тогда, чтобы получить решение модифицируем решение предыдущей задачи. Для каждой вершины так же будем хранить размер поддерева поиска, в котором она является корнем. Тогда получается, что для листьев он равен <tex dpi = 120> 1 </tex>, для всех остальных вершин надо проверить является ли их поддерево деревом поиска. Если да, то размер будет равен сумме размеров поддеревьев сыновей плюс один (т.к. учитываем текущую вершину), иначе <tex dpi = 120> 1 </tex>.
