Кодинг
★ Рубрика: Кодинг
★ Тема: Алгоритмы

Подсчет числа вершин и листьев в дереве

Задача. Написать программу подсчета числа вершин в дереве. Решение. Рассмотрим функцию n(x), равную числу вершин в поддереве с корнем в вершине номер x. Считаем, что n(nil)=0 (полагая соответствующее поддерево пустым), и не заботимся о значениях nil(s) для чисел s, не являющихся номерами вершин. Рекурсивная программа для s такова:
function n (x:integer):integer;
 begin
 | if x = nil then begin
 | | n:= 0;
 | end else begin
 | | n:= n(l[x]) + n(r[x]) + 1;
 | end;
 end;
Число вершин в поддереве над вершиной x равно сумме чисел вершин над ее сыновьями плюс она сама. Глубина рекурсии конечна, так как с каждым шагом высота соответствующего поддерева уменьшается.

Задача. Написать программу подсчета числа листьев в дереве. Решение.
function n (x:integer):integer;
 begin
 | if x = nil then begin
 | | n:= 0;
 | end else if (l[x]=nil) and (r[x]=nil) then begin {лист}
 | | n:= 1;
 | end;
 | end else begin
 | | n:= n(l[x]) + n(r[x]);
 | end;
 end;
 Похожие публикации: Алгоритмы

Войдите, чтобы добавить Ваш ответ. [ Регистрация | Вход ]