Program Tree;
Uses Crt;
{Варианты запуска обхода с подсчетом:
1 - количество вершин, имеющих хотя бы одну ненулевую связь;
2 - количество вершин, имеющих две ненулевые связи;
3 - количество вершин, имеющих не более одной ненулевой связи. }
Const AtLeastOne=1;
Two=2;
NoMoreThanOne=3;
Type inform = Integer;
ss = ^zveno;
zveno = Record
key: Integer;
inf: Inform;
left, right: ss;
End;
Var t: ss;
n,c, i: Integer;
{----формирование дерева----}
Procedure Insert (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 Insert (p^. left,x); End;
If x>=p^. inf Then Begin Insert (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 = AtLeastOne) and ( (p^. left <> Nil) or (p^. right <> Nil)))
or
{ Второй вариант - и left, и right не равны Nil }
( (v = Two) and ( (p^. left <> Nil) and (p^. right <> Nil)))
or
{ Третий вариант - либо left, либо right равны Nil }
( (v = NoMoreThanOne) 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 ('Введите количество элементов дерева: ');
Readln (n);
randomize;
For i:=1 To n Do
Begin
Writeln ('Введите элемент дерева');
Read (c);
Insert (t,c);
End;
Print (t,0);
Writeln ('Количество вершин с >= 1 ненулевой связью: ',Count (t,AtLeastOne));
Writeln ('Количество вершин с 2-мя ненулевыми связями: ',Count (t,Two));
Writeln ('Количество вершин с <= 1 ненулевой связью: ',Count (t,NoMoreThanOne));
Readkey;
End.