Подсчёт узлов двоичного дерева рекурсивной функцией

[Gamover jr]

Помогите, пжлст, найти ошибку.
Turbo Pascal 5.5



type
tRefBinTree = ^tBinTree;
tBinTree = record
info : integer;
left : tRefBinTree;
right : tRefBinTree;
end;

function Nodes (inRefRoot : tRefBinBauTree) : integer;
begin
if (inRefRoot <> nil) then
writeln(inRefRoot^.info); правильно выводит все содержащиеся в дереве числа
Nodes := 1 + Nodes(inrefRoot^.left) + Nodes(inrefRoot^.right) Возвращает разные большие отрицательные числа, -6ххх и др.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
end
end;

[BlackEric]

Возможно здесь имеет место переполненение типа попробуйте использовать больший тип. Word или что-там было в TP 5.5. Уже не помню

[ivank]

function Nodes (inRefRoot : tRefBinBauTree) : integer;
begin
if (inRefRoot <> nil) then
Nodes := 1 + Nodes(inrefRoot^.left) + Nodes(inrefRoot^.right)
else
Nodes := 0;
end;

[Gamover jr]

Ещё вопрос. Насколько оправдано применение рекурсии для подсчёта количества элемнтов в двоичном дереве?
Я правильно понимаю, что в какойто момент будет создано столько же экземпляров функции Nodes, сколько в дереве элементов? Если это так, тогда есть вероятность перепонения стека, если дерево окажется достаточно большим?

Если рекурсия не подходит, то как можно посчитать количество элементов?

[ivank]

Gamover jr, Понимаете почти правильно. Глубина вызовыво будет соответствовать высоте дерева (которая может быть равна числу элементов, если дерево ну очень несбалансированное).

Если дерево надо обойти в ширину, то нужно применять очередь. (помещаете в качестве первого элемента тот, который будете обходить, затем в цикле, пока очередь непуста, берёт из неё элемент и кладёте в неё всех его детей). Аналогично, если нужен обход в грубину, то можно применить стек.

[Gamover jr]

Если дерево сбалансированное, то для подсчёта элементов предпочтительней рекурсивная функция?

Если высота полность сбалансированного двоичного дерева составляет для примера (корень + 13) = всего 11111111111111b элементов в дереве = 16383 ?

В таком случае будут загружены 14 экземпляров фунции Node? Это приемлемо?

Поскольку в дереве хранятся значения типа integer, в моём конкретном случае только числа от 0 до 32767 = корень + 14 = 15 экземпляров функции Nodes.

Какая глубина вызова ещё приемлема, а при какой лучше от рекурсии отказаться?

[ivank]

Gamover jr, зависит от того где и как вы всё запускаете. Обычно стек не меньше мегабайта - тысячи вложенных вызовов в него легко влезут. А ещё сегмент стека часто умеет динамически расти. Но в любом случае, даже в досе с его ограничением на 64кб стека, такую лёгкую функцию как Nodes можно вызывать сотни раз.