Изменения

==Задачи о деревьях бинарном дереве поиска и произвольных двоичных деревьях==

'''1 шаг.''' Проверяем, есть ли у вершины левый сын. Если его нет, переходим к пункту 2, иначе сравниваем значения в этой вершине и в её левом потомке, а также значение в левом сыне с максимумом в поддереве. Если значение в левом сыне меньше, чем значение в вершине и больше переменной <tex>max</tex>, то запускаем <tex>dfs</tex> из левого сына. Здесь роль <tex>v </tex> будет разыгрывать <tex>v.left</tex>, <tex>max</tex> приобретёт значение <tex>v.key</tex>, <tex>min</tex> по-прежнему останется <tex>min</tex>, а <tex>res</tex> увеличится на <tex>1</tex>. ''Пояснение:'' ключи вершин левого поддерева не должны превосходить значения в рассматриваемой вершине, поэтому мы изменяем <tex>max</tex>. На <tex>min</tex> эта вершина не влияет в случае левого поддерева, поэтому он не изменяется. <tex>res</tex> увеличивается на <tex>1</tex>, так как в наше поддерево добавилась ещё одна вершина.

'''2 шаг.''' Аналогично действуем с правым потомком. Проверяем его наличие. Если он существует, то сравниваем значение в нём с минимумом и с ключом вершины. Если значение правого сына больше минимума в поддереве и меньше значения в вершине, то запускаем от потомка <tex>dfs</tex>. Теперь на место <tex>v</tex> встаёт <tex>v.right</tex>, <tex>max</tex> остаётся прежним, <tex>min</tex> становится ключом в рассматриваемой вершине, а <tex>res</tex> снова увеличивается на <tex>1</tex>. Для случая с правым поддеревом рассуждения аналогичны.