Solved

Recursive Functions

Posted on 1998-05-27
32
196 Views
Last Modified: 2012-05-04
I'm currently working with the construction and destruction of a tree  My first question is:

Why is the Post Order method (LRV) of traversing a tree used to delete the tree?  Is it because the only parameter necessary to the destructor is the root node which is passed by the pointer last (deleted last).

The above question relates to my problem of knowing what parameter is necessary in a driver function.  I don't know what I'm missing to make the destruction routine work.  I have the following:

The kill function below is called by the destructor:

void BinTree::kill(Node *p)
{  // delete every tree
      if(!p){cout<<"No tree to delete!\n"; return;}
      kill(p->_left);
      kill(p->_right);
      delete(p);
}

The destructor:
BinTree::~BinTree()
{
      kill(_root);
}

In the main program if the user chooses to initialize the tree or delete everything, I have the following call:

Tree1.kill()

But this results in "too few parameters in call to 'Bin::Tree::kill(node *)'"

Is it necessary to have the user pass a parameter to delete the entire tree?  I have declared Tree1 within main and therefore it is the only tree ever manipulated or created.
0
Comment
Question by:John500
  • 15
  • 10
  • 7
32 Comments
 
LVL 22

Accepted Solution

by:
nietod earned 50 total points
ID: 1164805
answer coming -- again.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1164806
Why is post order traversal needed?  In post order the two descendant nodes do "something" and then the node itself does the something.  In pre-order the node does the "something"  and then the descendants do the "something".  If you tried to delete using pre-order you would get a mess.  The "something" is delete a node. That means that first you would delete a node then delete its descendants, but since you've delete the node, you can't get to the descendants to have them do it.  (actually it can be done, but it is harder)  You don't have that problem in post order.  So why post order traversal?  Its easier.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1164807
You've got the right idea on how to kill a tree, but its got some problems.  Maybe you already know...

If i remove a few lines from kill that aren't going to have any affect on my point we have.

void BinTree::kill(Node *p)
{
   kill(p->_left);
}

In English this says everytime we kill a node we first call the kill for its left node.  When does this stop?  its like an infinite loop, but worse because it will cause a crash rather than a lock up.  Recursive procedures mut have some condition under which recursion will stop.  Otherwise they go on forever.   In most cases the calls that recurse will be in some sort of If like,

void BinTree::kill(Node *p)
   {  
   if (some condition)
      kill(p->_left);

   if (some condition)
       kill(p->_right);

   delete(p);
   }
0
 
LVL 22

Expert Comment

by:nietod
ID: 1164808
Final problem (too few parameters error)

The kill procedure, like most (all?) recursive procedures must be "primed"  That is pased a starting thing to work with and it will work with that thing and its "descendants".  Your destructor handles this correctly.  It passes the root nood to kill which kills the specified node and its descendants.  You need to do that in you main code, like

Tree1.kill(_root);

however don't do that.  First of all _root is probably private to the class, so that's probably won't work.  (If it isn't private, it should be.)  Second of all, its inconvient for the caller.  Better to provide a procedure that does that.  Call it KillWholeTree() or something.  Then the code that uses the class can call that procedure (with no parameters) and the class's destructor can call the procedure.  Make sense.

I'll be gone for about 2 hours.  Hopefully this will keep you occupied.
0
 
LVL 11

Expert Comment

by:alexo
ID: 1164809
Todd, you seem a bit confused.

First, John says (reformatted without permission):

    void BinTree::kill(Node *p)
    {
        if(!p)
        {
            cout<<"No tree to delete!\n"; // [Alex] Remove this sucker!
            return;
        }
        kill(p->_left);
        kill(p->_right);
        delete(p);
    }

So the condition check is already there.  The output is unnecessary, however, since it will be invoked on every leaf node.  Twice.

Next, we have the following marvel:

    BinTree::~BinTree()
    {
        kill(_root);
    }

(Assuming BinTree:kill() is private).  There is no need to have a KillWholeTree() method since the tree's dtor does exactly that.

Ergo, instead of:
    Tree1.kill();
Do:
    delete Tree1;

>> I'll be gone for about 2 hours.  Hopefully this will keep you occupied.
Which leaves you only 22 hours to answer questions today.  Will you manage?
0
 
LVL 22

Expert Comment

by:nietod
ID: 1164810
Alex,
   Hey, I'm not confussed.  Remember I've been programming since rocks were invented :- ).

I'm 99% sure that John's if statement is an error check, not an end to the recursion.  For several reasons, the most obvious on is the fact that it doesn't end the recursion, but also because I'be been looking at lots of his code in the last few weeks and I've got a good idea how he thinks.

Also what you are proposing is to end the recursion one step later than I am instructing him to do (I believe).  That is convenient because it has less conditions to test.  However, I prefer it the other way because it can be more naturally changed to using node classes.

You need a way to kill the tree if the tree object needs to be rebuilt or refiilled with new information.  You could delete and new again if you were working with a dynamically allocated tree, but tree1 in the example is almost certainly a local (no pointer).  I alway provide this type of function in my containers.
0
 
LVL 11

Expert Comment

by:alexo
ID: 1164811
>> Remember I've been programming since rocks were invented :- ).
Urk.

>> I'm 99% sure that John's if statement is an error check, not an end to the recursion.
Agreed.  However, it serves as an EOR check just the same.

>> it doesn't end the recursion
Duh!  It sure does.

>> but tree1 in the example is almost certainly a local (no pointer)
OK.

0
 

Author Comment

by:John500
ID: 1164812
Thanks for all the input.  Going back to Todd's suggestion of:

Better to provide a procedure that does... Call it KillWholeTree() or something.  Then the code that uses the class can call that procedure (with no parameters) and the class's destructor can call the procedure.  Make sense.

I'm not able to follow at this point.  I know this much, that the function "kill" was supposed to be separate from the destructor and which the destructor calls on.  Isn't the func. "kill" the same thing as you are proposing with KillWholeTree?

Also, are you saying that my kill func was written correctly but called incorrectly?  To confirm your statement, yes the _root is private.  The private parts of the BinTree class are:

Node *_root;
int _numNodes;
int _height;

The Node class has private parts of:

char *_word;
int _count;
Node *_left, *_right;

This project is called the Wondrous Word Watcher and should be capable of reading in a file, extracting only words, and then placing them in the tree in dictionary order.  Other things will be needed like deleting and such.
 
0
 
LVL 22

Expert Comment

by:nietod
ID: 1164813
Alex,
Your right it ends recursion.  I totally missed the "return" (twice!).  I saw you had it.  But thought you added it.

John,

>> Isn't the func. "kill" the same thing  as you are proposing with KillWholeTree?

No.  What Kill does is kill a specified node and all the nodes below it.  It doesn't kill the entire tree, just a specified portion of the tree.  It can be used to kill the whole tree.  To do that you call it with a pointer to the root node.  That is what killwholetree() does. KillWholeTree()  (My feelings whon't be hurt if you call it something different!!!) uses Kill to delete te entire tree by passing it the root node.  Remember the class's user can't do that bacause they can't get the root node pointer since it is private.

0
 
LVL 22

Expert Comment

by:nietod
ID: 1164814
>>Also, are you saying that my kill func was written correctly but called
>> incorrectly?  

It was called incorrectly when you wanted to delete the whole tree.  It must alway be passed a pointer to a node.  In that case you didn't pass any pointer so you got a compiler error.  To make matters worse though, the pointer you needed to pass (the root node pointer) was private so you couldn't pass it anyways.  That is why you need a seperate procedure to killthe whole tree.

Was it written correctly?  Well, it ends up it was written more correcly than I thought.  It does end recursion.  However, I think it was probably an accident.  You are treating the end of recursion condition as an error and printing an error message.  That condition is not an error, it is desirable and will occur potentially many times in the delete process.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1164815
Lets talk formatting style.  Some books/instuctors will tell you that anyway that you format the code that makes sense to you is acceptable.  They are wrong--mine is the only acceptable way.

Seriously though.  There are a couple of well established rulles that are followed by almost everyone.  First of all don't put multiple statements on a line, like

cout<<"No tree to delete!\n"; return;

That hides the succesive statements and can make program appear to function very differently than it does.  Format it like alexo did.

   cout<<"No tree to delete!\n";
    return;

Next indent the contents of if statements and loops.  When the if statement or loop ends go back t the previous indent level, like

if (something)
  conditional code
while (condition)
   while code
more code.

You have a habit of keeping the indent like.

if (something)
  conditional code
  while (condition)
      while code
      more code.

That is very confussing to read!  
0
 

Author Comment

by:John500
ID: 1164816
Ok, got it, here is what I've done.

I removed the error statment and the return.  Then, in the main program where the user is given the menu option to i)nit the tree, if the user presses i and return, I call the Tree1.~BinTree().  The program compiled and I'm assuming at this point I can read into the tree and initialize it???  I wanted to wait to hear from you though.

Also could you go over the logic of the recursion process.  If p->_left has reached the end then !p->_left is true, the next statement is kill(p->_right) not delete.  How is the delete performed on p->_left?


0
 
LVL 22

Expert Comment

by:nietod
ID: 1164817
Nope.  Don't listen to Alex, he hasn't been programming as long as I have  :-)

You don't want to call an object's destructor dirrectly (There are rare exceptions,  but you're not going to be doing that sort of stuff for some time.)  What Alexo was saying was that you can destroy the tree object to destroy the tree.  But for that to work, it has to be dynamically allocated, like

BinTree *TreePtr = new BinTree;
// add stuff.
delete TreePtr; // This clears the tree.

But it won't work for a global or locally declared tree, like

BinTree Tree1;

(Actually there is a good chance your code will work fine, but it is "against the rules", so there is no garantee.)  Write a seperate function for deleting the whole tree.  It will be just one line.  (It does what your destructor does.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1164818
>> Also could you go over the logic of the recursion process.  
The logic is as such.

For a particulate node
if there is a left child node.  make the left child node delete itself.
If there is a right child node make the right child node delete itself.
delete this node

Note this is post order traversal.  First do the children and then do yourself. (you being the node)

>>  If p->_left has reached the end then !p->_left is true

Yes.

>> the next statement is kill(p->_right) not delete.  

lets see your code.

>> How is the delete performed on p->_left?

It isn't  There's nothing to delete.  You just said it came to the end.
0
 
LVL 11

Expert Comment

by:alexo
ID: 1164819
>> Don't listen to Alex, he hasn't been programming as long as I have
OK, that does it!  My hunting permit is valid and the senior citizen season is about to reopen.

>> You don't want to call an object's destructor dirrectly
Correct.

>> But it won't work for a global or locally declared tree
The dtor will be invoked when your object goes out of scope.  No problem.

>>  Write a seperate function for deleting the whole tree.
And make your dtor call it instead of duplicating the code.

0
 

Author Comment

by:John500
ID: 1164820
Here is my code for kill() as you requested.

void BinTree::kill(Node *p)
{  // delete every tree
      if(!p)
      kill(p->_left);
      kill(p->_right);
      delete(p);
}
How is this executed, if there is no p->_left then the current p has no left child. But what if it did, it seems to me that a statement like delete p->_left would be necessary.  Do you see what I mean, I can visualize p getting deleted but not p->_left or _right.

Here is my KillWholeTree func. What do you think?
void BinTree::KillWholeTree()
{
  kill();
}


0
What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

 

Author Comment

by:John500
ID: 1164821
Sorry this doesn't sink in quicker but right now I have a destructor that does call a function "kill" that does destroy an entire tree as long as the root is passed.  The root is indeed passed because the destructor provides the call with _root:

BinTree::~BinTree()
{
  kill(_root);
}
Is the only problem here that I need a way to call the destructor from the main menu?  In which case I need a function (not part of the BinTree class) which calls the destructor like:

void killWholeTree()
{
  ~BinTree()
}
Thanks!
0
 
LVL 22

Expert Comment

by:nietod
ID: 1164822
Alex,
>>     The dtor will be invoked when your object goes out of scope.  No problem.
except this probably for a global tree that will need to be cleared and refilled repeatidly in the program.  Even if it is local the there may be a need to clear the tree.

>>     >>  Write a seperate function for deleting the whole tree.
>>     And make your dtor call it instead of duplicating the code.
Now I already suggested that, young whipper snapper.  (Now is that an expression you know?)

John,

remember that an if applies only to the statement that follows it.  You need { } to form a compound statement if you want an if to apply to multiple statements.  Thus, in

     if(!p)
         kill(p->_left);
     kill(p->_right);
     delete(p);

only the one statement is part of the if.  The last two statements are not and will always be executed.  Is that what you want?  Also not the use of an indent to make this clear.

>> if there is no p->_left then the current p has no left child. But what if it did, it
>> seems to me that a statement like delete p->_left would be necessary.
delete p->left is unnecessary.  But do you understand why.  Each node does 2 things on a kill.  
1.  "Tells" its children to kill (delete) themselves.
2.  Deletes itself.

The node doesn't delete its children dirrectly, it calls a procedure that lets them delete themselves.  Make sense?  If not, I'll try an indepth explanation.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1164823
The kill whole tree and destructor stuff is exactly backwards.  As far as you are concerned, you can never call a destructor, so the killwholetree() can't be right.

You want the whole tree to be killed when the destructor is called, so have the destructor call the KillWholeTree().  You want the KillwholeTree() to kill the whole tree, so it should call kill(_root)  i.e. you have the guts of the two functions switched.
0
 
LVL 11

Expert Comment

by:alexo
ID: 1164824
   void BinTree::KillWholeTree()
    {
        kill(_root);
    }

    BinTree::~BinTree()
    {
        KillWholeTree();
        // More stuff...
    }

Also, such small functions can be inline.

0
 
LVL 11

Expert Comment

by:alexo
ID: 1164825
   void BinTree::kill(Node *p)
    {
        if(!p)
            return; // <--- You forgot this one.
        kill(p->_left);
        kill(p->_right);
        delete(p);
    }

>> young whipper snapper.  (Now is that an expression you know?)
Not really.  Please enlighten me, gramps.

0
 

Author Comment

by:John500
ID: 1164826
You wrote:

BinTree::~BinTree()
 {
    KillWholeTree();
    // More stuff...
 }
What more stuff would be necessary if BinTree calls KillWholeTree() to do the job?

0
 
LVL 11

Expert Comment

by:alexo
ID: 1164827
>> What more stuff would be necessary if BinTree calls KillWholeTree() to do the job?
I dunno.  Your BinTree class can hold other data apart from the tree itself.
0
 

Author Comment

by:John500
ID: 1164828
Ok, the "return" statement is back in,  but getting back to the "more stuff" thing, each node is composed of:

char *_word;    // dynamically created
int _count;
Node *_left, *_right;

Won't the kill routine automatically take care of the whole node since the address to the node begins with _word?
0
 
LVL 11

Expert Comment

by:alexo
ID: 1164829
So you'll have to explicitly delete it using:
    delete[] _word;
in the dtor of the node.

Assuming it was allocated as:
    _word = new char[length];
or similar.

0
 

Author Comment

by:John500
ID: 1164830
So,

The following would be necessary in the call:
void BinTree::kill(Node *p)
{  // delete every tree
      if(!p)
            return;
      kill(p->_left);
      kill(p->_right);
      delete[]p->_word;
      delete(p);
}

??
0
 
LVL 22

Expert Comment

by:nietod
ID: 1164831
Deleting an object that stores a pointer does not automatically delete the thing the pointer points to.  So you want the node's destructor do delete the word character array.

However, while you are at it, you can make the node's destructor destroy the part of the tree that is below the node (this is the safest way to handle it).  In other words, the logic of the kill function gets incorporated into the nodes destructor.  When a node gets destroyed, it destroys its left and right nodes in the destructor.  Then to destroy the tree you just delete the root node with delete.  This calls the root node's destructor.  This destructor calls delete on the left and right nodes.  (If they exist) it calls their destructors.  which continues the process. on an on until the tree is gone.

This is the direction I was trying to get you going in, until Alex stepped in and made a mess of things!  :-)
0
 
LVL 22

Expert Comment

by:nietod
ID: 1164832
Comments are getting messed up. My last comment was not in response to john's last one.  This one is.

Your kill is correct.  It handles recursion correctly and it cleans up the node correctly.  However, I would do that stuff inside the node's destructor.  It is safer.  
0
 

Author Comment

by:John500
ID: 1164833
Todd,

This is the Node destructor:

Node::~Node()
{
      if(_word)delete[]_word;
      _left = 0;
      _right = 0;
      _count = 1;
}
Should I or shouldn't I now include delete[]p->_word in the kill function below:
void BinTree::kill(Node *p)
{  // delete every tree
if(!p)
    return;
kill(p->_left);
kill(p->_right);
delete[]p->_word;
delete(p);
}

0
 
LVL 22

Expert Comment

by:nietod
ID: 1164834
No, kill does not need to delete the word.  Kill (or any other function) does not need to clean up a node anymore, because the node will automatically clean up itself.  That is the point to having destructors.

However, there is still some cleanup that kill has to do, it has to kill the left and right nodes.  As it stands now, anytime you delete a node you have to remember to kill the node's left and right nodes first.  That's not a bug.  It will work, but it is room for a bug to creep in.  (Which is the same thing.  If you have room for a bug--you'll have a bug.)
Now, you can change it so that the node's destructor always deletes the node's left and right nodes.  Then this delete logic need to appear only in the destructor.  You won;t have to put it in the code at other places, like you will have to do now.  With this change, the kill function will no longer be needed.  To delete a node you just use the delete operator and it will delete the left and right nodes.  Which in turn will delete their left and right nodes etc.  
the killwholetree() function will no longer call kill()  (kill() will be gone)  It just deletes the root node.  The destructor for the root node will delete the nodes below it and so on and the whole tree dissappears.
0
 

Author Comment

by:John500
ID: 1164835
Todd,

Response via email
0
 

Author Comment

by:John500
ID: 1164836
Great!
0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Suggested Solutions

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…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

708 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

18 Experts available now in Live!

Get 1:1 Help Now