На этом шаге мы приведем общие сведения о произвольных деревьях с размеченными листьями.

Теперь мы можем ввести общее понятие дерева с размеченными листьями. Бинарные деревья с размеченными листьями - их частный случай.

Примем следующее определение:

Дерево с размеченными листьями - это последовательность ветвей, причем ветвь - это

либо объект базового типа,
либо дерево с размеченными листьями.

В языке Pascal тип данных "произвольные деревья с размеченными листьями" не предусмотрены, однако мы можем построить инкапсулированный тип данных с этим именем.

Для этого вначале в соответствии с рекурсивным определением произвольного дерева с размеченными листьями мы получаем следующее описание типа [1, т.2, с.393-394,439-443]:

   type  Tree   = ^PlexEl;
         PlexEl =  Record
                      O: Tree;
                      Case Atomic: Boolean of
                        TRUE : (Atom: Char);
                        FALSE: (F   : Tree)
                   End;

Учтите, что в версии TURBO Pascal существуют ограничения: запись может содержать не более одной вариантной компоненты, и эта компонента должна быть последней в записи.

Названия полей произошли от:

F - "First branch" ("Первая ветвь");
O - "Other branches" ("Остальные ветви").

Функции-конструкторы, необходимые для построения произвольного дерева с размеченными листьями реализуются следующим образом [1,т.2,с.439-443]:

   FUNCTION  E_m_p_t_y_T_r_e_e : Tree;
   { Построение пустого дерева }
   BEGIN
      E_m_p_t_y_T_r_e_e := Nil
   END;
  { --------------------------------------------- }
   FUNCTION  A_p_p_e_n_d (C: Char; B: Tree): Tree;
   { Добавление "листа" C к дереву B }
      var  h: Tree;
   BEGIN
      New (h); h^.Atomic := TRUE; h^.Atom := C; h^.O := B;
      A_p_p_e_n_d := h
   END;

Иллюстрируем графически действие функции A_p_p_e_n_d('C',B):

Рис.1. Результат функции A_p_p_e_n_d('C',B)

   FUNCTION  J_o_i_n (A: Tree; B: Tree): Tree;
   { Соединение деревьев A и B с образованием общего корня }
      var  h: Tree;
   BEGIN
      New (h); h^.Atomic := FALSE; h^.F := A; h^.O := B;
      J_o_i_n   := h;
   END;

Иллюстрируем графически действие функции J_o_i_n (A,B):

Рис.2. Результат функции J_o_i_n (A,B)

Терм для составленного из объектов A,B,C,D,E,F дерева с размеченными листьями

Рис.3. Терм

имеет вид:

   L := A_p_p_e_n_d (A,A_p_p_e_n_d (B,
           J_o_i_n (
                     A_p_p_e_n_d (C,E_m_p_t_y_T_r_e_e),
                     A_p_p_e_n_d (D,A_p_p_e_n_d (E,
                     A_p_p_e_n_d (F,E_m_p_t_y_T_r_e_e)))
                   )
        ))

Пример 1.

   PROGRAM  L_I_S_P_A_S;    {$A-}
  { Построение терма и вывод его на экран дисплея }
      type  TipElement = Char;
            Tree   = ^PlexEl;
            PlexEl =  Record
                         O: Tree;
                         Case Atomic: Boolean of
                            TRUE : (Atom: TipElement);
                            FALSE: (F   : Tree)
                      End;
      var   Ukaz0,Ukaz1,Ukaz2,Ukaz3,Ukaz4,Ukaz5,Ukaz6: Tree;
            Root: Tree;
  { ----------------------------------------- }
   FUNCTION  J_o_i_n (A: Tree; B: Tree): Tree;
   { Соединение деревьев A и B с образованием общего корня }
      var  h: Tree;
   BEGIN
      New (h); h^.Atomic := FALSE; h^.F := A; h^.O := B;
      J_o_i_n   := h;
   END;
  { --------------------------------------------------- }
   FUNCTION  A_p_p_e_n_d (C: TipElement; B: Tree): Tree;
   { Добавление "листа" C к дереву B }
      var  h: Tree;
   BEGIN
      New (h); h^.Atomic := TRUE; h^.Atom := C; h^.O := B;
      A_p_p_e_n_d := h
   END;
  { --------------------------------- }
   FUNCTION  E_m_p_t_y_T_r_e_e : Tree;
   BEGIN
      E_m_p_t_y_T_r_e_e := Nil
   END;
  { ---------------------------------------------------- }
   PROCEDURE  P_r_i_n_t_T_r_e_e (Root: Tree; l: Integer);
   { Вывод бинарного дерева Root на экран дисплея }
      var  i: Integer;
   BEGIN
      If  Root^.Atomic
         then  begin
                  If  Root^.O<>Nil
                     then  P_r_i_n_t_T_r_e_e (Root^.O,l)
                     else;
                  For i:=1 to l do  Write ('   ');
                  Writeln (Root^.Atom)
               end
         else  begin
                  If  Root^.O<>Nil
                     then  P_r_i_n_t_T_r_e_e (Root^.O,l)
                     else;
                  P_r_i_n_t_T_r_e_e (Root^.F,l+1);
                  For i:=1 to l do  Write ('   ');
                  Writeln ('#')
               end
   END;
  { --- }
   BEGIN
      Writeln ('Построим два дерева с размеченными листьями... ');
      Writeln ('---------------------------------------------- ');
      Ukaz0 :=  A_p_p_e_n_d ('F',E_m_p_t_y_T_r_e_e);
      Ukaz1 :=  A_p_p_e_n_d ('E',Ukaz0);
      Ukaz2 :=  A_p_p_e_n_d ('D',Ukaz1);
      Ukaz3 :=  A_p_p_e_n_d ('K',E_m_p_t_y_T_r_e_e);
      Ukaz4 :=  A_p_p_e_n_d ('C',Ukaz3);
      Ukaz6 :=  J_o_i_n     (Ukaz4,Nil);
      Ukaz5 :=  J_o_i_n     (Ukaz2,Ukaz6);
      Ukaz1 :=  A_p_p_e_n_d ('B',Ukaz5);
      Ukaz0 :=  A_p_p_e_n_d ('A',Ukaz1);
      P_r_i_n_t_T_r_e_e (Ukaz0,0); Writeln;
      Writeln ('---------------------------------------------- ');
      Ukaz0 :=  A_p_p_e_n_d ('F',E_m_p_t_y_T_r_e_e);
      Ukaz1 :=  A_p_p_e_n_d ('E',Ukaz0);
      Ukaz2 :=  A_p_p_e_n_d ('D',Ukaz1);
      Ukaz3 :=  A_p_p_e_n_d ('K',E_m_p_t_y_T_r_e_e);
      Ukaz4 :=  A_p_p_e_n_d ('C',Ukaz3);
      Ukaz5 :=  J_o_i_n     (Ukaz2,Ukaz4);
      Ukaz1 :=  A_p_p_e_n_d ('B',Ukaz5);
      Ukaz0 :=  A_p_p_e_n_d ('A',Ukaz1);
      P_r_i_n_t_T_r_e_e (Ukaz0,0); Writeln
   END.

Текст этой программы можно взять здесь.

Тестовый пример:

Построим два дерева с размеченными листьями...

   ----------------------------------------------
      K
      C
   #
      F
      E
      D
   #
   B
   A
   ----------------------------------------------
   K
   C
      F
      E
      D
   #
   B
   A

Полученные результаты можно графически изобразить так:

Рис.4. Графическая интерпретация

Следующая программа показывает, как можно список языка LISP, вводимый с клавиатуры, преобразовать в дерево с размеченными листьями.

Пример 2.

   PROGRAM  L_I_S_P_A_S;    {$A-}
  { Представление списка LISP в виде произвольного дерева с }
  {                 размеченными листьями                   }
      type  TipElement = Char;
            Tree       = ^PlexEl;
            PlexEl     =  Record
                             O: Tree;
                             Case Atomic: Boolean of
                                TRUE : (Atom: TipElement);
                                FALSE: (F   : Tree)
                          End;
            Q          = String [23];
      var   Root: Tree; { Полученное дерево с размеченными }
                        {            листьями              }
            List: Q;    { Вводимый список LISP             }
            i   : Integer;
  { --------------------------------- }
   PROCEDURE  E_n_t_e_r (var T: Tree);
   { Построение дерева, соответствующего списку LISP }
      var  X: TipElement;
   BEGIN
      X := List[i]; i := i + 1;
      If  X<>'.'
         then  begin
         { Помещаем элемент X лисповского списка в дерево }
                  If  X='('
                     then  begin
                              New (T); T^.Atomic := FALSE;
                              E_n_t_e_r (T^.F);
                              E_n_t_e_r (T^.O)
                           end
                     else  If  (X IN ['A'..'z'])
                              then  begin
                                       New (T);
                                       T^.Atomic := TRUE;
                                       T^.Atom := X;
                                       E_n_t_e_r (T^.O)
                                    end
                              else  If  X=')'
                                       then  T := Nil
               end
   END;
  { ---------------------------------------------------- }
   PROCEDURE  P_r_i_n_t_T_r_e_e (Root: Tree; l: Integer);
   { Вывод произвольного дерева с размеченными листьями }
      var  i: Integer;
   BEGIN
      If  Root^.Atomic
         then  begin
                  If  Root^.O<>Nil
                     then  P_r_i_n_t_T_r_e_e (Root^.O,l)
                     else;
                  For i:=1 to l do  Write ('   ');
                  Writeln (Root^.Atom)
               end
         else  begin
                  If  Root^.O<>Nil
                     then  P_r_i_n_t_T_r_e_e (Root^.O,l)
                     else;
                  P_r_i_n_t_T_r_e_e (Root^.F,l+1);
                  For i:=1 to l do  Write ('   ');
                  Writeln ('#')
               end
   END;
  { --- }
   BEGIN
      Writeln ('Построим дерево с размеченными листьями ');
      Writeln ('по заданному лисповскому списку... ');
      Writeln
      ('Вводите список LISP без пробелов между атомами. ');
      Writeln
      ('Последним символом должен быть символ "."...');
      Read (List);
      i := 1; Root := Nil;
      E_n_t_e_r (Root); Writeln;
      P_r_i_n_t_T_r_e_e (Root,0); Writeln
   END.

Текст этой программы можно взять здесь.

Тестовый пример:

   Построим дерево с размеченными листьями
   по заданному лисповскому списку...
   Вводите лисповский  с п и с о к...
   (CU((KE)N)(G(I(T)))).
               T
            #
            I
         #
         G
      #
         N
            E
            K
         #
      #
      U
      C
   #

Замечания.

Рассмотрим реализацию остальных операций над произвольными деревьями с размеченными листьями:

   FUNCTION  I_s_E_m_p_t_y_T_r_e_e (A: Tree): Boolean;
   BEGIN
      I_s_E_m_p_t_y_T_r_e_e := A=Nil
   END;
  { --------------------------------------- }
   FUNCTION  I_s_A_t_o_m (A: Tree): Boolean;
   { NOT I_s_E_m_p_t_y_T_r_e_e (Tree) }
   BEGIN
      I_s_A_t_o_m := A^.Atomic
         { AND  I_s_E_m_p_t_y_T_r_e_e (A^.O) }
   END;
  { ---------------------------------------------- }
   FUNCTION  F_i_r_s_t_B_r_a_n_c_h (A: Tree): Tree;
      { NOT I_s_E_m_p_t_y_T_r_e_e (A) AND
        NOT I_s_A_t_o_m (A) }
   BEGIN
      F_i_r_s_t_B_r_a_n_c_h := A^.F
   END;
  { -------------------------------------------------- }
   FUNCTION  O_t_h_e_r_B_r_a_n_c_h_e_s (A: Tree): Tree;
   { NOT I_s_E_m_p_t_y_T_r_e_e (A) }
   BEGIN
      O_t_h_e_r_B_r_a_n_c_h_e_s := A^.O
   END;
  { ---------------------------- }
   FUNCTION  VAL (A: Tree): Char;
   { I_s_A_t_o_m (a) }
   BEGIN
      VAL := A^.Atom
   END;

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

⁽¹⁾ Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс: В 2-х ч. Ч.1. пер. с нем. - М.: Мир, 1990. - 336 с.; Ч.2. пер. с нем. - М.: Мир, 1990. - 423 с.

Со следующего шага мы начнем рассматривать взаимосвязь языков LISP и LOGO.

Предыдущий шаг Содержание Следующий шаг