c++ delete entire binary search tree

Question

for some reason my nodes don't seem to be deleting. it looks as though it traverses to the end ok but after the node is "deleted" it still has the data in it. i've also tried free(bNode) and bNode = NULL instead of delete bNode but they all give the same result.

The cout and display functions were just put in when I was trying to debug. I just don't understand why its not working, i hope i'm not missing something simple.

struct
Book{
char title [50];
char url [75];
Book *left;
Book *right;
};

void deleteAllBooks (Book *bNode){
    if(bNode==NULL) return;                                             
    if(bNode->left !=NULL){
        cout << endl << "deleting left" << endl;
        deleteAllBooks(bNode->left);
    }
    if(bNode->right !=NULL){
        cout << endl << "deleting right" << endl;
        deleteAllBooks(bNode->right);
    }
    cout << endl << "deleting node " << bNode->title << endl;
    delete bNode;
    displayBookTree(bNode);
}
void displayBookTree(Book *bNode){
    if(bNode==NULL){
        cout << "No books" << endl;
        return; 
    }
    if(bNode->left !=NULL){
        displayBookTree(bNode->left);
    }
    if(bNode->right !=NULL){
        displayBookTree(bNode->right);
    }
    cout <<"Title: " << bNode->title << endl;
    cout <<"URL: " << bNode->url <<endl;
}

For one thing delete doesn't set the pointer to NULL, and you only check for null. — dutt
– dutt, Commented Nov 21, 2013 at 8:18
i tried using bNode = NULL but I still had the data... just ran it again like that and the data was removed from the pointer in the delete function but outside the function there is still data in the pointer that was passed into the delete function. hmm — Covertpyro
– Covertpyro, Commented Nov 21, 2013 at 8:23
The problem would go away by using std::unique_ptr<Book> inside Book. All this manual memory management makes code hard to read and frail. — MSalters
– MSalters, Commented Nov 21, 2013 at 8:36
The misunderstanding you have is that you think delete must remove your data. It doesn't have to. All it has to do is call the destructor and free the memory. You data might still be there, except now it's in free memmory so sooner or later it will probably get overwritten. — john
– john, Commented Nov 21, 2013 at 8:52
i got it so the tree is emptied out in the deleteAllBooks function but if i call deleteAllBooks(Student->bookTree); the bookTree is not empty after the call even though it is inside the call. what am i missing? — Covertpyro
– Covertpyro, Commented Nov 21, 2013 at 9:16

Community · Accepted Answer · 2017-05-23 11:50:16Z

2

"Use 0. The "NULL" macro is not type-safe; if you feel that you must use "null", make it a const int instead of the C-style "#define". Also see "The C++ Programming Language" for Stroustrup's argument against the usage of "NULL"."

I would try to change:

 if (bNode==NULL) { ... }

with

 if (!bNode) { ... }

And

if (bNode->left !=NULL) { ... }
if (bNode->right !=NULL) { ... }

with

if (bNode->left) { ... }
if (bNode->right) { ... }

And then take a look to this answer on how correctly delete a Struct!

edited May 23, 2017 at 11:50

CommunityBot

11 silver badge

answered Nov 21, 2013 at 8:38

Luca Davanzo

21.6k15 gold badges124 silver badges152 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

MSalters · Accepted Answer · 2013-11-21 08:40:20Z

0

Easiest solution:

struct Book{
  std::string title;
  std::string url;
  std::unique_ptr<Book> left;
  std::unique_ptr<Book> right;
};

void deleteAllBooks (std::unique_ptr<Book> bNode)
{
  // No code necessary. Literally. But usually you wouldn't even 
  // bother with this function, the default Book::~Book is fine.
}

answered Nov 21, 2013 at 8:40

MSalters

182k11 gold badges171 silver badges376 bronze badges

Comments

Torsten Robitzki · Accepted Answer · 2013-11-21 09:02:40Z

Your solution is correct, but your observations are wrong. When you delete an object, the destructor will be executed for that object. In your case, this destructor has no visible side effect, because all your data members are plain old data types that do not have a destructor on there own. Using an object after it was deleted, invokes undefined behavior and your observation is one possible incarnation of "undefined behavior".

Your test for != 0 before calling deleteAllBooks() is redundant:

void deleteAllBooks ( Book *node ) 
{
    if( node ) 
    {
        deleteAllBooks( node->left );                                            
        deleteAllBooks( node->right );                                            
        delete node;
    }
}

does the same, but might be easier to understand.

And don't mix free/alloc with new/delete. If you've allocated an object with new, you have to return it with delete. Otherwise, you will get undefined behavior.

Collectives™ on Stack Overflow

c++ delete entire binary search tree

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related