Jump to content
  • Advertisement
Sign in to follow this  
mike74

deleting binary tree

This topic is 4674 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Could someone tell me if this code is right for deleting a binary tree? If so, is there a better way? void deleteallnodes(Node *root) { if (root == NULL) return; deleteallnodes(root->left); deleteallnodes(root->right); delete root; } Thanks. mike http://www.coolgroups.com/

Share this post


Link to post
Share on other sites
Advertisement
That can certainly be optimised by removing one of the recursive calls, but it's otherwise fine.
PS Don't forget to use [code][/code] tags when posting code.

Share this post


Link to post
Share on other sites
What do you mean when you talk about removing one of the recursive calls?

mike
http://www.coolgroups.com/

Share this post


Link to post
Share on other sites
Quote:
Original post by mike74
What do you mean when you talk about removing one of the recursive calls?

mike
http://www.coolgroups.com/
Currently deleteallnodes calls itself twice, however with a simple modification it can be made to only call itself once. This both increases speed, and helps avoid stack overflow errors, depending on how balanced the tree is.

You'll have to answer Andrew's question before I show you how though.

Share this post


Link to post
Share on other sites
If this is not an homework, I would say you to add

root->left = root->right = NULL

after you deleted the pointers.

Otherwise you must forget about this! [smile]

Share this post


Link to post
Share on other sites
Quote:
Original post by blizzard999
If this is not an homework, I would say you to add

root->left = root->right = NULL

after you deleted the pointers.

Otherwise you must forget about this! [smile]


Neither of those values should be accessed after root is deleted - that area of memory will have been freed, and other parts of the program given access to them. If you want to do this in case they're used anyways (e.g. you have a bug) you could add:

#ifdef DEBUG
root->left = 0xBAADF00D;
root->right = 0xBAADF00D;
#endif //def DEBUG


This will hopefully cause the code to crash instead of silently succeeding whenever you try to reproduce that unreproducable bug which refuses to show itself except in user's experiences (in which case of course it will allways occur), if the node is used post-deletion. I choose BAADF00D (Bad food) as it is a common debug fill pattern indicating you've accessed memory you shouldn't have. If you ever see an access violation refering to an address like BAADF23F, you can tell you've used some area of uninitialized memory as a pointer...

Share this post


Link to post
Share on other sites
Quote:
Original post by MaulingMonkey
Quote:
Original post by blizzard999
If this is not an homework, I would say you to add

root->left = root->right = NULL

after you deleted the pointers.

Otherwise you must forget about this! [smile]


Neither of those values should be accessed after root is deleted - that area of memory will have been freed, and other parts of the program given access to them. If you want to do this in case they're used anyways (e.g. you have a bug) you could add:

#ifdef DEBUG
root->left = 0xBAADF00D;
root->right = 0xBAADF00D;
#endif //def DEBUG


This will hopefully cause the code to crash instead of silently succeeding whenever you try to reproduce that unreproducable bug which refuses to show itself except in user's experiences (in which case of course it will allways occur), if the node is used post-deletion. I choose BAADF00D (Bad food) as it is a common debug fill pattern indicating you've accessed memory you shouldn't have. If you ever see an access violation refering to an address like BAADF23F, you can tell you've used some area of uninitialized memory as a pointer...


Yes you are right.
However although not usefull this is not an error


delete( root->left );
delete( root->right );
root->left = root->right = NULL;
delete( root ); // sure: now root is an untouchable pointer!!!


I wrote that because it's an habit of mine...I'm used to write C++ code and the first method I write is always the Clear one so my class would seem something like this



class Node{
public:

Node(){
left = right = NULL;
}

~Node(){
Clear();
}

void Clear(){
delete( left );
delete( right );
left = right = NULL;
}
...

Node* left;
Node* right;

}


Share this post


Link to post
Share on other sites
No, it's not homework. It's for a kd-tree I'm building. So, how do you delete with one recursive call?

Share this post


Link to post
Share on other sites
Quote:
Original post by blizzard999
If this is not an homework, I would say you to add

root->left = root->right = NULL

after you deleted the pointers.

Otherwise you must forget about this! [smile]


Why? You're about to delete root anyway. And once this happens, left and right will be overwritten with 0xFEEEFEEE by the debug heap (assuming MSVC).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!