VPF::Деревья - Форум программистов

WGR

Дата 30.3.2007, 22:43 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 184
Регистрация: 6.6.2006
Где: Россия

Репутация: нет
Всего: нет

Вычислить длину внутреннего пути с помощью рекурсивной процедуры.
Дерево представить с помощью указателей.
Найти глубину дерева.

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

Код


Program d;

Const
n = 8; 

Type pt=^uzl;
uzl=Record
lson, rson: pt;
kl:byte;
End;

Var
j:word;
y:uzl;
coren:pt;


Procedure Vkl(Var cor:pt; y:uzl); 
Var
nov,ss,tt: pt;
b: Boolean;
Begin
New(nov);
nov^:= y; 
If cor = Nil Then
cor:= nov 
Else 
Begin
tt:= cor;
Repeat
ss:= tt;
b:= y.kl < ss^.kl;
If b Then
tt:= tt^.lson
Else
tt:= tt^.rson
Until tt = Nil;
If b Then
ss^.lson:= nov
Else
ss^.rson:= nov
End 
End;

BEGIN
Randomize;
coren:= Nil;
y.lson:= Nil;
y.rson:= Nil;
For j:= 1 to n do
Begin
readln(y.kl);
Vkl (coren, y) 
End;

Readln; 
END.

Это сообщение отредактировал(а) volvo877 - 30.3.2007, 23:15

--------------------

Flash ICQ Chuch@"... да как два байта отослать!!!"

volvo877

Дата 30.3.2007, 23:17 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116

Цитата(WGR @ 30.3.2007, 21:43

)

найти его глубину

Если не ошибаюсь, так:

Код


function max(a, b: integer): integer;
begin
  max := a;
  if b > a then max := b;
end;

function get_depth(T: pt): integer;
begin

  if T = nil then get_depth := 0
  else
    get_depth := max(get_depth(T^.lson) + 1, get_depth(T^.rson) + 1);

end;

(писал прямо сюда, могут быть накладки...)

Кстати, что имеется в виду под длиной дерева?

Это сообщение отредактировал(а) volvo877 - 30.3.2007, 23:17

WGR

Дата 31.3.2007, 00:17 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 184
Регистрация: 6.6.2006
Где: Россия

Репутация: нет
Всего: нет

Цитата

Кстати, что имеется в виду под длиной дерева?

это колисество рёбер между вершинами во всём дереве

тоесть дерево из 10 элементов значит рёбер (длина) 9

просто задача стоит этот порсчет реализовать рекурсивной процедуркой

А за глубину спасибо работает (+ те за это )
А то у меня сегодня КПД не больше 10% smile

--------------------

Flash ICQ Chuch@"... да как два байта отослать!!!"

volvo877

Дата 31.3.2007, 01:20 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116

Ну, если

Цитата(WGR @ 30.3.2007, 23:17

)

это колисество рёбер между вершинами во всём дереве

, то тогда вот так:

Код

procedure Count(Root: pt; var k: Integer);
begin
        if Root <> nil then begin
                inc(k);

        Count(Root^.lson, k);
                if (Root^.lson = nil) and (Root^.rson = nil) then Inc(k);
        Count(Root^.rson, k)
    end
end;

Вызывать так:

Код


i := -1;
count(Root, i);

То есть, фактически процедура Count считает число элементов, от него надо отнять 1 (тебе так понадобилось...)

WGR

Дата 31.3.2007, 02:13 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 184
Регистрация: 6.6.2006
Где: Россия

Репутация: нет
Всего: нет

Просто огромное спасибо!!!!

только тут

Цитата

procedure Count(Root: pt; var k: Integer);
begin
        if Root <> nil then begin
                inc(k);

        Count(Root^.lson, k);
             (это не надо а так всё замечательно) // if (Root^.lson = nil) and (Root^.rson = nil) then Inc(k);
        Count(Root^.rson, k)
    end
end;

и не думал что так просто в итоге будет выглядеть
Good!

--------------------

Flash ICQ Chuch@"... да как два байта отослать!!!"

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Object Pascal: кроссплатформенные технологии \| Следующая тема »