Solved

Probing a Tree (Part 2)

Posted on 1998-06-22
31
358 Views
Last Modified: 2010-04-01
Need help printing each level a tree when the user chooses to probe.
0
Comment
Question by:John500
  • 17
  • 14
31 Comments
 
LVL 22

Accepted Solution

by:
nietod earned 100 total points
ID: 1166426
You again!
0
 
LVL 22

Expert Comment

by:nietod
ID: 1166427
How was the test?  

You were really close on this.  So this should not take long.  But I've deleted everything you sent before, can you send the current version or post it here?
0
 
LVL 22

Expert Comment

by:nietod
ID: 1166428
Is this not part of an assignment anymore?  and if it is not part of an assignment, do you want help reaching the solution, ot just want to see the solution?  
0
 

Author Comment

by:John500
ID: 1166429
Here it is, take it away sam.  I sent the files to the following e-mail address:  tniec@wareunl.com

void Probe::goRight()
{
      if( _top < _size -1 && _trail[_top]->_right )
            {
                  _trail[_top + 1] = _trail[_top] -> _right;
                  _top++;
            }
}

void Probe::goLeft()
{
      if(_top < _size -1 && _trail[_top]->_left)
            {
                  _trail[_top + 1] = _trail[_top] -> _left;
                  _top++;
            }
}

void Probe::probeTree()
 {

}

BinTree::ProbTree()
{
      Probe CurrentProbe(this);
      //// Use CurrentProbe to probe the tree.
}

void Probe::probeTree()
{

  Node *CurPtr = _trail[_top];

                   if((CurPtr)
                        CurPtr->print();
                   if(CurPtr->_left)
                        CurPtr->_left->print();
                   if(CurPtr->_right)
                        CurPtr->_right->print();
                   cout << "Indicate direction to probe:\n\n";
                   cout<<"l)eft,   r)ight,   t)op,   u)p,   q)uit\n";
                   cout<<"\nSelection:\n\n";
                   char Option = GetMenuLetter("LRTUQ");

                   char Prompt[100];      // string used to form the menu prompt string.
                   Prompt[0] = 0;             // Terminate the prompt string.
                   /*
                   if (_trail[_top]->_left)            // If there is a left node, then
                   strcat(Prompt,"L)eft    "); // Add on the left option.
                   if (_trail[_top]->_right) // If there is a right node, then
                   strcat(Prompt,"R)ight   "); // Add on the rightt option.

                   */


              switch (Option)
      {
      case 'L':
                    goLeft();
                        break;
      case 'R':
                    goRight();
                        break;
      case 'T':
                    goTop();
                        break;
      case 'U':
                    goUp();
                        break;
      case 'Q':
                        return;
      }

}  // end of probe::Tree
0
 
LVL 22

Expert Comment

by:nietod
ID: 1166430
Are you just looking for the final answer or do you want help getting there?  I assume this does not count anymore as the course is over, right?
0
 

Author Comment

by:John500
ID: 1166431
Here it is, take it away sam.  I sent the files to the following e-mail address:  tniec@wareunl.com

void Probe::goRight()
{
      if( _top < _size -1 && _trail[_top]->_right )
            {
                  _trail[_top + 1] = _trail[_top] -> _right;
                  _top++;
            }
}

void Probe::goLeft()
{
      if(_top < _size -1 && _trail[_top]->_left)
            {
                  _trail[_top + 1] = _trail[_top] -> _left;
                  _top++;
            }
}

void Probe::probeTree()
 {

}

BinTree::ProbTree()
{
      Probe CurrentProbe(this);
      //// Use CurrentProbe to probe the tree.
}

void Probe::probeTree()
{

  Node *CurPtr = _trail[_top];

                   if((CurPtr)
                        CurPtr->print();
                   if(CurPtr->_left)
                        CurPtr->_left->print();
                   if(CurPtr->_right)
                        CurPtr->_right->print();
                   cout << "Indicate direction to probe:\n\n";
                   cout<<"l)eft,   r)ight,   t)op,   u)p,   q)uit\n";
                   cout<<"\nSelection:\n\n";
                   char Option = GetMenuLetter("LRTUQ");

                   char Prompt[100];      // string used to form the menu prompt string.
                   Prompt[0] = 0;             // Terminate the prompt string.
                   /*
                   if (_trail[_top]->_left)            // If there is a left node, then
                   strcat(Prompt,"L)eft    "); // Add on the left option.
                   if (_trail[_top]->_right) // If there is a right node, then
                   strcat(Prompt,"R)ight   "); // Add on the rightt option.

                   */


              switch (Option)
      {
      case 'L':
                    goLeft();
                        break;
      case 'R':
                    goRight();
                        break;
      case 'T':
                    goTop();
                        break;
      case 'U':
                    goUp();
                        break;
      case 'Q':
                        return;
      }

}  // end of probe::Tree
0
 

Author Comment

by:John500
ID: 1166432
Todd,

Yes, the course is over.  I gave all those details in the e-mail I sent.  Do as you wish with the answer.  Give it all at once or bit by bit, maybe a little of both?

John
0
 

Author Comment

by:John500
ID: 1166433
Todd,

Yes, the course is over.  I gave all those details in the e-mail I sent.  Do as you wish with the answer.  Give it all at once or bit by bit, maybe a little of both?

John
0
 

Author Comment

by:John500
ID: 1166434
Todd,

For whatever it's worth, as I was looking through my notes I noticed that the function Probe::probeTree() takes a parameter of (BinTree *tree) so that the function should look like:

void Probe::probeTree(BinTree *tree)  

That is, if we are to take my professor's approach...

John
0
 
LVL 22

Expert Comment

by:nietod
ID: 1166435
We didn't take that approach.  We made the Probe constructor take a BinrTree * which it saves.  So the probe then a probe object works with only one tree.  We can do it the other way if you want.  It is a small change.  Why not get the code I sent you compiling and then we can switch it.

Note one thing I didn;t consider (look at) in the code I sent, was the code that calls the probeTree() procedure.  That code should create a probe for the specified tree and then call probeTree() on it, it would be something like

case "P"
{
    Probe Prb(Tree1);
   Prb.probeTree();
   break;
}

0
 

Author Comment

by:John500
ID: 1166436
Todd,

You may not have received my email yet, but I did get it to compile.  I also inserted the test that you spoke of.  In regard to the function that calls probeTree(), remember that I have declared Tree1 within the main, and every other function I have uses it, so maybe I should be consistent and do the following:

case 'P': // Initialize
      probeTree(Tree1);
      break;

This is slightly different from yours.  Would the above work if we change the constructor to look like this:

Probe::Probe()
{
      _trail[0];
      _top = -1;
}

and make the function Probe::probeTree take the parameter Tree1?

The thing I haven't figured out is how to make the guts of the function Probe::probeTree(BinTree *tree) work on "tree" instead of CurPtr.  Would this be something like:

CurPtr = tree;

??

John

0
 
LVL 22

Expert Comment

by:nietod
ID: 1166437
The probe constructor could just do nothing, like

Probe::Probe()
 {
 }

(Or you could just leave it out, that is, you don't need one.)  then the probeTree() procedure just starts off with the code that used to be in the Probe() constructor, like

void Probe::probeTree(BinTree *TreePtr)
{
   if (TreePtr->_root == 0)
   {
      //// print an error message and return.  this test has the same purpose
     //// as the test I suggested before to make sure that there is at least one item
     //// on the stack.  That test was if (_top > 1), this does the same thing, but works better
     //// with the design you are switching to.
   }
   _trail[0] = TreePtr->_root;
   _top = 1;  // This should be 0 or 1 depending on your inclination.  
                    // Whatever you prefer to indicate 1 item on the stack.
   
// rest or probeTree stays the same.
0
 

Author Comment

by:John500
ID: 1166438
Todd,

I did the following, is this what you meant, I'm getting quite a few errors.  I changed the class declarations also.

void Probe::goRight()
{
      if( _top < _size -1 && _trail[_top]->_right )
            {
                  _trail[_top + 1] = _trail[_top] -> _right;
                  _top++;
            }
}

void Probe::goLeft()
{
      if(_top < _size -1 && _trail[_top]->_left)
            {
                  _trail[_top + 1] = _trail[_top] -> _left;
                  _top++;
            }
}

void Probe::probeTree(BinTree *TreePtr)
{
      if (TreePtr->_root == 0)
      {
            cout<<"\n Can't probe an empty tree!\n";
      }

       while(1)
      {

            _trail[0] = TreePtr->_root;
            _top = 1;

            cout << "Current:" << endl;
            TreePtr->print();
            cout << "Left:" << endl;
            if(TreePtr->_left)
                  TreePtr->_left->print();
            else
                  cout << "None" << endl;
            cout << "Right:" << endl;
            if(TreePtr->_right)
                  TreePtr->_right->print();
            else
                  cout << "None" << endl;

            char Prompt[100];      
                  Prompt[0] = 0;  

            if (TreePtr->_left)
                    strcat(Prompt,"L)eft    ");  
            if (TreePtr->_right)  
                    strcat(Prompt,"R)ight   ");    
            if (_top > 1)
                    strcat(Prompt,"U)p       T)op    ");
            strcat(Prompt,"Q)uit");                

            cout << "Indicate direction to probe:\n\n";
            cout << Prompt;                        
            char Option = GetMenuLetter("LRTUQ");
..}

I'm hoping to continue this from home but the wife may not grant that kind of time.  I know, I know...

John

0
 
LVL 22

Expert Comment

by:nietod
ID: 1166439
Well there's no deadline anymore... right?

A couple of things in probeTree()
1.  The first test for an empty tree should return after printing the message.  Otherwise, the code following it will crash.  That is why that test is there--to prevent the code from running.
2.  The lines

_trail[0] = TreePtr->_root;
_top = 1;

are inside the while loop.  They should be before the loop.  These lines "posiiton" the probe at the top of the tree.  That is they make the "current node" the root node.  This needs to be done when you start out.  (You need a starting point to probe from.)  However, with the lines as they are they will positiont he probe at the top of the tree on every loop.  so if you move the probe, these lines will move you back.  Not very effetive.  These lines belong before the loop, but after the if () that tests for an empty tree.   (The first of these lines will crash if the tree is empty, so they have to go after the empty test, and the empty test must end the procedure if the tree is empty.)
0
 
LVL 22

Expert Comment

by:nietod
ID: 1166440
In the code I e-mailed to you there was a switch() statement in probeTree()  What happedned to that?  (Actually that was in the code you sent me.)  It is still needed.
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 

Author Comment

by:John500
ID: 1166441
Todd,

No, there is no dead line because the course is completed.  I said I wanted to work on it from home because I enjoy it.

I put the "return" in the test, that was an oversite.  I see your point with the lines that initialize the stack to start pointing at the root.

The switch lines of code were left out to save space, they weren't an issue in my last question.

Did I correctly replace the word CurPtr with TreePtr in the last question?  I figured every occurence of CurPtr had to be replaced with TreePtr.

I'm getting quite a few errors at this point, one of which is:
'print' is not a member of BinTree in function probeTree(BinTree*).  The same goes for every occurence of _right and _left.

John

0
 
LVL 22

Expert Comment

by:nietod
ID: 1166442
I didn't notice the CurPtr to TreePtr change.  That is not completely right.  First of all they are different types.  CurPtr points to a node, the node that is currently being probed.  TreePtr points to a tree.  So they can't be substituted.  The current node can be found at the top of the stack the syntax is

_stack[_top]

That is a pointer to the current node.  But it is a pain to type each time you need the current node, so at the top of the loop we store it in a variable called CurPtr, like

while (1)
{
    Node *CurPtr = _stack[_top];

Most of the errors you are getting are due to the fact that TreePtr points to a tree not a node, make that fix and let me know.
0
 

Author Comment

by:John500
ID: 1166443
Todd,

I have some questions about how the stack works.  In the functions goLeft & goRight _top is used as a test:

if( _top < _size -1 && _trail[_top]->_right )
{
      _trail[_top + 1] = _trail[_top] -> _right;
      _top++;
}

How can _top ever be less than negative 1?  If _size is -1 then the array is full and top must be much higer, no??  Array item zero is set to the root with _trail[0] = TreePtr->_root, and the top is incremented or set to 1.  Each time _top gets incremented, I'm assuming that size gets decremented automatically?  If this is true, as _size gets smaller _top gets larger but in any case under the SUN, _top couldn't be less then 0???

John
0
 

Author Comment

by:John500
ID: 1166444
Todd,

I made the changes with CurPtr and that fixed most everything as you said.  Now the one error I have says:

call to undefined function 'probeTree()' in function main.

Here is what I have in the class declaration and definition:

void Probe::probeTree(BinTree *TreePtr)
void probeTree(BinTree *TreePtr)

And here is the way I'm calling it in main:

probeTree(Tree1);

I also used your method below but it didn't work:

Probe prb(Tree1);
prb.probeTree();
0
 
LVL 22

Expert Comment

by:nietod
ID: 1166445
>> How can _top ever be less than negative 1?
So far, you haven't been clear with how you are using _top.  That's why my comments have often had two choices with how _top should be used in them.  Lets say now that
_top is the index of the top item on the stack  (The other approach is that it is the number of items in the stack.  These differ by 1.)  Thus we will use _top = -1 to indicate an empty stack.  _top = 0 to indicate one item on the stack (in this case it must be the root node.)  and _top = _size -1 to indicate a full stack.  Note that an empty stack is not a very important case for this.  When the tree is empty, we can't probe so we won't ever use the stack.  If the tree is not empty we will always have at least one item, the root node, on it.

>>  If _size is -1 then the array is full and top must be much higer, no??  
??? no.  _size is constant.  That is an enum you set to the size of the stack array.  It allows you to change the size of the stack's array in case you need more room.  (on a compilation by compilation basis.  You can't change the size while the program is running.)

>>Array item zero is set to the root with _trail[0] = TreePtr->_root, and the top is
     incremented or set to 1.  Each time _top gets incremented, I'm assuming that size gets
     decremented automatically?  If this is true, as _size gets smaller _top gets larger but in any case under the SUN, _top couldn't be less then 0???

_top gets larger, but _size stays the same.  The array size stays the same.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1166446
>>void Probe::probeTree(BinTree *TreePtr)
>>     void probeTree(BinTree *TreePtr)

That declares two functions called probeTree().  One function is a member of the probe class.  The other is a regular function.  You probably define the function that is a member of the probe class, but you probably don't define the global one.  That's alright, you don't want the global one.  But you should get rid of its declaration as well.  (The 2nd one.)

>>     And here is the way I'm calling it in main:

     probeTree(Tree1);

That calls the non-member (global) one.  The one you didn't define.  you want to call the member one, that is, the one that uses a probe object.

>>     I also used your method below but it didn't work:

>>     Probe prb(Tree1);
>>     prb.probeTree();

That works for the way we had probe where the constructor took the tree, and the probeTree() procedure took nothing.  Now change it to.

    Probe prb();
    prb.probeTree(&Tree1);

0
 

Author Comment

by:John500
ID: 1166447
Todd,

You wrote:
So far, you haven't been clear with how you are using _top.  

Within the class definition of Probe, I have the following:
void goTop(){_top = 0;}
This was given in class as well as the goLeft & goRight functions which use the following test:
_top < _size -1  
Is it correct, is there any way it could make sense?  If I now switch to what you said,

"Thus we will use _top = -1 to indicate an empty stack.  _top = 0 to indicate one item on the stack (in this case it must be the root node.)  and _top = _size -1 to indicate a full stack."

This change will impact all my functions, no?  At present, are the class definitions and functions in harmony?
0
 

Author Comment

by:John500
ID: 1166448
Todd,

Regarding:
>>void Probe::probeTree(BinTree *TreePtr)
>>     void probeTree(BinTree *TreePtr)
You said:
That declares two functions called probeTree.

No, one is the class decalaration and the other is the function definition.  I can see how I sent the wrong signal.  I just wanted you to see I'm declaring & defining it properly.

Using the above function, I still get errors even using your last suggestion of:
Probe prb();
    prb.probeTree(&Tree1);
The error is:
Structure required on left side of . or .* in func main().
Keep in mind I have no Probe constructor at this point.




0
 

Author Comment

by:John500
ID: 1166449
Todd,

I forgot to mention, how can size be constant if it is set to 30 in the private member definitions?  You wrote:
>_size is constant.  That is, an enum you set to the size of the >stack array.

Since the professor set it to 30 (which to me means 30 possible levels or total possible height) the size must get smaller each time top is incremented.

Which brings me to my next question.  When we call _top++, does this mean that we are that much further from the top?
0
 
LVL 22

Expert Comment

by:nietod
ID: 1166450
>>     Within the class definition of Probe, I have the following:
>>     void goTop(){_top = 0;}
>>     This was given in class as well as the goLeft & goRight functions which use the following test:
>>     _top < _size -1  
>>     Is it correct, is there any way it could make sense?  If I now switch to what you said,
>>     This change will impact all my functions, no?

First of all since you weren't being consistent.  The change was going to have to be made somewhere (to make things consistant).  Second.  I tried to find the change that would be easiest to make  (i'.e. change to the system that you seemed to be using most.)  Third, as luck would have it, the system i suyggested you use is the one the teacher suggested.  

That might be hard for you to see.  But GoTop leaves one item on the stack.  As I said one item is on the stack when _top is 0.  GoTop sets _top to 0.  So this is the way to go.

--------------------------------------------------

>>..>>void Probe::probeTree(BinTree *TreePtr)
>>  >>     void probeTree(BinTree *TreePtr)
>>     You said:
>>     That declares two functions called probeTree.
>>     No, one is the class decalaration and the other is the function definition.
Not the way it is written.  The second would have to have the "probe::" as well.  You may have had that ain the code and missed that in posting here.  But I assumed that is what you had.  In any case, you were calling the function, as if it were a global function, because you didnt have a probe  varaible before the call.  Does that make sense?

probeTree(&Tree1); // calls global function.
Prb.probeTree(&Tree1); // calls member function or Prb's class.
****************************
>>Probe prb();
>>         prb.probeTree(&Tree1);
>>     The error is:
>>     Structure required on left side of . or .* in func main().
>>     Keep in mind I have no Probe constructor at this point.
Try
Probe prb;
prb.probeTree(&Tree1);

Not parenthesis for the constructor, since there is no constructor..
--------------------------------------------------------
>> forgot to mention, how can size be constant if it is set to 30 in the private >> member definitions?  

You declared _size as an enum that is set to 30.  its value can not be changed anywhere in the program.  Thus it is constant.  You can change it to a new value and recompile and it will be a new constant value.  

>> Since the professor set it to 30 (which to me means 30 possible levels or total
>> possible height) the size must get smaller each time top is incremented.

_size is the size of the entire array.  Not the size of the free space in the array.  The size of the array stays constant so _size stays constant.  The free space does decrease as _top increases, but that doesn't affect _size.  _size-top is the free space.  That changes as _top changes.

>>When we call _top++, does this mean that we are that much further from the top?  
That means that top has increased by one and another item in the array is not considered to be stored in the stack.  Remember the array doesn't change size.  But the part of the array that is considered the stack does.  The array items from [0] to _Itop] are considered part of the stack and [_top] is the top one in the stack.  _Top++ "adds" the next item in the array to the stack.
0
 

Author Comment

by:John500
ID: 1166451
Todd,

The program compiled with:
Probe prb;
prb.probeTree(&Tree1);

but it crashed after I read in a file and then chose to probe.  Any suggestions for testing why?

Also, just to be sure there is no confusion, I may have stated this backwards before:
void probeTree(BinTree *TreePtr) // declared within the class def
void Probe::probeTree(BinTree *TreePtr) // defined in the program

I have written all my functions from Proj 0 as is written above.  I'm sure there is nothig wrong with it.

0
 
LVL 22

Expert Comment

by:nietod
ID: 1166452
Why don't you e-mail me a new copy of everything.  

Probing will crash if you choose a bad option, like probing left when there is no left (we will put in safegaurds, but haven't yet.)  I'll look at the code.
0
 

Author Comment

by:John500
ID: 1166453
Todd,

Ok, will do.
0
 

Author Comment

by:John500
ID: 1166454
Todd,

If
   _trail[0] = TreePtr->_root

   _top must be set to zero in order to print the CurPtr.
   _trail[_top]->print()  // I know we are using CurPtr

What else would need to be fixed?

John
0
 

Author Comment

by:John500
ID: 1166455
Probe works fine!
0
 
LVL 22

Expert Comment

by:nietod
ID: 1166456
There still is the danger that it will crash when you hit an invalid option.  We can fix that by changing the option string that is passed to GetMenuLetter(), like

   char Prompt[100];                       // string used to form the menu prompt string.
   char OptionStr[10];                  // Avaialble menu option letters.
   Prompt[0] = 0;                          // Terminate the prompt string.
  OptionStr[0] = 0;                          // Terminate the prompt string.
   
   if (CurPtr->_left)                      // If there is a left node, then
   {
      strcat(Prompt,"L)eft    ");          // Add on the left option.
      strcat(OptionStr,"L");               // Add on the left option.
   }
   if (CurPtr->_right)                     // If there is a right node, then
   {
      strcat(Prompt,"R)ight   ");          // Add on the right option.
      strcat(OptionStr,"R");               // Add on the right option.
   }
   if (_top > 1)
   {
      strcat(Prompt,"U)p       T)op    "); // Add on the up and top options.
      strcat(OptionStr,"UT ");                // Add on the up and top options.
   }
   strcat(Prompt,"Q)uit");                 // Add on the quit option.
   strcat(OptionStr,"Q");                 // Add on the quit option.

   cout << "Indicate direction to probe:\n\n";
   cout << Prompt;                         // Display the prompt.                           //
   char Option = GetMenuLetter(OptionStr);


Now it will ignore invalid options.  Make sense?

0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

744 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

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now