Solved

Help Binary Search Tree

Posted on 1997-03-23
35
626 Views
Last Modified: 2012-06-21
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
0
Comment
Question by:mihai031697
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 17
  • 5
  • 5
  • +5
35 Comments
 

Author Comment

by:mihai031697
ID: 1215264
Please forward an answer(hopefully a working one) to
<bver@hotmail.com>
Thanks a lot

M.
0
 
LVL 5

Expert Comment

by:julio011597
ID: 1215265
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
 
LVL 1

Expert Comment

by:pprikryl
ID: 1215266
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
Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

 

Author Comment

by:mihai031697
ID: 1215267

0
 
LVL 1

Expert Comment

by:pprikryl
ID: 1215268
...by the way, "Write a program" is hardly a question ;-)
0
 

Author Comment

by:mihai031697
ID: 1215269
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
 

Author Comment

by:mihai031697
ID: 1215270
Edited text of question
0
 

Author Comment

by:mihai031697
ID: 1215271
Edited text of question
0
 
LVL 1

Expert Comment

by:Fordream
ID: 1215272
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
 
LVL 1

Expert Comment

by:pprikryl
ID: 1215273
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
 

Author Comment

by:mihai031697
ID: 1215274
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
 

Expert Comment

by:mittalk033197
ID: 1215275
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
 

Author Comment

by:mihai031697
ID: 1215276
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
 

Author Comment

by:mihai031697
ID: 1215277
Adjusted points to 245
0
 

Expert Comment

by:mittalk033197
ID: 1215278
sure...I'll have it done and posted here by then. No probs. !!
0
 

Expert Comment

by:mittalk033197
ID: 1215279
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
 

Author Comment

by:mihai031697
ID: 1215280
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
 
LVL 4

Expert Comment

by:nils pipenbrinck
ID: 1215281
This smells like homework.
0
 
LVL 4

Expert Comment

by:nils pipenbrinck
ID: 1215282
This smells like homework.
0
 

Author Comment

by:mihai031697
ID: 1215283
It is one, Nils
I have done most of it but I'm stuck now..
That's why I asked for help

M.
0
 

Expert Comment

by:mittalk033197
ID: 1215284
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
 

Author Comment

by:mihai031697
ID: 1215285
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
 

Expert Comment

by:mittalk033197
ID: 1215286
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
 
LVL 3

Expert Comment

by:mheacock
ID: 1215287
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
 

Author Comment

by:mihai031697
ID: 1215288
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
 
LVL 3

Expert Comment

by:mheacock
ID: 1215289
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
 
LVL 3

Expert Comment

by:mheacock
ID: 1215290
Besides...if you don't like the current answer...reject it...let someone else give it a try.
0
 

Author Comment

by:mihai031697
ID: 1215291
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
 

Author Comment

by:mihai031697
ID: 1215292
You see it still does not work>-(
Mihai
0
 
LVL 3

Expert Comment

by:mheacock
ID: 1215293
Reject = F grade.
0
 

Author Comment

by:mihai031697
ID: 1215294
>mheacock...

> Reject = F grade. <

What does this mean ???
0
 
LVL 3

Expert Comment

by:mheacock
ID: 1215295
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
 

Author Comment

by:mihai031697
ID: 1215296
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
 

Accepted Solution

by:
virgo21 earned 240 total points
ID: 1215297
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
 

Author Comment

by:mihai031697
ID: 1215298
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

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

After hours on line I found a solution which pointed to the inherited Active Directory permissions . You have to give/allow permissions to the "Exchange trusted subsystem" for the user in the Active Directory...
Had a business requirement to store the mobile number in an environmental variable. This is just a quick article on how this was done.
How to Install VMware Tools in Red Hat Enterprise Linux 6.4 (RHEL 6.4) Step-by-Step Tutorial
Exchange organizations may use the Journaling Agent of the Transport Service to archive messages going through Exchange. However, if the Transport Service is integrated with some email content management application (such as an antispam), the adminiā€¦

752 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question