UNIT TreeStorage_New;
INTERFACE

USES
  Types;

  PROCEDURE InsertInTree(Lexem: LexemType);
  FUNCTION IsTreeFull(): BOOLEAN;
  FUNCTION GetLexemCount(): INTEGER;
  PROCEDURE PrintTree(VAR F: TEXT);
  PROCEDURE DeleteTree();

IMPLEMENTATION
CONST
  DepthOfTree = 854;  {ìàêñèìàëüíîå êîëè÷åñòâî óçëîâ äåðåâà}
TYPE
  NodePtr = ^NodeType;
  NodeType = RECORD
               Key: LexemType;
               Left, Right: NodePtr;
               Count: INTEGER
             END;
  VAR
  Root: NodePtr;
  LexemCount: INTEGER;

  PROCEDURE Insert(VAR Ptr: NodePtr; Str: LexemType);
  BEGIN {Insert}
    IF Ptr = NIL
    THEN
      BEGIN {Ñîçäàåì ëèñò ñî çíà÷åíèåì Str}
        NEW(Ptr);
        Ptr^.Key := Str;
        Ptr^.Left := NIL;
        Ptr^.Right := NIL;
        Ptr^.Count := 1;
        INC(LexemCount)
      END
    ELSE
      IF Ptr^.Key > Str
      THEN
        Insert(Ptr^.Left, Str)
      ELSE
        IF Ptr^.Key < Str
        THEN
          Insert(Ptr^.Right, Str)
        ELSE
          INC(Ptr^.Count)
  END;  {Insert}                          \

  FUNCTION GetLexemCount(): INTEGER;
  BEGIN  {GetLexemCount}
    GetLexemCount := LexemCount
  END;  {GetLexemCount}

  FUNCTION IsTreeFull(): BOOLEAN;
  BEGIN {IsTreeFull}
    IsTreeFull := (LexemCount = DepthOfTree)
  END;  {IsTreeFull}

  PROCEDURE InsertInTree(Lexem: LexemType);
  BEGIN {InsertInTree}
    Insert(Root, Lexem)
  END;  {InsertInTree}

  PROCEDURE Print(Ptr: NodePtr;  VAR F: TEXT);
  BEGIN {Print}
    IF Ptr <> NIL
    THEN  {Ïå÷àòàåò ïîääåðåâî ñëåâà, âåðøèíó, ïîääåðåâî ñïðàâà}
      BEGIN
        Print(Ptr^.Left, F);
        WRITELN(Ptr^.Key, ' ', Ptr^.Count);
        Print(Ptr^.Right, F)
      END
  END;  {Print}

  PROCEDURE PrintTree(VAR F: TEXT);
  BEGIN {PrintTree}
    Print(Root, F)
  END;  {PrintTree}

  PROCEDURE Delete(Ptr: NodePtr);  {î÷èñòêà ïàìÿòè}
  BEGIN {Delete}
    IF Ptr <> NIL
    THEN  {Óäàëÿåò ïîääåðåâî ñëåâà, âåðøèíó, ïîääåðåâî ñïðàâà}
      BEGIN
        Delete(Ptr^.Left);
        Delete(Ptr^.Right);
        DISPOSE(Ptr)
      END
  END;  {Delete}

  PROCEDURE DeleteTree();  {î÷èñòêà ïàìÿòè}
  BEGIN {DeleteTree}
    Delete(Root)
  END;  {DeleteTree}

BEGIN
  Root := NIL;
  LexemCount := 0
END. {UNIT TreeStorage_New}