Traversal of Tree in Delphi Question (using strings)

I am trying to traverse a tree structure and output the data of two strings. Below is the record structure i am using and what i have written so far.

My issue comes in that it appears i am not traversing the list at all. I am unsure of why it is not working. I am trying to use an inorder recursive traversal. I even tried to add a local variable N to go through the tree.

Regardless of what i try, it give me no output whatsoever. Is it actually possible or am i chasing something that cannot be done?

I have spent all weekend on this, and i am ready to just walk away from it alltogether it is so annoying and demoralising!


program MelodySearchEngine;
 
{$apptype console}
 
uses
  SysUtils,
  MelodyListADT,
  MelodyTreeADT;
 
var
  melodyFilename: string;
  melodyFile: text;
  melodies: MelodyTree;
  option:char;
 
procedure Menu;
begin
  writeln;writeln;writeln;
  writeln('   (l)oad melody data');
  writeln('   (d)isplay tree');
  writeln('   (s)earch for a tune');
  writeln('   (f)ind all phrases from songs');
  writeln('   (q)uit');
  writeln;
end;
 
procedure LoadMelodies(filename: string);
// pre:  true
// post: if the file corresponding to filename exists and is in a valid format,
//       the melodies tree variable now contains the tune data
var phraseText,songTitle,fileLine:string;
    tune:TuneList;
    expectation,melodyCount:integer;
begin
  AssignFile(melodyFile, filename);
 
  // the compiler directives here take care with opening the file,
  // as we don't want to abort if there's an error
  {$I-} Reset(melodyFile); {$I+}
  if IOResult <> 0  then
    writeln('Problem opening the file ',filename, ', sorry!')
  else
  begin
    expectation := 0;    // this just stores which kind of a line we're expecting:
                         // song phrase (0), pitch changes(1) or song title (2)
    melodyCount := 0;
    initialiseTree(melodies);
    while not eof(melodyFile) do  // go systematically line-by-line through the file
    begin
      readln(melodyFile,fileLine);
      fileLine := trim(fileLine);  // trimming removes extraneous whitespace
      if (length(fileLine)>0) then // non-empty line
      begin
        if expectation=0 then // expecting a line containing phrase from the song
        begin
          if fileLine[1]='"' then // found a phrase
          begin
            phraseText := fileLine;
            expectation := 1;
          end
          // otherwise ignore the line since we don't know what it was
        end
        else if expectation=1 then // expecting a tune
        begin
          if validPitchChange(fileLine[1]) then // u s or d
          begin
            parsePitchChanges(fileLine,tune); // now tune contains the pitch changes
            expectation := 2;
          end;
        end
        else if expectation=2 then  // expecting a song title
        begin
          songTitle := fileLine;
          expectation := 0;
          inc(melodyCount);
          addToTree(melodies,phraseText,songTitle,tune);
          // writeln('Found a tune:');
          // writeln('Words: ',phraseText);
          // writeln('Pitch changes: ',fileLine);
          // writeln('Song: ',songTitle)
        end
      end;
    end;
    writeln('Number of melodic phrases found in file: ',melodyCount);
    close(melodyFile)
  end
end;
 
procedure findPhrase (t: MelodyTree; n:integer);  //Use inorder traversal
begin
 writeln;
 writeln(' Phrases Stored In The Tree Are: ');
 
If (Not(Assigned(T))) And (Length(Trim(T^.title)) = 0) Then
 begin
    findPhrase(t.title,n+1);
    write('[', (t^.title), ']  :  ', '"');
 end;
 
If (Not(Assigned(T))) And (Length(Trim(T^.phrase)) = 0) Then
 begin
    findPhrase(t.phrase, n+1);
    write((t^.phrase), '"');
 end;
end;
 
begin
 
   writeln('     *** Melody Search Engine ***');
   repeat
     Menu;
     write('Option? ');
     readln(option);
     case option of
        'l':  // (l)oad melody data
        begin
          write('Load melodies from which file? ');
          readln(melodyFilename);
          LoadMelodies(melodyFilename);
        end;
        'f':  // (f)ind all phrases from songs
        begin
          findPhrase(melodies,0);
        end;
 
     end;
 
 
   until (option='q') or (option='Q');
end.
 
 
(* UNIT IS IN A SEPERATE FILE CALLED MelodyTreeADT *)
 
 
unit MelodyTreeADT;
 
interface
 
uses MelodyListADT;
 
type MelodyTree = ^TreeNode;
     TreeNode = record
                  upBranch: MelodyTree;
                  downBranch: MelodyTree;
                  sameBranch: MelodyTree;
                  title: string;
                  phrase: string;
                end;
 
procedure initialiseTree(var t:MelodyTree);
// pre:  true
// post: t has been initialised to the empty tree
 
procedure addToTree(var t:MelodyTree; phraseText,songTitle:string; tuneP:TuneList);
// pre:  the given phrase in the song is not already in the tree, nor is there
//       another phrase with the same u/s/d sequence already in the tree
// post: the phrase and song title have been stored in the tree in the correct
//       location according to the u/s/d sequence pointed to by tuneP
 
implementation
 
procedure initialiseTree(var t:MelodyTree);
// pre:  true
// post: t has been initialised to the empty tree
begin
  t := nil;
end;
 
procedure addToTree(var t:MelodyTree; phraseText,songTitle:string; tuneP:TuneList);
// pre:  the given phrase in the song is not already in the tree, nor is there
//       another phrase with the same u/s/d sequence already in the tree
// post: the phrase and song title have been stored in the tree in the correct
//       location according to the u/s/d sequence pointed to by tuneP
begin
  if t=nil then  // need to create a tree node here
  begin
    new(t);
    t^.phrase := '';        // these strings may get overwritten
    t^.title := '';         //  later if a tune ends at this tree node
    t^.upBranch := nil;
    t^.sameBranch := nil;   // any of these 3 nil branches may get
    t^.downBranch := nil;   // extended later if necessary
  end;
  if tuneP=nil then   // end of this tune; need to store the strings here
  begin
    // assuming no duplicates, i.e. no other phrase/song is already stored here
    t^.phrase := phraseText;
    t^.title := songTitle;
  end
  else   // need to go further down the tree, according to the next
  begin  // pitch change in the tune
    if tuneP^.change=Up then
      addToTree(t^.upBranch,phraseText,songTitle,tuneP^.next)
    else if tuneP^.change=Same then
      addToTree(t^.sameBranch,phraseText,songTitle,tuneP^.next)
    else
      addToTree(t^.downBranch,phraseText,songTitle,tuneP^.next)
  end
end;
end.

Open in new window

Prima12Asked:
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.

Prima12Author Commented:
Sorry i forgot point out, my lecturer has written most of the code i have done the findPhrase procedure.
0
spoxoxCommented:
from findPhrase:
If (Not(Assigned(T))) And (Length(Trim(T^.title)) = 0) Then

Assigned(t) means you have a tree. Not Assigned(t) means you have no tree.

How about trying this instead:
If ( (Assigned(T))) And (Length(Trim(T^.title)) > 0) Then

0
Prima12Author Commented:
Thanks for the comment/ Unfortunatly no that does not help with displaying the tree values Title & Phrase. The only output i get on the screen is:

Phrases Stored In The Tree Are:




 
0
Cloud Class® Course: C++ 11 Fundamentals

This course will introduce you to C++ 11 and teach you about syntax fundamentals.

spoxoxCommented:
The fact that you don't see the "Number of melodic phrases found in file" on your output seems to be bad news.


LoadMelodies looks pretty suspicious. It seems to require a particular format for the input file:

"This is a phrase from a song"
usd pitch change line
This is the song title, might have quotes
"This is a phrase from another song"
usd pitch change line
Another song title

etc.

Errors along the way (no initial quote for the song phrase, invalid Pitch Change) look like they might mess up the operation.

Is this guaranteed by the prof, or is it your work?

If you can guarantee the quality of the data, this can (and should) be more straightforward:

while not eof
     readln(melodyfile, phrasetext)
     readln(melodyfile, pitch)
      // work with pitch
     readln(melodyfile, songtitle)
      // work with songtitle


0
spoxoxCommented:
You are starting by loading a melody file...?
0
Prima12Author Commented:
Hi

Yes the code originally given is 100% fine. Whenever i run the program, you have to select the load option before we do anything else. We load from a text file which is pre filled with data in a certain format indeed.

The issue is somewhere in the procedure i have written for sure as the displaying of the file contents works 100%.
0
spoxoxCommented:
I'm not really clear on the upbranch/samebranch/downbranch structure, and what the tree is meant to hold.

General discussion of recursion, as it seems warranted from the code above.

Generally, when dealing with recursion, we have to identify the base case and recursive case. For example, one classic teaching example for recursion is calculating n! (factorial). You probably remember that

n! = n * (n-1)  * (n-2) * ... * 3 * 2.

Therefore,

n! = n * (n-1)!

The use of factorial in the solution marks this as recursive. In developing a recursive subroutine to calculate factorial, we first identify the base case. We know that

1! = 0! = 1

This is our base case. We'll express it as (n is less than 2).

The recursive case is (n greater than or equal to 2).

So,

factorial(n):
if (n<2) // base case
   return 1;
else  // recursive case
  return n * factorial(n-1);

Specific to current case
procedure findPhrase (t: MelodyTree; n:integer);
In traversing your MelodyTree, you have to identify your base case and recursive cases. It seems the base case will be when Assigned(t) is false. The recursive case will be Assigned(t) is true.

When Assigned(t) is true, you probably want to do this, or some variation:
Writeln(t^.title, t^.phrase);findPhrase(t^.sameBranch);findPhrase(t^.downBranch);

This will track the sameBranch links to their end, node-by-node. Then it will track the downBranch links, starting furthest from the original node (N1, N2, N3, N4, N5, N6, N7 in snippet). Without studying how the tree-building code works, I don't know if this is the right traversal. You should have a better idea of what makes sense.

start
 |
 V
N1 -sB-> N2 -sB-> N3 -sB-> N4 -sB-> nil
 |        |        |        |
 |        |        V        V
 |        |       nil      N5 -sB-> N6 -sB-> nil
 |        V                 |        |
 |                          V        V
 V                         N7       nil

Open in new window

0
Prima12Author Commented:
What an excellent response. It certainly helps when understanding recursion. We did indeed use that exact example with factorials.

Re the issue....
The crash is occuring when i attempt to use recursion. I ran the program without debugging and it left the console window open instead of it automaticlly shutting down on me. It printed out 3 lines which all said:

Phrases Stored In The Tree Are:

Phrases Stored In The Tree Are:

Phrases Stored In The Tree Are:


Then it gave the windows "program stopped working" error.

Usually when i just run it as normal i see a flash of 00000X before it closes down. To me it seems the code is fine, it makes sense to me and i understand why its coded that way. But this compiler seems to freak out.
0
spoxoxCommented:
To save (at least temporarily) the output before the program console window closes, you can either:
1) just before the program exits, add a readln(someString);

2) outside delphi, open a command window and navigate to the project directory. You can run the (.exe) program manually.

3) search google for other ways!


Is the code still up to date, or do you have a more recent version? I'll run it myself if you can supply the data file and MelodyListADT unit.
0
Prima12Author Commented:
Hi

http://www.speedyshare.com/539313426.html

Once you get the files let me know so i can delete them from speedyshare

Cheers for checking this out
0
spoxoxCommented:
have downloaded
0
spoxoxCommented:
I haven't spent the time to figure out how the melodyTree is maintained. (I have no idea what the pitch business is about!)

Anyway, the answer I provided in 22977461 works, except...

When Assigned(t) is true, you probably want to do this, or some variation:
begin
Writeln(t^.title, t^.phrase); // just want t^.phrase
findPhrase(t^.sameBranch);
findPhrase(t^.downBranch);
findPhrase(t^.upBranch); // add this too end
0
Prima12Author Commented:
Wow so it actually runs on your end?  What are you using to compile it and run?

I am going to be so annoyed if all this time spent fretting over code was because of my IDE and not my code being at fault.
0
spoxoxCommented:
I'm using Turbo Delphi:
"Borland® Delphi® for Microsoft® Windows" Version 10.0.2288.42451 Update 2"

You are running, too, as evidenced by your post 22977710.

The key point is that the phrases are all found "Up" from the tree node. Without traversing "upBranch", the phrases won't be found.

I am reluctant to show an answer to an assignment, but....try this.

procedure findPhrase (t: MelodyTree);  //Use inorder traversalbegin //writeln; //writeln(' Phrases Stored In The Tree Are: '); // test: is not emptyIf (Assigned(T)) Then begin    if t^.phrase <> '' then      writeln(t^.phrase);    findPhrase(t^.sameBranch);    findPhrase(t^.downBranch);    findPhrase(t^.upBranch); end;end; // end procedure findPhrase
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
Prima12Author Commented:
I actually had the structure in a pre order traversal since my earlier post , before you posted that, but i still would not have gotten it to work without the removal of that trim so thank you very much for pointing that out.
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
Editors IDEs

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.