Procedure PrintTree(tree : Node);
Begin
Write(tree^.info, ' ');
If tree^.left = Nil then PrintTree(tree^.left);
If tree^.right = Nil then PrintTree(tree^.right)
End;

Procedure PrintTree(tree : Node);
Begin
  Write(tree^.info, ' ');
  If tree^.left <> Nil then PrintTree(tree^.left);
  If tree^.right <> Nil then PrintTree(tree^.right)
End;

Program LR_3;
Type
  Node = ^Bder;
  Bder = record
    info : char;
    left, right : Node;
  end;
  
Var 
  tree : Node;
  i, N : Integer;
  info : Char;
  
{ Создание нового бинарного дерева }
Procedure NewTree(info : Char; Var tree : Node);
Var P, pr, T: Node;
Begin
  New(T);
  T^.info := info;
  T^.left := Nil;
  T^.Right := Nil;
  P := tree; Pr := Nil;
  While p <> Nil do
  Begin
    Pr := P;
    If p^.info > info then P := P^.left
    else P := P^.right;
  End;
  If tree = Nil then tree := T
  else
    If Pr^.info > info then Pr^.left := T
    else Pr^.right := T;
End;

{ Процедура обхода дерева }
Procedure PrintTree(level: integer; tree : Node);
Begin
  If tree <> nil then
    with tree^ do
    begin
      Writeln('':2*level, info);
      PrintTree(level + 1, Left);	
      PrintTree(level + 1, Right);
    end;
End;

{
  Печатаем листья, одновременно подсичтывая, сколько из них
  равны Ch
}
procedure PrintLeafs(ch: char; Tree: node; var count: integer);
begin
  if tree <> nil then
  begin
    PrintLeafs(ch, tree^.Left, count);
    if (tree^.Left = nil) and (tree^.Right = nil) then
    begin
      write(tree^.info:2);
      if ch = tree^.info then inc(count);
    end;
    PrintLeafs(ch, tree^.Right, count);
  end
end;

{ Удаление дерева }
Procedure DeleteTree(P : Node);
Begin
  If P^.left <> Nil then DeleteTree(P^.left);
  If P^.right <> Nil then DeleteTree(p^.right);
  Dispose(P);
  P := Nil;
End;

var
  counter: integer;

{ Основная программа }
Begin
  Write('Введите количество элементов дерева: '); Readln(N);
  tree := Nil;
  For i := 1 to N do
  Begin
    Write(i, ' элемент = '); Readln(info);
    NewTree(info, tree);
  End;

  If tree = nil then Writeln('Пустое дерево')
  else
  begin
    Writeln('Обход дерева:');
    PrintTree(0, tree);

    write('Введите символ (для поиска в листьях): '); readln(info);

    writeln('Листья:');
    counter := 0;
    PrintLeafs(info, tree, counter);
    writeln;

    writeln('Среди листьев найдено ', Сounter, ', равных заданному символу');

    DeleteTree(tree);
  end;
  
  Readln;
End.