Деревья. Правильно ли работает программа!

[Skipper Ok]

Дано число N. Необходимо вычислить количество возможных двоичных деревьев, высота которых не превышает N. Каждый узел в дереве может либо не иметь ни одного потомка, либо иметь сразу двух потомков. Например, для N=1 возможно только одно дерево, состоящее из одного узла. Для N=2 возможны уже два варианта - либо дерево из одного узла, либо дерево из узла с двумя потомками. При этом высоты деревьев могут отличаться друг от друга.

uses crt;
var buf:array[1..100] of integer;
i,n:integer;
function f(n:integer):integer;
var res,i:integer;
begin
if buf[n] <> -1 then res:=buf[n] else
if n < 1 then res:=0
else if n = 1 then res:=1
else begin
res:=f(n-1);
for i:=1 to n-1 do res:=res+f(i);
end;
f:=res;
end;

begin
clrscr;
readln(n);
for i:=1 to n do begin
buf[i]:=-1;
buf[i]:=f(i);
end;
writeln(f(n));
end.

[Базиля]

Давайте начнем с условия:

Каждый узел в дереве может либо не иметь ни одного потомка, либо иметь сразу двух потомков.

Либо я чего-то не понимаю, либо же ни одно дерево с высотой от 2 и выше не будет удовлетворять данному условию.

Или все-таки допускается, что узел может иметь более 2 потомков, в таком случае это допустимо...
Но правильней было бы тогда указать в условии:

Каждый узел в дереве может либо не иметь ни одного потомка, либо иметь сразу двух потомков и более

Например, для N=1 возможно только одно дерево, состоящее из одного узла.

Да, но вы забыли про дерево с высотой 1 (по условию вашего задания ) - дерево с корнем по 1 потомку в каждом поддереве (бинарное дерево рассматриваем).

[Serge_Bliznykov]

Базиля, извините, но Вы не правы.

посмотрите теорию.
Да хоть ту же вики: Двоичное дерево

Сообщение от википедия

Двоичное дерево - древовидная структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.

[Sibedir]

f(n) = f(n-1)^2 + 1
вроде так, но не доказано.

[Базиля]

Serge_Bliznykov

Базиля, извините, но Вы не правы.
посмотрите теорию.

Если говорить о потомке, то соответственно речь уже идет о потомстве. И любой узел, расположенный ПОД исходным узлом - есть его потомок

А если мы уже говорим о ребенке/сестре/брате, то здесь уже подразумеваем именно ПРЯМОЕ отношение к родительскому узлу и ни к какому иначе.

[Serge_Bliznykov]

Сообщение от Базиля

Serge_Bliznykov

Если говорить о потомке, то соответственно речь уже идет о потомстве. И любой узел, расположенный ПОД исходным узлом - есть его потомок

А если мы уже говорим о ребенке/сестре/брате, то здесь уже подразумеваем именно ПРЯМОЕ отношение к родительскому узлу и ни к какому иначе.

Т.е, Вы хотите сказать, что определение на википедии дано неверно?!

[Базиля]

Нужно только определиться с понятием "потомок" в данном контексте.
Вы считаете что я не прав?

[Serge_Bliznykov]

Сообщение от Базиля

Нужно только определиться с понятием "потомок" в данном контексте.
Вы считаете что я не прав?

согласен.
Только вот значение "потомок" в исходном посте TC совпадает со значением в определении (на вики, например): - это только "дети" (внуки и правнуки не участвуют в данном случае).

[Poma][a]

Базиля, извините, но Вы не правы.

Я за Базилю. Перед тем, как давать такое задание(на форуме) стоит четко определить что понимает ТС или его препод под терминами из условия..

8Реферат: Представление бинарного дерева в виде массива - Xreferat.ru...
Сыновья узла и сыновья их сыновей называются потомками (descendants), а родители и прародители – предками (ancestors) этого … Д. Кнут Искусство программирования для ЭВМ. Т1, Основные алгоритмы. … Понятие достижимости в теории графов, их математические свойства.
xreferat.ru›54/2450-1-predstavlenie-binarnogo-… копия ещё

уж простите за то, что в таком виде.. На планшет не очень удобен для таких дел

О самой задаче : очевидно, что тут будет рекурентная формула.. А вот какая - надо думать.

[Poma][a]

О решении : для начала я вынужден не согласиться с ТС. Для N = 2 возможны три варианта : один корень, корень и еще одна вершина, соединенная с ним, и полное бинарное дерево..

Далее.. Пусть у нас есть решения для i-той высоты. Тогда найдем решение для i+1. Это будут все решения для i + построим такое дерево : у каждого узла только один сын. И таких узлов ровно i. Теперь будем прибавлять к каждой вершине, начиная с корня, еще одного такого сына. Таким макаром мы добавим еще i+1 вариант.
И тогда решением будет сумма от i = 1 до n самих i. (А теперь запихнем это в арифметическую прогрессию. И получим (n+1)*n/2