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

BlackEric · Отправлено: **23:19, 10-11-2007** | #2

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

ivank · Отправлено: **02:06, 11-11-2007** | #3

Код:

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

Gamover jr · Отправлено: **13:11, 11-11-2007** | #4

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

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

ivank · Отправлено: **14:41, 11-11-2007** | #5

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

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

Gamover jr · Отправлено: **15:55, 11-11-2007** | #6

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

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

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

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

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

ivank · Отправлено: **18:15, 11-11-2007** | #7

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