0

I created a class called BST and it has a member root. i know when i call a deconstructor to class BST it deletes root and frees memory occupied by the class.

I wanted to know that, will the deconstructor deconstruct all the nodes as well associated with the BST object. that is left child and right child of root and their left and right child and so on and so forth.

my guess is a No. in that case i think i will have to do a post order traversal and delete every node manually. is there any way to do it in once. without walking around the tree nodes

#ifndef BST_H
#define BST_H
#include "bst.h"
#include <stdio.h>
#include<iostream>

class bst
{
protected:
    struct node{

        node* p;
        node* lc;
        node* rc;
        int key;
        node(int x,node* p=nullptr,node* lc=nullptr,node* rc=nullptr):key(x){

        }
        ~node(){
        std::cout<<"decontrucotr node";
        }

    };
    node* nil=new node(0);
    node* root;


public:


    bst();
    virtual ~bst();
    void put(int x);
    void in_order(node* x);
    void in_order();
    void pre_order(node* x);
    void pre_order();




    private:
};

#endif // BST_H

functions are defined in this

#include "bst.h"
#include <stdio.h>
#include<iostream>

bst::bst():root(nil)
{



}

bst::~bst()
{

std::cout<<"deconstructor tree"<<'\n';
}

void bst::put(int x)
{

node* k=new node(x,this->nil,this->nil,this->nil);
node* y=this->root;
node* p=y;
while (y != nil){

    p=y;
    if (y->key>x){
        y=y->lc;
    }
    else{
        y=y->rc;
    }
}
if (p==nil){
    this->root=k;
    k->lc=this->nil;
    k->rc=this->nil;
    k->p=this->nil;
}
else if(p->key>x){
    p->lc=k;
    p->lc->p=p;
    k=p->lc;
    k->lc=this->nil;
    k->rc=this->nil;
}
else{
    p->rc=k;
    p->rc->p=p;
    k=p->rc;
    k->lc=this->nil;
    k->rc=this->nil;
}
}

void bst::in_order(node* x){
if(x != nil){
this->in_order(x->lc);
printf("%d%c",x->key,'\t');
this->in_order(x->rc);
}
}
void bst :: in_order(){
this->in_order(this->root);
printf("%c",'\n');

}
void bst::pre_order(node* x){
    if(x!=this->nil){
    printf("%d%c",x->key,'\t');
    pre_order(x->lc);
    pre_order(x->rc);


}
}
void bst::pre_order(){
pre_order(this->root);

printf("%c",'\n');
}
Nikhil
  • 71
  • 7
  • 4
    Quick question: have you looked into STL's Smart Pointers? http://stackoverflow.com/questions/106508/what-is-a-smart-pointer-and-when-should-i-use-one http://en.cppreference.com/w/cpp/memory/shared_ptr I apologize if you're _required_ to use raw pointers or can't use C++11 or later, but if you aren't, take a look at the smart pointers. Memory management can be a real bear. – kayleeFrye_onDeck Jun 09 '16 at 20:43
  • I think that's not possible. For every `new` in your code, there should be an equivalent `destroy`. You can deep-travel you tree, and start destroying elements from the leaf nodes to the root. – Wikiti Jun 09 '16 at 20:43
  • 5
    @Wikiti I think you meant there should a `delete` for every `new`. Might sound like nitpicking but sometimes words matter. It is neither called "destroying" nor "deconstruct", but newed objects have to be deleted (which includes calling the destructor, but thats not all what is happening). – 463035818_is_not_an_ai Jun 09 '16 at 20:51
  • I think it's a good policy to every time you new something put in the code to delete it. – Ian Jun 09 '16 at 20:52
  • 3
    @Ian: No, every time you new something, replace it with `std::unique_ptr`. – GManNickG Jun 09 '16 at 20:58
  • @Ian and if you dont use smart pointer it is not good policy but a must – 463035818_is_not_an_ai Jun 09 '16 at 20:59
  • @GManNickG There are quite a large number of cases in C/C++ where managed pointers are not useful/a good idea. –  Jun 09 '16 at 21:04
  • @WilliamKappler the *vast* majority of cases in C++ would be better served with managed pointers. For beginners, it is most definitely good advice to encourage the use of smart pointers. – Steve Lorimer Jun 09 '16 at 21:05
  • @SteveLorimer Totally disagree. Dynamic memory management is what makes C/C++ what it is. Sooner or later, fully understanding that is *required* to program working C/C++. And in my experience, it's usually sooner. Telling someone to use smart pointers in response to questions about proper use of dynamic memory is no more helpful to learning C/C++ than telling them to try Java would be. –  Jun 09 '16 at 21:08
  • @WilliamKappler there's a difference between understanding how and why something works the way it does, and encouraging the use of a superior solution. – Steve Lorimer Jun 09 '16 at 21:10
  • 1
    @WilliamKappler what are some examples where `new` and `delete` are preferred over managed pointers? All I can think of is cases where I'm returning data to C code which obviously can't use managed pointers. Even then I'd use `unique_ptr` until I'm ready to release and return the pointer. – Kevin Jun 09 '16 at 21:11
  • 1
    I learned C++ 20 years ago. I'm quite happy with new and delete. – Ian Jun 09 '16 at 21:14
  • @Kevin I am programming a library where I have to interact with the graphics system (OpenGL). That means a large number of generic-memory buffers. A managed pointer solution would be a mess and do everything other than make it safer/simpler. I am quite sure there are plenty of other cases for similar low-level operations. –  Jun 09 '16 at 21:14
  • @WilliamKappler: "would be a mess" is a pretty poor argument. I've written plenty of OpenGL wrappers, none of them made my code harder to read or reason about. You just take your clean-up code and put it in something that's guaranteed to run, such as a destructor. Scoped exit-guards are the prototypical lowest layer of this. – GManNickG Jun 09 '16 at 21:19

2 Answers2

3

I created a class called BST and it has a member root. i know when i call a deconstructor to class BST it deletes root and frees memory occupied by the class.

In the implementation you have shown, the ~bst destructor is essentially empty (logging does not count), it is not freeing any nodes at all.

I wanted to know that, will the deconstructor deconstruct all the nodes as well associated with the BST object.

The bst object itself is destructed. Its child nodes are not, no.

that is left child and right child of root and their left and right child and so on and so forth.

Not in the current implementation, no. You need to code that logic.

in that case i think i will have to do a post order traversal and delete every node manually.

In the current implementation, yes.

is there any way to do it in once. without walking around the tree nodes

Either:

  1. code the ~node destructor to delete its immediate child nodes. Then the ~bst destructor can delete its root node, and all of the other nodes under it will get deleted recursively.

  2. Use smart pointers, such as std::unique_ptr, instead of raw pointers. Let the compiler do all of the work for you.

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
1

"Do I have to manually deconstruct all objects?"

Yes, because C/C++ does not track memory you tell it you are going to self-manage, which is what using new and / or malloc implicitly says.

If you want it to, there are options for varying use cases. Aside from those, though, you must always pair every allocation (new) with exactly 1 deallocation (delete).

"I wanted to know that, will the deconstructor deconstruct all the nodes as well associated with the BST object?"

No, because you did not tell it to.

You should:

~node()
{
    std::cout<<"decontrucotr node";
    delete lc;
    delete rc;
}

That said, bst::put(int x) makes no sense to me and I find it quite possible there are similar errors in it. You should strive to write documented, clear code - especially if you plan on asking other people for help with it.

  • what you said created an infinite recursion – Nikhil Jun 09 '16 at 21:17
  • @Nikhil Infinite *recursion* should not be possible in a delete operation. If you make a child its own parent (indirectly even) I would expect a crash when you try to `delete` an object twice, at least if you built this as debug. Perhaps infinite recursion could occur without debug; it would be undefined behavior. If it just keeps running forever without crashing, I would encourage you to add in some debug functionality to print the node structure to the console, and if the cause is not obvious, ask a separate question. –  Jun 09 '16 at 21:21
  • it crashed when i remove cout. but with cout it just keeps on printing the string written in deconstructor. i have made a sentinel object nil is it becausse of that? nil is just there so that when i inherit from this class to Red black trees – Nikhil Jun 09 '16 at 21:23
  • @Nikhil Actually, I did not realize that. Why would you use a sentinel object in place of null? Use null or nullptr to represent empty pointers. `delete` on a null is a no-op. `delete` on an object, even if you call it "nil", deletes the object. So you are, now that I look at it, deleting `nil` recursively. As for the printing not making it crash... undefined behavior. No idea why that fixes the crash, but the print to console is not itself actually influencing this. –  Jun 09 '16 at 21:27
  • yeah without nil it will work i tried that first but i need to nil for red black tree. nil sentinel makes the coding easier its just a helping tool. I was looking for a way to make it work even with the nil. – Nikhil Jun 09 '16 at 21:29
  • @Nikhil I don't see why you would need it. But if you for some reason absolutely do, if `nil` is accessible to `node`, you can add in a check `if( lc != someobjectwithnil->nil ) { delete lc; }`, and same for `rc`. –  Jun 09 '16 at 21:31