end;

4.2 Включение элемента в дерево

Включение элемента в дерево реализуется путем во-первых, поиска вершины √ предка нового элемента, во-вторых, непосредственным включением элемента в дерево по найденной позиции. Опишем процедуру поиска предка для нового элемента.

function SearchNode( Elem: TypeOfElem; var Tree, Result: Assoc): Boolean;

var

  ServiceVar1, ServiceVar2: Assoc;

  b: Boolean;

begin

  b:= False;

  ServiceVar1:= Tree;

  if Tree <> nil then

    repeat

      ServiceVar2:= ServiceVar1;

      if ServiceVar1^.Elem= Elem then {элемент найден} b:= True

        else begin

          {запоминание обрабатываемой вершины}

          ServiceVar2:= ServiceVar1;

          if Elem < ServiceVar1^.Elem then ServiceVar1:=

            ServiceVar1^.Left

            else ServiceVar1:= ServiceVar1^.Right

        end

    until b or ( ServiceVar1= nil );

  SearchNode:= b;

  Result:= ServiceVar2

end;

Как видно из описания, эта функция подобна ранее рассмотренной функции поиска элемента дерева (FoundInTree), но в качестве побочного эффекта фиксируется ссылка на вершину, в которой был найден заданный элемент (в случае успешного поиска), или ссылка на вершину, после обработки которой поиск прекращен (в случае неуспешного поиска). Сама процедура включения элемента в дерево будет иметь следующее описание.

procedure IncludeInTree( Elem: TypeOfElem; var Tree: Assoc );

var

  Result, Node: Assoc;

begin

  if not SearchNode( Elem, Tree, Result ) then begin

    {формирование новой вершины в дереве}

    new( Node );

    Node^.Elem:= Elem;

    Node^.Left:= nil;

    Node^.Right:= nil;

    if Tree= nil then

      {если дерево пусто, то созданный элемент сделать вершиной дерева}

      Tree:= Node

      else

        {подсоединить новую вершину к дереву}

        if  Elem < Result^.Elem then Result^.Left:= Node

          else Result^.Right:= Node

  end

end;

Двоичное дерево можно рассматривать как рекурсивную структуру данных, состоящую из корневой записи, указывающей на левое и правое поддерево. Оба поддерева имеют такую же структуру: корень поддерева и правое и левое поддеревья. При этом, для представления дерева рекурсивной динамической структурой целесообразно модифицировать описание типа дерева, данное выше. А именно, удобнее изменить тип ссылок на левое и правое поддеревья с нетипизированного (Pointer) на типизированный:

type

  TypeOfElem1= {};

  Assoc1= ^ElemOfTree1;

  ElemOfTree1= record

    Elem: TypeOfElem1;

    Left, Right: Assoc1

end;

Опишем процедуру вставки элемента рекурсивно.

procedure IncludeInTree2( NewElem: Assoc1; var SubTree: Assoc1 );

begin

  if SubTree= nil then begin

    SubTree:= NewElem;

    NewElem^.Left:= nil;

    NewElem^.Right:= nil;

  end

    else

      if NewElem^.Elem < SubTree^.Elem then

        IncludeInTree2( NewElem, SubTree^.Left )

        else

          IncludeInTree2( NewElem, SubTree^.Right )

end;

4.3 Удаление элемента дерева

Проблема реализации данной операции состоит в том, что в общем случае, в удаляемую вершину входит одна связь, а выходят две. Поэтому, необходимо найти подходящий элемент дерева, который можно было бы вставить на место удаляемого. Этот элемент является либо самым правым элементом левого поддерева (для достижения этого элемента необходимо перейти в следующую вершину по левой ветви, а затем, переходить в очередные вершины по правым ветвям до тех пор, пока очередная такая ссылка не будет равна nil), либо самый левый элемент правого поддерева (для достижения этого элемента необходимо перейти в следующую вершину по правой ветви, а затем, переходить в очередные вершины по левым ветвям до тех пор, пока очередная такая ссылка не будет равна nil). Процедура исключения элемента из двоичного дерева должна различать тои случая:

1.    элемента с заданной информативной частью в дереве нет; 2.    элемент с заданной информативной частью имеет не более одной ветви; 3.    элемент с заданной информативной частью имеет две ветви.

procedure DeleteElemOfTree( var Tree: Assoc1; Elem: TypeOfElem1 );

var

  ServiceVar1: Assoc1;

  procedure Del( var ServiceVar2: Assoc1 );

  begin

    if ServiceVar2^.Right= nil then begin

      ServiceVar1^.Elem:= ServiceVar2^.Elem;

      ServiceVar1:= ServiceVar2;

      ServiceVar2:=ServiceVar2^.Left

    end

      else Del( ServiceVar2^.Right )

  end;

begin

  {удаление элемента с информативным полем равным Elem из дерева Tree}

  if Tree= nil then

    {первый случай процедуры удаления}

    writeln( 'Элемент не найден' )

    else

      {поиск элемента с заданным ключом}

       if Elem < Tree^.Elem then DeleteElemOfTree( Tree^.Left, Elem )

         else

           if Elem > Tree^.Elem then

             DeleteElemOfTree( Tree^.Right, Elem )

             else begin

               {элемент найден, необходимо его удалить}

                ServiceVar1:= Tree;

                {второй случай процедуры удаления}

                if ServiceVar1^.Right= nil then

                  Tree:= ServiceVar1^.Left

                  else

                    if  ServiceVar1^.Left= nil then

                      Tree:= ServiceVar1^.Right

                      else

                        {третий случай процедуры удаления}

                         Del( ServiceVar1^.Left )

             end

end;

Вспомогательная рекурсивная процедура Del вызывается лишь в третьем случае процедуры удаления. Она переходит к самому правому элементу левого поддерева удаляемого элемента, а затем заменяет информационное поле удаляемого на значение поля найденного элемента.

4.4 Вывод элементов дерева

Данная задача также может быть решена с помощью механизма рекурсии.

procedure PrintTree( Tree: Pointer);

var

  ServiceVar: Assoc1;

begin

  ServiceVar:= Tree;

  writeln( ServiceVar^.Elem );

  if ServiceVar^.Right <> nil then PrintTree(ServiceVar^.Right);

  if ServiceVar^.Left <> nil then PrintTree(ServiceVar^.Left);

end;

Разберем решение типичной задачи, связанной с обработкой двоичных деревьев.

Текст задания

Описать процедуру copy( T, T1) которая строит T1 √ копию дерева T.

Решение

procedure CopyTree( T: Tree; var T1: Tree );

begin

  if T= nil then T1:= nil

    else

      begin

        new( T1 );

        T1^.Elem:= T^.Elem;

        CopyTree( T^.Left, T1^.Left );

        CopyTree( T^.Right, T1^.Right )

      end

end;

Глава II. Практическая часть

1-Задача 1. Программа «Калькулятор»

Постановка задачи. Составить программу калькулятор.

Листинг программы

program Kalkulator;

var

   M:array[1..50] of string;

   j,i,n:integer;

   s,s1,s2,s3:string;

   x,y:real;

begin

writeln('BBeDi OPeRAciy');

readln(s);

n:=length(s);

         for i:=0 to n-1 do

         begin

          M[i]:=copy(s,i,1);

          if (m[i]='+')or(m[i]='-')or(m[i]='*')or(m[i]='/') then j:=i;

     end;

s1:=copy(s,0,j-1);

s2:=copy(s,j,1);

s3:=copy(s,j+1,n);

val(s1,x,n);

val(s3,y,n);

if s2='+' then writeln(x+y:4:1);

if s2='-' then writeln(x-y:4:1);

if s2='*' then writeln(x*y:4:1);

if s2='/' then writeln(x/y:4:1);

readln;

end.

Блок-схема

Пояснение к блок-схеме