Рекурсия для подсчета числа вершин

Рейтинг: 0Ответов: 1Опубликовано: 22.01.2015

Помогите написать рекурсивную функцию Level(T,n) для подсчёта числа вершин на n-м уровне дерева T (считать, что 1-й уровень соответствует корню дерева, а уровень любой другой вершины – на единицу больше уровня её родительской вершины).

Вот часть моего кода:

type tree=^node;
node=record elem:integer;
left,right:tree;
end;  
function Level(T: tree; n: integer): integer; {n>=1}
begin if T=nil then Level:=0 else {непустое дерево:}
 if n=1 then Level:=1 else {общий случай:}

А вот для общего случая я написать не могу.
Помогите, пожалуйста.
Если можно, с объяснениями.

дерево pascal
Источник: Stack Overflow на русском

Ответы

▲ 1
function Level(T: tree; n: integer): integer; {n>=1}
begin
  if T = nil then // вершины нет, результат нулевой
    Result := 0 // Result тоже, что и Level
  else // вершина есть, смотрим дальше
    if n = 1 then  // это вершина нужного нам уровня
      Result := 1  // добавим 1 к количеству вершин
    else {общий случай:} // до нужного уровня еще не добрались, ныряем дальше
  // посмотрим сколько есть вершин нужного нам уровня в каждой из веток текущего узла
      Result := Level(T^.left, n - 1) + Level(T^.right, n - 1); // n уже на 1 уровень меньше
end;