243
правки
Изменения
→Поиск максимального поддерева, являющегося BST, в заданном двоичном дереве
maxdp = dp
maxroot = u
dfsPrint(maxroot,-INF,INF)
'''1 шаг.''' Проверяем, есть ли у вершины левый сын. Если его нет, переходим к пункту 2, иначе сравниваем значения в этой вершине и в её левом потомке, а также значение в левом сыне с максимумом в поддереве. Если значение в левом сыне меньше, чем значение в вершине и больше переменной <tex>max</tex>, то запускаем <tex>dfs</tex> из левого сына. Здесь роль v будет разыгрывать <tex>v.left</tex>, <tex>max</tex> приобретёт значение <tex>v.key</tex>, <tex>min</tex> по-прежнему останется <tex>min</tex>, а <tex>res</tex> увеличится на 1. ''Пояснение:'' ключи вершин левого поддерева не должны превосходить значения в рассматриваемой вершине, поэтому мы изменяем <tex>max</tex>. На <tex>min</tex> эта вершина не влияет в случае левого поддерева, поэтому он не изменяется. <tex>res</tex> увеличивается на 1, так как в наше поддерево добавилась ещё одна вершина.
'''3 шаг.''' Возвращаем результат в переменной <tex>res</tex>, где записано количество вершин поддерева.
[[Файл:BST_in_Tree.gif|centre|Пример выполнения процедуры dfs (из корневой для вершины дерева)с номером 7]]
Процедура обхода дерева представлена ниже:
