deleting binary tree

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

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 on other sites
Looks fine. Is this a homework question?

Share on other sites
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 on other sites
What do you mean when you talk about removing one of the recursive calls?

mike
http://www.coolgroups.com/

Share on other sites
Quote:
 Original post by mike74What do you mean when you talk about removing one of the recursive calls? mikehttp://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 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.

Share on other sites
Quote:
 Original post by blizzard999If this is not an homework, I would say you to add root->left = root->right = NULLafter 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...

Share on other sites
Quote:
Original post by MaulingMonkey
Quote:
 Original post by blizzard999If this is not an homework, I would say you to add root->left = root->right = NULLafter 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;}

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 on other sites
Quote:
 Original post by blizzard999If this is not an homework, I would say you to add root->left = root->right = NULLafter 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).

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 9
• 34
• 16
• 11
• 12
• Forum Statistics

• Total Topics
634123
• Total Posts
3015649
×