deleting binary tree
Author
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/
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.
PS Don't forget to use [code][/code] tags when posting code.
Author
What do you mean when you talk about removing one of the recursive calls?
mike
http://www.coolgroups.com/
mike
http://www.coolgroups.com/
Quote:Original post by mike74Currently 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.
What do you mean when you talk about removing one of the recursive calls?
mike
http://www.coolgroups.com/
You'll have to answer Andrew's question before I show you how though.
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]
root->left = root->right = NULL
after you deleted the pointers.
Otherwise you must forget about this! [smile]
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 DEBUGroot->left = 0xBAADF00D;root->right = 0xBAADF00D;#endif //def DEBUGThis 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...
Quote:Original post by MaulingMonkeyQuote: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 DEBUGroot->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;}
Author
No, it's not homework. It's for a kd-tree I'm building. So, how do you delete with one recursive call?
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).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
