?
Solved

Traversal of Tree in Delphi Question (using strings)

Posted on 2008-11-16
15
Medium Priority
?
330 Views
Last Modified: 2013-11-23
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

0
Comment
Question by:Prima12
  • 8
  • 7
15 Comments
 

Author Comment

by:Prima12
ID: 22971933
Sorry i forgot point out, my lecturer has written most of the code i have done the findPhrase procedure.
0
 
LVL 11

Expert Comment

by:spoxox
ID: 22972633
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
 

Author Comment

by:Prima12
ID: 22973095
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 11

Expert Comment

by:spoxox
ID: 22973408
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
 
LVL 11

Expert Comment

by:spoxox
ID: 22973409
You are starting by loading a melody file...?
0
 

Author Comment

by:Prima12
ID: 22975304
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
 
LVL 11

Expert Comment

by:spoxox
ID: 22977461
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
 

Author Comment

by:Prima12
ID: 22977710
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
 
LVL 11

Expert Comment

by:spoxox
ID: 22977994
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
 

Author Comment

by:Prima12
ID: 22978350
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
 
LVL 11

Expert Comment

by:spoxox
ID: 22978577
have downloaded
0
 
LVL 11

Expert Comment

by:spoxox
ID: 22980611
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
 

Author Comment

by:Prima12
ID: 22980680
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
 
LVL 11

Accepted Solution

by:
spoxox earned 2000 total points
ID: 22980877
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
 

Author Closing Comment

by:Prima12
ID: 31517281
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

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

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

Update (December 2011): Since this article was published, the things have changed for good for Android native developers. The Sequoyah Project (http://www.eclipse.org/sequoyah/) automates most of the tasks discussed in this article. You can even fin…
The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
The viewer will learn how to use NetBeans IDE 8.0 for Windows to connect to a MySQL database. Open Services Panel: Create a new connection using New Connection Wizard: Create a test database called eetutorial: Create a new test tabel called ee…
The viewer will learn how to use and create new code templates in NetBeans IDE 8.0 for Windows.
Suggested Courses

839 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