Help Binary Search Tree

Please (if you are able to) write a program thaty maintains information on NHL hockey teams as a double binary search tree. The main tree should hold the names of the teams, while the sub-tree holds the names of the players.(See diasgram below)


                  Canadiens
                  /     |     \
            Bruins    Roy    Maple Leafs
               |        \          |
            Neely          Savage    Gilmour
                                \
                              Momesso

The program should do the following:

a) Read in the initial data, given bellow as 15 lines, each with a team name followed by a player's name
b) Insert the players and teams into a double binary search tree as described above.
c) Read in a series of ten more lines of data (also given below), consisting of an action followed by one or more team or player names. For 'Trade' the two players given should swap teams within the tree. For 'CUT' the player should be deleted from the team name given. If this player does not exist print out an errror message. For 'ADD' the player should be added to the team name given. If the team does not exist in the tree it should be added. Finally, for, PRINT, all the teams along with their corresponding players should be printed out in alphabetical order.

DATA

Bruins Neely
Sabres Galley
Blues Noonan
MapleLeafs Gartner
Blues Wells
Canucks Bure
Sabres Peca
Sabres Huddy
Bruins Zombo
Islanders Beers
MapleLeafs Gill
Blues Hull
Canucks Courtnall
Bruins Oates
Stars Modano




ADD BRUINS ELIK
ADD CAPITALS PEAKE
CUT ISLANDERS BEERS
ADD BLUES PRONGER
CUT STARS REICH
CUT STARS MODANO
TRADE SABRES PECA MAPLELEAFS GILL
ADD CANUCKS BROWN
CUT CANUCKS BURE
TTRADE BLUES WELLS SABRES TALIA
PRINT
mihai031697Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

mihai031697Author Commented:
Please forward an answer(hopefully a working one) to
<bver@hotmail.com>
Thanks a lot

M.
0
julio011597Commented:
No homework assignments will be welcome here, i'm afraid.
At least, try to do it yourself, then post on the _programming_ problems you're unable to solve.

Good luck, julio
0
pprikrylCommented:
I agree with julio :-) Anyway, learn about dynamic allocation of variables (new, dispose, pointers). Then learn about the abstract data structures (record with the key and contents and two pointers as a node of the binary tree). Then learn something about binary tree traversal -- a recursive procedure can be very useful here. Then you should learn about parsing the input text and convert it into calls of your abstract operation on the three (like insert node, delete node, traverse in-order -- for print). And then you simply put it together.
0
Cloud Class® Course: SQL Server Core 2016

This course will introduce you to SQL Server Core 2016, as well as teach you about SSMS, data tools, installation, server configuration, using Management Studio, and writing and executing queries.

mihai031697Author Commented:

0
pprikrylCommented:
...by the way, "Write a program" is hardly a question ;-)
0
mihai031697Author Commented:
Hey  pprikryl...,
I know 'Write a programm ' is not question . It might sound like..
I just pasted the requirement. I don't have to hide the fact that , indeed , it is an asssignment.
BTW I already have most of it( Level 2-3 ) algorithms; but when I try to code and compile it I keep getting lots of errors
That's why I asked for help. I helped myself lots of people ( not in this section of exp-exchange) so I expected others to do the same. But I guess this area is not that popular... Anyways the assignment is due tomorrow I hope I'll finish it and
Good luck here in the Pascal corner of the Ex-Exc.
0
mihai031697Author Commented:
Edited text of question
0
mihai031697Author Commented:
Edited text of question
0
FordreamCommented:
Actually I can't understand what you want. You said that tree you wrote is double binary tree. But binary tree is a tree that each node has at most two child nodes. In your tree, there even three nodes connected to a node! I think it is not binary tree. and second, you said that main tree should hold the names of the teams(Does main tree stand for nodes thats deep is 1? Like Bruins, Roy, Maple leafs in your tree?) and sub-tree holds the player names. Then what is a node thats deep is 3? is "Momesso" is a team name? or a player's name? or what? I can make program that operates commands you said - ADD, CUT, and TRADE. but I can't understand what you want. The operation is done without tree. The problem has no relation about tree. Please describe more detailedly if you want program code. (Maybe there is no time?, But I can give you code whenever if you want)
 Bye
0
pprikrylCommented:
Hi mihai. I know exactly your situation as I am a teacher in a course like that one you are just attending :-) Then you should not expect that I will write a program for you. I also do not like when my students solve the problem this way or paying the other one some beers. What I always say to my students is, "think about the problem with pen and paper in your hand -- you will understand the problem better and you will solve it much quicker" (it does not seem to be true at the first look, but it is). Then you should build your program from simple and working blocks. You should never write the whole source text just to avoid the situation that you can see 50 errors at the beginning.  
0
mihai031697Author Commented:
Hey Foredream,
You are probably confused because the figure appearing here on this page is not what I've posted. When I write it in a text editor (Notepad) looks different. That is the is double because besides the regular tree with three fields:two pointers to the nex ttwo other, and the info field, it has another pointer to a new pointer to a new binary tree holding the players...
Is easier if you see the correct picture. If you want to help me why don't you give me an address where I could send you the correct picture and if you need the code I got so far
Thanks a lot
Mihai
0
mittalk033197Commented:
If you increase the points to 250 I will
write you a sample program to do
what you want. You have allocated too few points for wanting a complete complex binary treee program.
0
mihai031697Author Commented:
OK mittalk
You got all my points. I'll have to answer lots of questions to get them back..!
But can you do it until Wednsday April 2, evening?
Today is already Apr !st...

0
mihai031697Author Commented:
Adjusted points to 245
0
mittalk033197Commented:
sure...I'll have it done and posted here by then. No probs. !!
0
mittalk033197Commented:
Here goes the program u wanted !!

program Dict;
(* simple dictionary using a btree.
  The program reads in an ASCII file with one word per line and stores the
  words in an btree. A btree is something like binary tree but every node
  can have more than two descent nodes. This is done by linked list.

  This method has two advantages:
    * when a word is wrong you can easily give some proposes how the word
      is written correctly (just change the path in the tree a little)
    * bigger dict. may save space. E.g "base, basicly, basement" etc.
      share the same path on the first three niveaus.

  ATTENTION! I don't free any mem I've allocated. This is done by the
  heap manager (i.e. he allocates large blockes and releases them } when
  the program ends. But this can be added easily.

  Also, there is no function included that deletes words (I don't need it in
  my project). I suggest it is not that easy to add such a function but
  have a try ;-))

*)

{ $DEFINE DEBUG} { if DEBUG is defined (just erase space between "{" and "$")
                   then some actions are logged while building the tree and
                   while searching. }

const debugfile = 'dict.log';     { log file (if needed) }
      dictFileName = 'dict.dat';  { data input (words in ASCII) }

type  PNode     = ^TNode;
      TNode     = record
                    Character : Char;    { the current character }
                    WordEnd   : Boolean; { is this char. the last of one word?}
                    right,down: PNode;   { right: points to next char on the
                                                  same niveau
                                           down : points to the next char in
                                                  word }
{$IFDEF DEBUG}
                    Level     : byte;    { level of the tree }
{$ENDIF }
                  end;

var BTree: PNode;                       { our tree }
    DictFile: Text;                     { our ascii dictionary }
{$IFDEF DEBUG}
var f: Text;                            { log file handle }
{$ENDIF }


procedure CreateBTree;
{ just initalizes the tree w/ a dummy element }
begin
  Btree:=NIL;
  New(Btree);
  BTree^.character:=#$1A; { #$1A is END-OF-FILE. shouldn't be used in any word }
  BTree^.right:=NIL;
  Btree^.down:=NIL;
  BTree^.Wordend:=true;
{$IFDEF DEBUG}
  BTree^.level:=1;
  writeln(f,'B-Tree with dummy element created.');
{$ENDIF }
end;

{$IFDEF DEBUG}
function GetNode(Character: Char; LevelPtr: PNode; Level: byte): PNode;
{$ELSE }
function GetNode(Character: Char; LevelPtr: PNode): PNode;
{$ENDIF }
{ returns the node in Level "LevelPtr" that contains "Character".
  if there is no node, it is created }
var p: PNode;
begin
  if levelptr=NIL then begin
    New(P);
    P^.right:=NIL;
    P^.down:=NIL;
    P^.character:=character;
    P^.WordEnd:=False;
{$IFDEF DEBUG}
    P^.Level:=Level;
    writeln(f,'#New niveau-node enterd. Content of the first node: '+
            ' "',character,'". Level ',level);
{$ENDIF }
    GetNode:=p;
  end else begin
    p:=levelptr;
    while (p^.right<>NIL) and (p^.character<>Character) do p:=p^.right;
    if p^.character=character then
    begin
      getnode:=p;
{$IFDEF DEBUG}
      writeln(f,'Node "',character,'" found on level ',level,'.');
{$ENDIF }
    end
      else begin
        { p^.right is NIL! }
        new(p^.right);
        p:=p^.right;
        p^.character:=character;
        p^.right:=NIL;
        p^.down:=nil;
        p^.wordend:=false;
{$IFDEF DEBUG}
        p^.level:=level;
        writeln(f,'#Entered new node. Content "',character,'". Level ',level);
{$ENDIF }
        GetNode:=p;
      end; {if}
  end; { if }
end;

procedure InsertWord(wort: string);
{ inserts the word "wort" into btree }
var p1,p2,p3: PNode;
    i: byte;
begin
  if wort='' then exit;
  p2:=btree;
  for i:=1 to length(wort) do
  begin
{$IFDEF DEBUG}
    p1:=getnode(wort[i],p2,i);
{$ELSE}
    p1:=getnode(wort[i],p2);
{$ENDIF}
    if p2=NIL then p3^.down:=p1;
    p3:=p1;
    p2:=p1^.down;
  end;
  p1^.wordend:=true;
{$IFDEF DEBUG}
  writeln(f,'Wort "',wort,'" eingetragen.');
{$ENDIF }
end;

function ProofWord(Wort: string): boolean;
{ returns true if "wort" is in our dictionary }
var P1,p2: PNode;
    I: Byte;
begin
  ProofWord:=FALSE;
  if wort='' then exit;
  p1:=BTree;
  i:=1;
{$IFDEF DEBUG}
  writeln(f,'Searching for word "',wort,'".');
{$ENDIF }
  while (p1<>NIL) and (length(wort)>=i) do begin
    while (p1^.right<>NIL) and (p1^.character<>wort[i]) do p1:=p1^.right;
    if p1^.character=wort[i] then begin
      inc(i);
      p2:=p1;
      p1:=p1^.down;
{$IFDEF DEBUG}
      writeln(f,'Character "',wort[i-1],'" found on level ',i-1,'.');
{$ENDIF }
    end else p1:=NIL;
  end;
  if (i=length(wort)+1) and (p2^.wordend) then proofword:=TRUE;
end;


var OldExitProcPtr: Pointer;

procedure MyExitProc;far;
begin
  ExitProc:=OldExitProcPtr;
  if exitcode = 214 then writeln('Huston! We''ve got a pointer problem!');
{$IFDEF DEBUG}
  close(f);
{$ENDIF }
end;

var s: String;

begin
  OldExitProcPtr:=ExitProc;
  ExitProc:=@MyExitProc;
  {$IFDEF DEBUG}
  assign(f,debugfile);
  rewrite(f);
  {$ENDIF }
  assign(dictfile,dictfilename);
  createBTree;
  reset(dictfile);
  write('Reading dictionary...');
  while not eof(dictfile) do
  begin
    readln(dictfile,s);
    insertword(s);
  end;
  writeln('done.');
  writeln('Request mode. End with "END"!');
  s:='';
  repeat
    write('OK>');
    readln(s);
    if s<>'END' then
      if proofword(s) then writeln('Word found!',#7)
                      else writeln('Word not fond!');

  until s='END';
  {$IFDEF DEBUG}
  close(f);
  {$ENDIF }
  ExitProc:=OldExitProcPtr;
end.=====================Code ends===============================


This should do it. Slight modifications may be neccessary. I
have compiled this on TP 6.0. !!
0
mihai031697Author Commented:
Hey mittalk,
I really appreciate your job, but..
First of all the program is not dealing with DOUBLE BINARY SEARCH TREE, but with a BTREE, wich is not at all the same. I need that
binary search tree becuase the requirement was :
-'The main tree should hold the names of the teams, while the sub-tree holds the names of the players.'(See above)
That is, the first name on the line is a team and the second is a player belonging to that team
Then  i have to do some operations with the Players:
-Trade
-Add
-Cut
So I really cannot use your program not even as a guide..
Could you please do the right program?
0
nils pipenbrinckCommented:
This smells like homework.
0
nils pipenbrinckCommented:
This smells like homework.
0
mihai031697Author Commented:
It is one, Nils
I have done most of it but I'm stuck now..
That's why I asked for help

M.
0
mittalk033197Commented:
Well if you give me your stuff I could modify it. I think
once you understand my code.... updating it for a double tree should be very simple.
0
mihai031697Author Commented:
What do u mean by 'more stuff'?
Your code is Ok but it does not apply to my question.
It is NOT a double binery  tree
My problem is that I cannot read data (I don't know how to do it) in the binary teee.I can't understand how it is arranged in the double binary tree. An dthen how to cut and add it/
I'm in serious trouble...
M
0
mittalk033197Commented:
All u would need is to use my code as a unit or something and
have two tree variables defined. Now when you read some data into one tree variable, you can make a call to the second tree variable to add the things you want it to, in relation to the first one.. like maybe the pointer address or something. I can't think of a set routine for a double binary tree. If you understand OOP you will find it easier to understand this concept of a double treeif you think of a tree object and make 2 copies of it and update them simuntaneously.

That is all I can help without you awarding points for my answers. If you want, you can email medirectly at kunal@thepentagon.com

Best of luck !
0
mheacockCommented:
What the hell is a double binary tree??  I've taken a few ADT
courses, but can't figure out what this is.  And his diagram
is totally misleading.

And he should grade the answer just to get the question off of
the board.

Stop being a jerk MIHAI.  Grade the answer.  Your assignment is over.  Lets all move on.  Perhaps CompSci is not for you.
0
mihai031697Author Commented:
Hey mheacock...
>And he should grade the answer just to get the question off of
 the board.
 I absolutelly cannot grade this answer since this has nothing to do with my question. This is simply a 'cut & paste' from a public code source board. This deal with a B-Tree and not a binary search tree

> Stop being a jerk MIHAI. Grade the answer. Your assignment is over. If you think so you are as loser as the guy who copied and pasted it. How come this PAscal page is read by so many who do not have anything in common with real  programming?

>Lets all move on. Perhaps CompSci is not for you.
If you are curios I've answered lots of questions ( not dealing with Pascal programming) here on CompSci and the answers were mine not copied...
I will kepp this question there since someone will get a correct answer. BTW I have a working answer.

Good Luck guys.
Mihai
0
mheacockCommented:
Could you at least edit your question and the diagram so that it is clearer.  Your diagram and the requirements are totally misleading.  A proper explanation might have garnered you an answer when you needed it.
0
mheacockCommented:
Besides...if you don't like the current answer...reject it...let someone else give it a try.
0
mihai031697Author Commented:
Hi mheacock,
If you are interestede in giving it a try please give me an address where a I could send you a correct diagram , because whatever I do the diagram got shrinked here...
BTW I don't know how to reject this 'answer'...
I'lll try to explain it better. We have a normal binary search tree(BST)which looks as usual:
-two pointers ( left and right) to the next trees
-an 'info' field that keeps the name of a team
   AND ( this is the 'double thing ' you wondered about)
- a new pointer to a BST that looks like the one above but
instaed of keeping the name of a team it keeps the names of the players from that specific team:

                    Canadiens
                    /    |    \
                Bruins Roy Maple_Leafs
                 |       \        |
               Neely   Savage   Gilmour
                                    \
                                   Momesso
0
mihai031697Author Commented:
You see it still does not work>-(
Mihai
0
mheacockCommented:
Reject = F grade.
0
mihai031697Author Commented:
>mheacock...

> Reject = F grade. <

What does this mean ???
0
mheacockCommented:
If you want to rejec the current answer and allow someone else
to answer it, give the current answer a grade of 'F'.  But
it would appear you've just recently done that.

No ones going to answer your question anyhow...not for free.
We can give you hints and some help, but you aren't paying
us to write programs...I don't contract for free.

You're wasting your time and ours.  If you can't even write
a simple binary search tree...well...you figure it out.

And what you are asking is not a binary search tree anyhow...
perhaps a binary tree of teams, with each team node containing
a sub binary tree of players.  But you totally didn't explain
it right or even come close to diagraming it right.
0
mihai031697Author Commented:
mheacock...

I rejected that 'answer' and your comment.
Why didn't you add it as a comment ?

>>No ones going to answer your question anyhow...not for free.
I did not ask a free answer. The question is rated 245 points
and I think it is a fair amount of points.

>>You're wasting your time and ours
  I cannot waste your time since I do not care at all about it!

>>If you can't even write a simple binary search tree...well...you figure it out.
  First of all this is not a 'simple' binary tree; it is a DOUBLE one. Secondly, this is not a question of only writing it as you can see if you already learned to read plain English.
If you think that the diagram could help you more that the explanations I've alraedy provided do what I have asked you to do: give me an address where I could send you the correct diagram. I will repeat myself and tell you that the diagram gets shrinked (right justified) when I post it.
Please stop posting comments as answers and writing stupidities.
If you are able to answer the question do it, otherwise use your time in a better way.
Good luck!
0
virgo21Commented:
Here you go, there is some kind of bug in the treedel function, but I'll fix it if you want, I'm not sure this is the way you mean with a double binary search tree but I think so, the binary
search tree unit is taken from a book with a few small modifications.
I hope this code at least can get you on the right track.
If u want me something I can be reached at Virgo21@Hotmail.com.

{ Unit 1, handles a binary tree. }
Unit BinTree;

Interface

   Type

      BTree = ^nodeType;

      itemType = Record
                    Name : String;
                    PlayRoot : BTree;
                 End;


      nodeType = Record
                    Item : itemType;
                    LChild, RChild : BTree;
                 End;

{      BTree = treePtrType;}

      procType = Procedure (Var T : BTree; Item : itemType);

      Procedure CreateTree (Var T : BTree);
      { -----------------------------------------------------------
        Creates an empty tree.
        Precondition:  None.
        Postcondition: The empty Tree T is created.
        ----------------------------------------------------------- }

      Function TreeIsEmpty (T : BTree) : Boolean;
      { -----------------------------------------------------------
        Determines wheter a tree is empty or not.
        Precondition:  CreateTree (T) has been called.
        Postcondition: Returns true if T was empty; else returns
                       false.
        ----------------------------------------------------------- }

      Procedure TreeIns (Var T : BTree; NewItem : itemType;
                         Var Success : Boolean);
      { -----------------------------------------------------------
        Inserts an itme into the tree in it's proper sorted order.
        Precondition:  CreateTree (T) has been called and no two
                       items of T is the same. T's item are sorted in
                       alphabetical order. The item New differ from
                       all other items allready in the tree.
        Postcondition: New is in it's proper order in T ans Success
                       is true.
        ----------------------------------------------------------- }

      Procedure TreeDel (T : BTree; S : String; Var Success : Boolean);
      { -----------------------------------------------------------
        Deletes a specific item from the tree.
        Precondition:  CreateTree (T) has been called and no two
                       items of T is the same. T's item are sorted in
                       alphabetical order. The item New differ from
                       all other items allready in the tree.
        Postcondition: If we find a String in the tree equal to S
                       then that item is removed from the tree and
                       success is true. Otherwise, T is unchanged
                       and success is false.
        Calls: Local procedure DeleteItem, wich calls
               ProcessLeftmost.
        ----------------------------------------------------------- }
      Procedure TreeRetrieve (Var T, Found : BTree; S : String;
                              Var Success : Boolean);
      { -----------------------------------------------------------
        Retrieves the item matching S.
        Precondition:  CreateTable (T) has been called and  no two
                       items of T is the same. T's item are soted
                       in alphabetical order.
        Postcondition: If the retrieval was successful, T will point
                       at the node where it was found and success is
                       true else T is unchanged and success is false.
        ----------------------------------------------------------- }

      Procedure Traverse (T : BTree; Visit : procType);
      { -----------------------------------------------------------
        Traverses a tree in sorted order, calling procedure Visit
        once for each item.
        Precondition:  CreateTable (T) has been called and  no two
                       items of T is the same. The procedure
                       represented by Visit exists outside of the
                       ADT implementation and is defined with the
                       far directive.
        Postcondition: Visit's action occurs once for each item
                       in T.
        Note: Var allows Visit to alter T.
        ----------------------------------------------------------- }

Implementation

      Procedure CreateTree (Var T : BTree);
      Begin
         T := Nil;
      End; { CreateTree }

      Function TreeIsEmpty (T : BTree) : Boolean;
      Begin
         TreeIsEmpty := (T = Nil);
      End; { TreeIsEmpty }

      Procedure TreeIns (Var T : BTree; NewItem : itemType;
                         Var Success : Boolean);
      Begin
         Success := False;

         If (T = Nil) Then
            { the position has been found - insert after leaf }
         Begin
            new(T);
            T^.Item          := NewItem;
            T^.Item.PlayRoot := Nil;
            T^.LChild        := Nil;
            T^.RChild        := Nil;
            Success          := True;
         End
         Else
            If NewItem.Name < T^.Item.Name then
               { Search the left subtree }
               TreeIns (T^.LChild, NewItem, Success)
            Else
               { Search the right subtree }
               TreeIns (T^.RChild, NewItem, Success);
      End;

      Procedure TreeDel (T : BTree; S : String; Var Success : Boolean);

         Procedure ProcessLeftmost (Var NodePtr : BTree;
                                    Var TreeItem : itemType);
         { --------------------------------------------------------------
           Retrieves and deletes the leftmost descendent of a given node.
           Precondition:  NodePtr points to a node in a binary search tree.
                          This tree contains no dupes of any item.
           Postcondition: TreeItem contains the item in the leftmost
                          descendent of the node to wich NodePtr points.
                          The leftmost descendent of NodePtr is deleted.
           -------------------------------------------------------------- }
         Var
            DelPtr : BTree;
         Begin
            If NodePtr <> Nil Then
            Begin
               If NodePtr^.LChild = Nil Then
               Begin
                  TreeItem := NodePtr^.Item;
                  DelPtr := NodePtr;
                  NodePtr := NodePtr^.RChild;
                  Dispose (DelPtr);
               End
               Else
                  ProcessLeftmost (NodePtr^.LChild, TreeItem);
            End; { IF }

         End; { ProcessLeftmost }

         Procedure DeleteItem (Var RootPtr : BTree);
         { --------------------------------------------------------------
           Deletes the item in the root of a given tree.
           Precondition:  RootPtr points to the root of a binary search
                          tree. This tree contains no duplicate items.
           Postcondition: The item in the root of the given tree is
                          deleted.
           Algorithm note: There are four cases to consider:
              1. The root is a leaf.
              2. The root has no left child.
              3. The root has no right child.
              4. The root has two children.
           Calls: ProcessLeftmost.
           -------------------------------------------------------------- }
           Var
              DelPtr : BTree;
              ReplacementItem : itemType;
           Begin
              If RootPtr <> Nil Then
              Begin
                 { test for a leaf }
                 If (RootPtr^.LChild = Nil) and (RootPtr^.RChild = Nil) Then
                 Begin
                    Dispose (RootPtr);
                    RootPtr := Nil;
                 End
                 { test for no left child }
                 Else If RootPtr^.LChild = Nil Then
                 Begin
                    DelPtr := RootPtr;
                    RootPtr := RootPtr^.RChild;
                    Dispose (DelPtr);
                 End
                 { test for no right child }
                 Else If RootPtr^.RChild = Nil Then
                 Begin
                    DelPtr := RootPtr;
                    RootPtr := RootPtr^.LChild;
                    Dispose (DelPtr);
                 End
                 { there are two children - delete and retrieve the
                   inorder successor }
                 Else
                 Begin
                    ProcessLeftmost (RootPtr^.RChild, ReplacementItem);
                    RootPtr^.Item := ReplacementItem
                 End;
              End { If RootPtr <> Nil }
           End; { DleteItem }

      Begin
         If T = Nil Then
            Success := False { Empty Tree }
         Else If S = T^.Item.Name Then
         Begin
            DeleteItem (T); { Delete the item }
            Success := True;
         End
         { else search for the name }
         Else If S < T^.Item.Name Then
            { search the left subtree }
            TreeDel (T^.LChild, S, Success)
         Else
            { search the right subtree }
            TreeDel (T^.RChild, S, Success);
      End; { TreeDel }

      Procedure TreeRetrieve (Var T, Found : BTree; S : String;
                              Var Success : Boolean);
      Begin
         If T = Nil Then
            Success := false { Tree is empty }

         Else If S = T^.Item.Name Then
         Begin
            Found := T;
            Success := true;
         End

         Else If S < T^.Item.Name Then
            { Search the left subtree }
            TreeRetrieve (T^.LChild, Found, S, Success)
         Else
            { Search the right subtree }
            TreeRetrieve (T^.RChild, Found, S, Success);
      End; { TreeRetrieve }

      Procedure Traverse (T : BTree; Visit : procType);
      Begin
         { inorder traversal }
         If T <> Nil Then
         Begin
            Traverse (T^.LChild, Visit);
            Visit (T, T^.Item);
            Traverse (T^.RChild, Visit);
         End;

      End;

End.


{ Unit 2, parses the command line into a record. }
Unit Parser;

Interface

   Type
      CommandLine = Record
                       Command : String[5];
                       Team1    : String;
                       Player1  : String;
                       Team2    : String;
                       Player2  : String;
                    End;

   Procedure Parse (S : String; Var ComLine : CommandLine);

Implementation

   Procedure Parse (S : String; Var ComLine : CommandLine);
   Var
      n,
            tmp : Integer;
            tmpStr : String;
      Begin
            For n := 1 To Ord(S[0]) Do
                  S[n] := UpCase(S[n]);
            ComLine.Command := '';

            If S = 'PRINT' Then
            Begin
                  With ComLine Do
                  Begin
                        Command := S;
                        Team1   := '';
                        Player1 := '';
                        Team2   := '';
                        Player2 := '';
                  End
            End
            Else
            Begin
                  Case S[1] of
                        'A' : Begin
                                          For n := 1 To 3 Do
                                                tmpStr[n] := S[n];
                                                tmpStr[0] := Chr(3);

                                          If (S[4] = ' ') and (tmpStr = 'ADD') Then
                                          Begin
                                                For n := 5 To Ord (S[0]) Do
                                                      S[n-4] := S[n];
                                                S[0] := Chr (Ord (S[0]) - 4);
                                                ComLine.Command := 'ADD';

                                                { Put the team into the record. }
                                                For n := 1 To Ord (S[0]) Do
                                                      If S[n] = ' ' Then Tmp := n;

                                                For n := 1 To Tmp - 1 Do
                                                      ComLine.Team1[n] := S[n];
                                                ComLine.Team1[0] := Chr (Tmp - 1);

                                                For n := (Tmp + 1) To Ord (S[0]) Do
                                                      S[n-Tmp] := S[n];
                                                S[0] := Chr (Ord (S[0]) - Tmp);

                                                { Put the player into the record. }
                                                ComLine.Player1 := S;

                                                { Initialize the unused team and player. }
                                                ComLine.Team2 := '';
                                                Comline.Player2 := '';
                                          End
                                          Else
                                                WriteLn ('*** Syntax Error');
                                    End; { ADD command ends }

                        'C' : Begin
                                          For n := 1 To 3 Do
                                                tmpStr[n] := S[n];
                                          tmpStr[0] := Chr(3);

                                          If (S[4] = ' ') and (tmpStr = 'CUT') Then
                                          Begin
                                                For n := 5 To Ord (S[0]) Do
                                                      S[n-4] := S[n];
                                                S[0] := Chr (Ord (S[0]) - 4);
                                                ComLine.Command := 'CUT';

                                                { Put the team into the record. }
                                                For n := 1 To Ord (S[0]) Do
                                                      If S[n] = ' ' Then Tmp := n;

                                                For n := 1 To Tmp - 1 Do
                                                      ComLine.Team1[n] := S[n];
                                                ComLine.Team1[0] := Chr (Tmp - 1);

                                                For n := (Tmp + 1) To Ord (S[0]) Do
                                                      S[n-Tmp] := S[n];
                                                S[0] := Chr (Ord (S[0]) - Tmp);

                                                { Put the player into the record. }
                                                ComLine.Player1 := S;

                                                { Initialize the unused team and player. }
                                                ComLine.Team2 := '';
                                                Comline.Player2 := '';
                                          End
                                          Else
                                                WriteLn ('*** Syntax Error');
                                    End; { CUT Command ends }

                        'T' : Begin
                                          For n := 1 To 5 Do
                                                tmpStr[n] := S[n];
                                          tmpStr[0] := Chr (5);

                                          If (S[6] = ' ') and (tmpStr = 'TRADE') Then
                                          Begin
                                                For n := 7 To Ord (S[0]) Do
                                                      S[n-6] := S[n];
                                                S[0] := Chr (Ord (S[0]) - 6);
                                                ComLine.Command := 'TRADE';

                                                { Put team one into the record. }
                                                tmp := 0;
                                                For n := 1 To Ord (S[0]) Do
                                                      If (S[n] = ' ') and (tmp = 0) Then Tmp := n;

                                                For n := 1 To Tmp - 1 Do
                                                      ComLine.Team1[n] := S[n];
                                                ComLine.Team1[0] := Chr (Tmp - 1);

                                                For n := (Tmp + 1) To Ord (S[0]) Do
                                                      S[n-Tmp] := S[n];
                                                S[0] := Chr (Ord (S[0]) - Tmp);

                                                { Put player one into the record. }
                                                tmp := 0;
                                                For n := 1 To Ord (S[0]) Do
                                                      If (S[n] = ' ') and (tmp = 0) Then Tmp := n;

                                                For n := 1 To Tmp - 1 Do
                                                      ComLine.Player1[n] := S[n];
                                                ComLine.Player1[0] := Chr (Tmp - 1);

                                                For n := (Tmp + 1) To Ord (S[0]) Do
                                                      S[n-Tmp] := S[n];
                                                S[0] := Chr (Ord (S[0]) - Tmp);

                                                { Put team two into the record. }
                                                tmp := 0;
                                                For n := 1 To Ord (S[0]) Do
                                                      If (S[n] = ' ') and (tmp = 0) Then Tmp := n;

                                                For n := 1 To Tmp - 1 Do
                                                      ComLine.Team2[n] := S[n];
                                                ComLine.Team2[0] := Chr (Tmp - 1);

                                                For n := (Tmp + 1) To Ord (S[0]) Do
                                                      S[n-Tmp] := S[n];
                                                S[0] := Chr (Ord (S[0]) - Tmp);

                                                { Put player two into the record. }
                                                ComLine.Player2 := S;
                                          End
                                          Else
                                                WriteLn ('*** Syntax Error');
                                    End; { TRADE Command ends }
                  Else
                        WriteLn ('*** No such command!!!');
                  End; { CASE ends }
            End;
      End;
End.


{ The main program. }
Program Main;

Uses
   Crt,
   BinTree,
      Parser;

Const NameArr : Array[1..15] of string =
   ( 'Bruins Neely', 'Sabres Galley', 'Blues Noonan', 'MapleLeafs Gartner',
     'Blues Wells','Canucks Bure', 'Sabres Peca', 'Sabres Huddy',
     'Bruins Zombo', 'Islanders Beers', 'MapleLeafs Gill', 'Blues Hull',
     'Canucks Courtnall', 'Bruins Oates', 'Stars Modano' );

{$F+}
Procedure Visit2 (Var T : BTree; Item : itemType);
Begin
   WriteLn (Item.Name);
End;

Procedure Visit1 (Var T : BTree; Item : itemType);
Begin
      WriteLn;
      WriteLn;
      WriteLn (Item.Name);
      Traverse (T^.Item.PlayRoot, Visit2);
      WriteLn;
End;
{$F-}

Var
      tmpStr, S, Line : String;
      MyT : Record
                        TeamRoot   : BTree;
                        T          : BTree;
                        Temp       : Btree; { While traversing the player tree. }
                  End;
      Item : itemType;
      TItem : Array[1..2] Of itemType;
      ComLine : CommandLine;
      Success : Boolean;
      i, j, n, tmp : Integer;


Begin
      ClrScr;
      CreateTree (MyT.T);
      MyT.TeamRoot := MyT.T;

      For i := 1 To 15 Do
      Begin
            S := NameArr[i];
            MyT.T := MyT.TeamRoot;
            For j := 1 To Ord (S[0]) Do
                  S[j] := UpCase (S[j]);

            For j := 1 To Ord (S[0]) Do
                  If S[j] = ' ' Then tmp := j;

            For j := 1 To tmp - 1 Do
                  tmpStr[j] := S[j];
            tmpStr[0] := Chr(tmp - 1);

            Item.Name := tmpStr;
            Item.PlayRoot := Nil;

            For j := tmp + 1 To Ord (S[0]) Do
                  S[j-tmp] := S[j];
            S[0] := Chr (Ord (S[0]) - tmp);

            TreeRetrieve (MyT.T, MyT.Temp, Item.Name, Success);

            If NOT Success Then
            Begin
                  TreeIns (MyT.T, Item, Success);
                  If (i = 1) and Success Then
                        MyT.TeamRoot := MyT.T;
                  TreeRetrieve (MyT.T, MyT.Temp, Item.Name, Success);
            End;

            Item.Name := S;
            TreeIns (MyT.Temp^.Item.PlayRoot, Item, Success);
      End; { For }

      While (Line <> 'EXIT') Do
      Begin
            ReadLn (Line);
            Parse (Line, ComLine);

            If ComLine.Command = 'PRINT' Then
                  Traverse (MyT.T, Visit1)

            Else If ComLine.Command = 'ADD' Then
            Begin
                  TreeRetrieve (MyT.T, MyT.Temp, ComLine.Team1, Success);

                  If NOT Success Then
                  Begin
                        Item.Name := ComLine.Team1;
                        Item.PlayRoot := Nil;

                        TreeIns (MyT.T, Item, Success);

                        If (i = 1) and Success Then
                              MyT.TeamRoot := MyT.T;
                        TreeRetrieve (MyT.T, MyT.Temp, Item.Name, Success);
                  End; { If }

                  Item.Name := ComLine.Player1;
                  Item.PlayRoot := Nil;
                  TreeRetrieve (MyT.Temp^.Item.PlayRoot, MyT.Temp, Item.Name, Success);
                  If Success Then
                        WriteLn (#10#13'Player allready exists in that team!!!')
                  Else
                  Begin
                        TreeRetrieve (MyT.T, MyT.Temp, ComLine.Team1, Success);
                        TreeIns (MyT.Temp^.Item.PlayRoot, Item, Success);
                  End;
            End
            Else If ComLine.Command = 'CUT' Then
            Begin
                  TreeRetrieve (MyT.T, MyT.Temp, ComLine.Team1, Success);

                  If Success Then
                  Begin
                        TreeDel (MyT.Temp^.Item.PlayRoot, ComLine.Player1, Success);
                        If Not Success Then
                              WriteLn (#10#13'*** The player dosen''t play in that team or dosen''t exist.');
                  End
                  Else
                        WriteLn (#10#13'*** The team dosen''t exist!!!');
            End
            Else If ComLine.Command = 'TRADE' Then
            Begin
                  { Get first player item }
                  TreeRetrieve (MyT.T, MyT.Temp, ComLine.Team1, Success);
                  TreeRetrieve (MyT.Temp^.Item.PlayRoot, MyT.Temp,
                                            ComLine.Player1, Success);
                  TItem[1] := MyT.Temp^.Item;

                  { Get second player item }
                  TreeRetrieve (MyT.T, MyT.Temp, ComLine.Team2, Success);
                  TreeRetrieve (MyT.Temp^.Item.PlayRoot, MyT.Temp,
                                            ComLine.Player2, Success);
                  TItem[2] := MyT.Temp^.Item;

                  { Delete first player item }
                  TreeRetrieve (MyT.T, MyT.Temp, ComLine.Team1, Success);
                  Traverse (MyT.Temp^.Item.PlayRoot, Visit2);
                  ReadLn;
                  TreeDel (MyT.Temp^.Item.PlayRoot, ComLine.Player1, Success);
                  Traverse (MyT.Temp^.Item.PlayRoot, Visit2);
                  ReadLn;

                  { Delete second player item }
                  TreeRetrieve (MyT.T, MyT.Temp, ComLine.Team2, Success);
                  Traverse (MyT.Temp^.Item.PlayRoot, Visit2);
                  ReadLn;
                  TreeDel (MyT.Temp^.Item.PlayRoot, ComLine.Player2, Success);
                  Traverse (MyT.Temp^.Item.PlayRoot, Visit2);
                  ReadLn;

                  { Find second team }
                  TreeRetrieve (MyT.T, MyT.Temp, ComLine.Team2, Success);
                  Traverse (MyT.Temp^.Item.PlayRoot, Visit2);
                  ReadLn;
                  { Insert first player into second team }

                  TreeIns (MyT.Temp^.Item.PlayRoot, TItem[1], Success);
                  Traverse (MyT.Temp^.Item.PlayRoot, Visit2);
                  ReadLn;


                  { Find first team }
                  TreeRetrieve (MyT.T, MyT.Temp, ComLine.Team1, Success);
                  Traverse (MyT.Temp^.Item.PlayRoot, Visit2);
                  ReadLn;
                  { Insert second player into first team }
                  TreeIns (MyT.Temp^.Item.PlayRoot, TItem[2], Success);
                  Traverse (MyT.Temp^.Item.PlayRoot, Visit2);
                  ReadLn;
            End;




   End; { While }

End.

0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
mihai031697Author Commented:
virgo21,
Your  answer works quite good.\There are a few bugs here and there, but you deserve an A---> excelent!
I wish you'll get the same in your real classes.

Thnks again,


Mihai
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Pascal

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.