CODEWITHSUNDEEP
c++binary-search-tree
Covertpyro
Covertpyro

Reputation: 199

c++ delete entire binary search tree

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;
}

Upvotes: 1

Views: 436

Answers (3)

Torsten Robitzki
Torsten Robitzki

Reputation: 2555

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.

Upvotes: 0

Luca Davanzo
Luca Davanzo

Reputation: 21548

"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!

Upvotes: 2

MSalters
MSalters

Reputation: 180303

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.
}

Upvotes: 0

Related Questions