Quesiton about classes/dynamic allocation.

I'm making a binary tree class with a lot of pointers to objects. The thing is they aren't allocated using new. I have a node class with a Node* for left and right, and whenever I add a node it just uses uses the rules of a binary search tree to point the pointers to the added node. The thing is when I want to destroy them. I know that the synthesized destructor doesn't get rid of the objects being pointed to, but if they aren't allocated with new should I be worried about the cleanup?

So basically what I'm saying is lets say I add nodes and have a tree of like height 5. Would just destroying the link from the head to all descendants suffice, or does my destructor need to recursively deconstruct the objects?

Quote:

---

whenever I add a node it just uses uses the rules of a binary search tree to point the pointers to the added node.

---

So where are the nodes stored? What makes them persistent?

>if they aren't allocated with new should I be worried about the cleanup?
If you don't control allocation, you shouldn't be expected to worry about release. Just snip the node out of your structure and let the calling code deal with the memory. The big thing I would worry about is node corruption. Because you don't control the memory, it's possible that a node will be released while still linked to the tree.

Well the actual Nodes are Classes, they only contain three members, two for the children, and one for the data. The actual tree class has a pointer to a Node for the head and that should be it. Everything works off pointers, but nothing is stored in arrays or something.

Edit: By "calling code deal with the memory" is this something I should implement or is this a compiler specific call.

It's a requirement on the user of your tree.

But you haven't answered my question: where are the nodes stored, if not on the heap?

I'm guessing the same place other classes are stored when not dynamically allocated.

I create a head node, initially it has a set value and two node pointers, I insert another node by constructing it initially with null children, and a value, and insert it as a BST, then point the head node to that, then so on and so on.

Quote:

---

Originally Posted by indigo0086

I'm guessing the same place other classes are stored when not dynamically allocated.

I create a head node, initially it has a set value and two node pointers, I insert another node by constructing it initially with null children, and a value, and insert it as a BST, then point the head node to that, then so on and so on.

---

When clas is not dynamically allocated it is stored in the stack
When this variable exits the scope - the class is destroyed.

Are you saying that in your class you just point to the local variables that are actually destroyed after function exits

or the add function of the tree does something smarter than that?

Well there's a node class and a tree class. All the node classes are contained within the tree class so I guess when the tree class goes out of scope all the node classes get destroyed. So the class itself would be destroyed when it goes out of scope. I was just wondering if I needed to do any special type of destruction of each node down to the child, or do I just let the default synthesized destructor do all the work without worry of a memory leak.

Could you post your add function? and tree class definition?
I personally cannot answer the quetion without seeing the code

I haven't started writing the tree implementations yet, I wanted to know before I wrote them if there would be a conflict. It really is a node question because when the tree is destroyed so are the nodes.

Code:

---

#define NULL 0

class Node
{
    public:
        Node(int d = 0): left(NULL), right(NULL), data(d) {}
        Node(const Node&);
        Node& operator=(const Node&);
        ~Node() { remove_children(this); }

        Node *l_child() const { return left; }
        Node *r_child() const { return right; }
        Node get_data() const { return data; }

        bool has_children() const { return (left != NULL) || (right != NULL); }
        bool leaf() const { return (left == NULL) && (right == NULL); }

    private:
        Node *left, *right;
        int data;

        void remove_children(Node*);
};

---

Code:

---

#include "bintree.h"

//========================= Node Implementation ================================

//copy constructor
Node::Node(const Node& aNode)
    :left(aNode.left), right(aNode.right), data(aNode.data) {}


Node& Node::operator=(const Node& aNode)
{
    if(&aNode != this)
    {
        if(has_children())
            remove_children(this);
        left = aNode.left;
        right = aNode.right;
        data = aNode.data;
    }
    return *this;
}

void Node::remove_children(Node* n)
{
    n->left = n->right = NULL;
}

---

Currently - because you don't allocate memory in any function - you don't need to free it...

Okay, there are basically two ways to handle the nodes in a tree (or in any linked data structure). You can completely control the memory for nodes by creating them and destroying them internally:

Code:

---

// Insert an owned node
node *add ( node *root, int data )
{
  if ( root == 0 )
    root = new node ( data );
  else {
    int dir = root->data < data;
    root->link[dir] = add ( root->link[dir], data );
  }

  return root;
}

---

This is preferred simply because the memory is under your control and you don't have to worry about some yoyo in another module screwing with it. The other option is to accept existing nodes and simply handle the links to fit it into your structure:

Code:

---

// Insert an unowned node
node *add ( node *root, node *obj )
{
  if ( root == 0 )
    root = obj;
  else {
    int dir = root->data < obj->data;
    root->link[dir] = add ( root->link[dir], obj );
  }

  return root;
}

---

This is useful if you want to support non-dynamic nodes (nodes created on the stack) and it makes working with free lists easier because you move the maintenance of the free list elsewhere and can focus on the tree algorithms.

cool.

Better question, I've noticed that if I do re-direct pointers the objecst still won't be destroyed until after the call to main finishes, is there a way to destroy the objects when I disconnect the pointers to the node classes?