243
правки
Изменения
→Поиск максимального поддерева, являющегося BST, в заданном двоичном дереве: 10
|definition = Найти в данном дереве максимальное из поддеревьев поиска.
}}
Будем рассматривать каждую вершину дерева, предполагая, что она может являться корнем максимального поддерева поиска. Найдём для каждой из них количество всех вершин, которые могут находиться в таком поддереве. Максимальный из результатов, получаемых на каждом шаге, будем запоминать. Вместе с максимумом будем запоминать и соответствующую ему вершину. После того, как мы обошли всё дерево и нашли корень дерева поиска с наибольшим количеством вершин, запускаем процедуру<tex>\mathrm{preorderTraversal}</tex>, выводящую все вершины на экран.
'''Node''' root()
res += dfs(v.left, max, v.left.key)
'''return''' res
[[Файл:BST_from_seq.gif|right|thumb|260px|Восстановление дерева поиска по последовательности ключей]]
