Бинарные деревья поиска. Помогите пожалуйста с алгоритмом решения
В бинарном дереве поиска найти максимальное поддерево с наибольшим числом вершин, в котором для каждой нелистьевой вершины число вершин в левом поддереве больше числа вершин в правом поддереве.
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Выполняем обратный обход, при котором поддеревья посещаются раньше их общего корня.
После получения размеров деревьев сравниваем их, и если левое больше правого, и оба значения неотрицательные, то сумму размеров сравниваем с текущим максимумом размера, и передаём на уровень выше.
Иначе передаём выше значение -1, что означает, что деревья в этой ветви "плохие".
Примерно так:
int Walk(Root)
if (Root==Null)
return 0
lsize = Walk(Root.left)
rsize = Walk(Root.right)
if (lsize==0 && rsize ==0)
return 1
if (lsize<0 || rsize<0 || lsize<=rsize)
return -1
size = lsize + rsize + 1
maxsize = max(maxsize, size)
return size