Бинарные деревья поиска, Определить пути в дереве, имеющие только Опции

[FENIX]

Задание:
Дан текстовый файл. Построить дерево поиска из символов этого файла. Определить пути в дереве, имеющие только согласные буквы. Все эти вершины отметить цветом.

Моя задумка заключается в следующем: в процедуре Print сравнивать входящую информацию с инфой в массиве и, соответственно, менять цвет.
Но что-то ничего не сравнивается
Не могу понять, как сделать правильно.

Program Lab;
Uses Crt;

Const n = 19;

Alphabet : array [1..n] of String =
   ('b', 'c', 'd', 'f', 'g', 'h', 'k', 'l', 'm', 'n', 'p', 'q', 'r',
   's', 't', 'v', 'w', 'x', 'z');

Type DataType = String;

Type BTreePtr = ^BTree;

BTree = object
        Data : DataType;
        Barrier : boolean;
        Left, Right : BTreePtr;
        LLen, RLen : word;
        Constructor Init;
        Destructor Done;
        Procedure Print(K : word);
        Procedure Add_Search(D : DataType); virtual;
        {Procedure Main;}
end;

Constructor BTree.Init;
begin
   Barrier := TRuE;
end;

Destructor BTree.Done;
begin
   If not Barrier then
   begin
      Dispose(Left, Done);
      Dispose(Right, Done);
   end;
end;

Procedure BTree.Add_Search(D : DataType);
begin
   If Barrier then
   begin
      Data := D;
      Barrier := false;
      New(Left, Init);
      New(Right, Init);
   end
   else
   If D < Data then
   Left^.Add_Search(D) else Right^.Add_Search(D);
end;

============================== 

Procedure BTree.Print(K : word); 
var i : word;
begin
   If not Barrier then
   begin
      Left^.Print(k + 4);
      For i := 1 to n do
      If Data = Alphabet[i] then
      begin
         TextColor(Yellow);
      end
      else
      TextColor(7);
      writeln(Data : k);
      Right^.Print(k + 4);
   end;
end;

============================== 

var B1 : BTree;
   input : text;
   s, sl : string;
   i : word;

BEGIN
   ClrScr;
   assign(input, 'Lab_12.txt');
   reset(input);
   writeln('BEFORE - ', MemAvail, ' bytes.');
   writeln;
   B1.Init;

   While not EOF (input) do
   begin
      sl := '';
      Readln(input, s);
      If s[length(s)] <> ' '
      then s := s + ' ';
         For i := 1 to length(s) do
            If s[i] <> ' '
            then sl := sl + s[i]
            else
            If length(sl) <> 0 then
            begin
               B1.Add_Search(sl);
               sl := '';
            end;
   end;

   B1.Print(4);
   {B1.Main;}
   writeln;
   B1.Done;
   writeln('AFTER - ', MemAvail, ' bytes.');
   readln;

END.

Сообщение отредактировано: FENIX - 26.04.2005 21:24

[volvo]

Например вот так (к сожалению, пришлось переделать твое дерево)

uses crt;
const
  alpha = ['B', 'C', 'D', 'F', 'G', 'H', 'K', 'L',
           'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'V',
           'W', 'X', 'Z'];

type
  TType = char;

  PTNode = ^TNode;
  TNode = object
    Data: TType;
    right, left: PTNode;
    constructor init(T: TType);
    destructor done;
  end;

  TTree = object
    root: PTNode;

    constructor init;
    destructor done;

    procedure add(Var p: PTNode;
              T: TType);
    procedure print;

  private
    arr: array[1 .. 255] of TType;
    count: integer;
    function find_check(T: TType): string;
  end;

constructor TNode.Init(T: TType);
begin
  Data := T;
  left := nil; right := nil;
end;
destructor TNode.Done;
begin end;

constructor TTree.init;
begin
  root := nil;
  count := 0;
end;

destructor TTree.done;

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

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

begin
  Delete(root)
end;

procedure TTree.add(var p: PTNode;
          T: TType);

begin
  if p <> nil then
    with p^ do begin
      if Data < T then add(right, T)
      else
        if Data > T then add(left, T)
    end
  else new(p, Init(T))
end;


procedure TTree.print;

  procedure Indent(len: integer);
  var i: integer;
  begin
    for i := 1 to len do
      write(#32)
  end;

  procedure print_node(T: PTNode; level: integer);
  begin
    { store the leafs }
    if (T^.right = nil) and (T^.left = nil) then begin
      inc(count); arr[count] := T^.data;
    end;

    if T^.right <> nil then
      print_node(T^.right, level + 1)
    else begin
      indent(4 * (level + 1)); writeln('NIL');
    end;

    if upcase(T^.Data) in alpha then textcolor(yellow);
    indent(4 * level); writeln(T^.Data);
    textcolor(lightgray);



    if T^.left <> nil then
      print_node(T^.left, level + 1)
    else begin
      indent(4 * (level + 1)); writeln('NIL');
    end
  end;

begin
  print_node(root, 1)
end;

function TTree.find_check(T: TType): string;

var
  pp: PTNode;
  s: string;
  only_cons: boolean;
  i: integer;
begin
  s := '';
  if root <> nil then begin

    pp := root; s := root^.data;
    while pp <> nil do
      if T = pp^.data then break
      else begin
        if T < pp^.Data then pp := pp^.Left
        else pp := pp^.Right;

        s := s + pp^.data;
      end;
  end;

  only_cons := true;
  for i := 1 to length(s) do
    only_cons := only_cons and (upcase(s[i]) in Alpha);

  if only_cons then find_check := s
  else find_check := ''
end;


var
  f: text;
  tree: TTree;
  ch: char;
  i: integer;
  s: string;
begin
  assign(f, 'lab_12.txt');
  reset(f);
  tree.init;

  while not seekeof(f) do begin
    read(f, ch);
    tree.add(tree.root, ch);
  end;

  tree.print;

  for i := 1 to tree.count do begin
    s := tree.find_check(tree.arr[i]);
    if s <> '' then writeln(s);
  end;

  tree.done;
  close(f);
end.

[FENIX]

function TTree.find_check(T: TType): string;

var
  pp: PTNode;
  s: string;
  only_cons: boolean;
  i: integer;
begin
  s := '';
  if root <> nil then begin

    pp := root; s := root^.data;
    while pp <> nil do
      if T = pp^.data then break
      else begin
        if T < pp^.Data then pp := pp^.Left
        else pp := pp^.Right;

        s := s + pp^.data;
      end;
  end;

for i := 1 to tree.count do begin
    s := tree.find_check(tree.arr[i]);
    if s <> '' then writeln(s);
  end;

Вот же функция для распечатки путей, так? А нижний кусок кода - распечатка... Тогда почему у меня не печатает?
Может ли это как-нибудь быть связано с настройками самого Паскаля?

З.Ы. Я немного не понял, для чего печатать "NIL" на месте отсутствующих элементов...

Сообщение отредактировано: FENIX - 30.04.2005 16:19

[volvo]

Вот же функция для распечатки путей, так? А нижний кусок кода - распечатка...

:yes:

Тогда почему у меня не печатает?

А ты визуально проверил, есть ли пути в которых присутствуют ТОЛЬКО согласные буквы? Попробуй, например вот такой файл: "g l f k e h v r s a m t"... В нем точно есть пути только с согласными...

З.Ы. Я немного не понял, для чего печатать "NIL" на месте отсутствующих элементов... 

Я бы не называл это "отсутствующими" элементами. Просто ветка закончена... А NIL - для удобства (я так всегда делаю).