212
правок
Изменения
м
Под размером дерева будем понимать количество вершин в нем. Тогда, чтобы Решение этой задачи легко получить решение модифицируем решение из предыдущей задачи. Для каждой вершины так же будем хранить размер поддерева поиска, в котором она является корнем. Тогда получаетсяБудем проверять все поддеревья и из тех, что для листьев он равен <tex dpi = 120> 1 </tex>, для всех остальных вершин надо проверить является ли их поддерево окажутся деревом поиска. Если да, то размер будет равен сумме размеров поддеревьев сыновей плюс один (твыберем максимальное.к. учитываем текущую вершину), иначе <tex dpi = 120> 1 </tex>Под размером дерева подразумевается количество вершин в нем.
→Поиск максимального целого поддерева, являющегося деревом поиска
===Поиск максимального целого поддерева, являющегося деревом поиска===
====Псевдокод====
'''return''' false;
</code>
===Поиск максимального поддерева, являющегося деревом поиска===
В этой задаче нам не требуется найти целое дерево, то есть у любой в таком дереве вершины может не быть одного из поддеревьев. Тогда для решения проверку левого и правого поддеревьев надо сделать отдельно.
