Программа №3

Program derevo;

Uses Crt;

{Варианты запуска обхода с подсчетом:

1 - количество вершин, имеющих хотя бы одну ненулевую связь;

2 - количество вершин, имеющих две ненулевые связи;

3 - количество вершин, имеющих не более одной ненулевой связи. }

Const NeMensheOdnoj=1;

Dve=2;

NeBolsheOdnoj=3;

Type inform = Integer;

ss = ^zveno;

zveno = Record

key: Integer;

inf: Inform;

left, right: ss;

End;

Var t: ss;

n,nn,c, i,k: Integer;

{----формирование дерева----}

Procedure Vstavka (Var p: ss; x: Integer);

 

Begin

If p = Nil Then

 

Begin

New (p);

p^. inf: =x;

p^. key: =1;

p^. left: =Nil;

p^. right: =Nil;

 

End

else begin

If x<p^. inf Then Begin Vstavka (p^. left,x); End;

If x>=p^. inf Then Begin Vstavka (p^. right,x); End;

end;

End;

{----вывод дерева----}

Procedure Print (Var p: ss; h: Integer);

Var i: Integer;

 

Begin

If p <> Nil Then

 

Begin

Print (p^. right,h+4);

For i: =1 To h Do Write (' ');

Writeln (p^. inf);

Print (p^. left,h+4);

End;

End;

{ Рекурсивная функция, делающая подсчёт для текущего дерева }

Function Count (p: ss; v: integer): integer;

 

Begin

{ Нет элемента - результата ноль }

IF p = Nil Then Count: =0

Else Begin

{ Рассматриваются варианты вызова функции с соответствующими условием}

{ Первый вариант - либо left, либо right не равны Nil }

If ((v = NeMensheOdnoj) and ((p^. left <> Nil) or (p^. right <> Nil)))

or

{ Второй вариант - и left, и right не равны Nil }

((v = Dve) and ((p^. left <> Nil) and (p^. right <> Nil)))

or

{ Третий вариант - либо left, либо right равны Nil }

((v = NeBolsheOdnoj) and ((p^. left = Nil) or (p^. right = Nil)))

{ Какой-то из вариантов сработал => ставим 1

и добавляем результаты рекурсивных вызовов левой и правой ветви}

Then Count: =1 + Count (p^. left,v) + Count (p^. right,v)

{ Иначе берём 0 и добавляем рекурсивные вызовы }

else Count: =0 + Count (p^. left,v) + Count (p^. right,v)

End;

End;

{----обход дерева----}

Begin ClrScr;

Writeln ('Vvedite koli4estvo elementov dereva: ');

Readln (n);

randomize;

For i: =1 To n Do

 

Begin

Writeln ('Vvedite o4erednoj element');

Read (c);

Vstavka (t,c);

End;

Print (t,0);

Writeln ('Koli4estvo vershin c >= 1 nenulevoj svjazi: ',Count (t,NeMensheOdnoj));

Writeln ('Koli4estvo vershin c 2 nenulevymi svjazjami: ',Count (t,Dve));

Writeln ('Koli4estvo vershin c <= 1 nenulevoj svjazi: ',Count (t,NeBolsheOdnoj));

Readkey;

End.