Re: destructor of binary tree
On Jan 27, 1:47 am, Erik Wikstr=F6m <Erik-wikst...@telia.com> wrote:
On 2008-01-26 21:19, xz wrote:
[...]
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.
Which doesn't necessarily solve the problem.
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).
That's fine in theory, but I have a case in practice (a trie,
rather than a tree, but the problem is the same) where in some
cases, order of initialization issues mean that I need a
complete static initialization. The only solution I've found to
date is inheritance: the static instances are instances of
StaticSetOfCharacter, which also defines the const functions
(lookup, etc.). The user uses a derived class SetOfCharacter,
which adds the non-const functions and a destructor which
deletes all of the internal data. This still doesn't support
mixing of static nodes with non-static nodes, but in my case, at
least, that's almost an advantage. What's not pretty, of
course, is that the user has to be aware of the two types---if
he's not modifying data, it's not SetOfCharacter const&, it's
StaticSetOfCharacter const&. But as I said, I haven't found a
better solution.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34