Построение дерева поиска, работа с последовательностями ("деревья") Опции

[Анна М.]

Доброго времени суток. Недавно задали нижеприведенную задачу. Очень нуждаюсь с Вашей помощи!
Заранее спасибо за данные советы и, возможно, решение.





Исходная последовательность значений читается из текстового
файла 'file_in.pas'. Файл может быть прочитан только один раз.

ВСЕ СТРУКТУРЫ ДАННЫХ ДОЛЖНЫ БЫТЬ РЕАЛИЗОВАНЫ В ВИДЕ ОБЪЕКТОВ,
(КЛАССОВ), имеющих весь "джентльменский набор" - конструкторы,
деструкторы, "полную" инкапсуляцию и др.

........................................................................
Задание:

Дана последовательность слов, составленных из символов английских
букв. Слова pазделены несколькими пpобелами. Длина любого слова не
пpевосходит 10 символов. Последовательность завеpшается сочетанием ' *'.
Постpоить для этой последовательности деpево поиска и pаспечатать его.
Напечатать слова исходной последовательности в алфавитном поpядке, указав
для каждого слова количество повтоpений. Разpешается использовать
массив из 10 символов для хpанения вводимого слова.

Пpимеp:
последовательность:
МАР РТХ ТНА КСВ РТХ КСА НЕВ КСН ТХМ ХК КСА РТХ *

деpево:

_____________________НЕВ
_________________КСА
_____________КСВ
_________________КСН
_________МАР
_____________РТХ
_____________________ТХМ
_________________ТНА
_____________________ХК

pезультат: НЕВ-1 КСА-2 КСВ-1 МАР-1 РТХ-3 ТНА-1 ТХМ-1 ХК-1

[volvo]

Ну, вот тебе набросок... Я начал переносить программу из FAQ в ООП, только не закончил еще... Попробуй продолжить...

Type
  TType = string[10];


  TTree = ^TNode;

  TNode =
    Object
      Constructor Create(s: TType);

      Data: TType;
      Count: Integer;
      Left, Right: TTree;
    End;

Constructor TNode.Create(s: TType);
Begin
  Data := s; Count := 1;

  Left := nil;
  Right := nil
End;





Procedure Add(Var T: TTree; s: TType);

Begin
  If T <> nil Then
    With T^ Do Begin

        If Data < s Then Add(Right, s)
        Else
          If Data > s Then Add(Left, s)
          Else
            Inc(T^.Count);

    End
  Else
    T := new(TTree, Create(s));
End;


Procedure Delete(T: TTree);
Begin
  If T = nil Then Exit;

  Delete(T^.Right);
  Delete(T^.Left);
  Dispose(T)
End;

Function FindNode(p: TTree; ToFind: TType): TTree;
Var pp: TTree;
Begin
  If p <> nil Then Begin
    pp := p;
    While pp <> nil Do Begin

      If ToFind < pp^.Data Then
        pp := pp^.Left
      Else
        If ToFind = pp^.Data Then Break
        Else pp := pp^.Right

    End;
    FindNode := pp
  End
  Else FindNode := nil
End;


Procedure PrintDown(T: TTree);
Begin
  If T = nil Then Exit;
  With T^ Do Begin

    Write(Data, ':', Count, ' ');
    PrintDown(Left); PrintDown(Right)

  End
End;

Procedure PrintLex(T: TTree);
Begin
  If T = nil Then Exit;
  With T^ Do Begin

    PrintLex(Left);
    Write(Data, ':', Count, ' ');
    PrintLex(Right)
  End
End;

Procedure PrintUp(T: TTree);
Begin
  If T = nil Then Exit;
  With T^ Do Begin

    PrintUp(Left);
    PrintUp(Right);
    Write(Data, ':', Count, ' ');

  End
End;


Procedure LeafsCount(T: TTree; Var k: Integer);
Begin
  If T <> nil Then Begin
    LeafsCount(T^.Left, k);

    If (T^.Left = nil) and (T^.Right = nil) Then Inc(k);
    LeafsCount(T^.Right, k)
  End
End;

Function GetNode(T: TTree): TType;
Begin
  GetNode := '';

  If T = nil Then
    writeln('Error - empty tree!')
  Else GetNode := T^.Data
End;







procedure get_words(s: string;
          var root: TTree);
const
  delimiter = [#32, '*'];
var
  count: integer;

  i, curr_len: byte;

begin
  count := -1; i := 1;
  while i <= length(s) do begin

    while (s[i] in delimiter) and (i <= length(s)) do inc(i);

    curr_len := 0;
    while not (s[i] in delimiter) and (i <= length(s)) do begin
      inc(i); inc(curr_len);
    end;

    if curr_len > 0 then begin
      Add(root, copy(s, i - curr_len, curr_len));
    end;

  end;
end;



const
  s: string = 'MAP   PTX   THA  KCB      PTX  KCA HEB  KCH   TXM  XK  KCA PTX *';

var
  root: TTree;

begin
  root := nil;
  get_words(s, root);
  printLex(root);
end.