Извините, я так и не понял, рекурсивную или нерекурсивную.
Ну начнём с рекурсивной. Как не залезать в листья — уже разобрались. Теперь я тут на псевдокоде напишу функцию, потому что не знаю, как промежуточное написать, и пусть меня модераторы скушают.
Код:
sum(Node^ a)
if (a = nil) or ((a^.left = nil) and (a^.right = nil))
// передали несуществующее поддерево, или попали в лист
return 0
else
// сумма составляется из «подсумм» и числа в вершине
return sum(a^.left) + sum(a^.right) + a^.value
Если теперь это надо нерекурсивным, используем, например, поиск в глубину. Понадобится стек из
Node^ и, конечно, переменная, накпаливающая сумму.
Сначала в стек положим корень дерева. Потом будем повторять одно и тоже, пока в стеке будет хоть один элемент: возьмём верхний элемент и, если он не лист, добавим число, хранящееся в нём, к сумме, а затем положим на стек вершину левого поддерева, если она не
nil, а затем вершину правого, если она тоже не
nil (можно и в обратном порядке). Собственно, может даже показаться проще, чем рекурсией.
