Dumbo strikes again.

[Qubit]

I'm making a binary tree for the parser I intend to write (if I ever get there). All is well, I can store elements in my tree, but when I try to retrieve something, it appears that my root element is NULL. I don't know how this can happen -- I have nothing that changes my root element, other than a simple routine that calls new.

Here is the offending function:


template <class T>
void BinaryTree<T>::addElement(const T& val, BinaryTreeNode<T> *where)
{
if ( where == 0 )
where = new BinaryTreeNode<T>(val);
else
addElement( val, val < where->value ?
where->left : where->right );
}


BinaryTreeNode is a template class containing pointers to the left and right child node and a T that contains a value.

If you need more code, I'll place it online.

For those people who gave me the suggestions for the parser -- well, it looks as if it will be a long time before I can put it to practice, sorry!

[The Kooman]

I think your problem is

template <class T>
void BinaryTree<T>::addElement(constT &val, BinaryTreeNode<T> *where)
{
if ( where == 0 )
where = new BinaryTreeNode<T>(val);

here in this last line.

I hope I can explain it well enough ....

The assignment statement in the last line creates a new BinaryTreeNode and assigns its address to "where". In other words, you are modifying the "where" variable itself by making "where" point to another memory location. Hence, when you leave the function, the change would not be retained. If you want to modify the pointer, you'll have to pass a pointer to the pointer!

Let me try to simplify with the help of some parallels.

Firstly, observe that a pointer is nothing but an integer variable. The only privelege a pointer has is that you can treat the contents of this variable as an address and go and de-reference that addr
ess. So, modifying a pointer is as good as modifying an integer variable (at least in this situation). If you want to see the changes of your modification after returning from the function, you'll have to pass a pointer to the integer.

So, your code should probably look like ......


template <class T>
void BinaryTree<T>::addElement(const T& val, BinaryTreeNode<T> **where)
{
if ( *where == 0 )
*where = new BinaryTreeNode<T>(val);
// blah ... with "where" replaced by "*where"


Hope that wasn't too confusing ;)!

[kmj]

To make it a little simpler, instead of passing a pointer to a pointer, you could pass the pointer by reference...


template <class T>
void BinaryTree<T>::addElement(const T& val, BinaryTreeNode<T> &*where)
{
if ( where == 0 )
where = new BinaryTreeNode<T>(val);


Note the ampersand before where in the argument list; this means you're passing a reference, so changing anything inside the function will change it outside the function, too. Same as using pointers, but a little cleaner.

[Qubit]

Cool, it works! Thanks guys!

I had never thought it would be in the assigment... I always looked for the more obvious dirty errors like a recursion going mad or '=' instead of '=='...

Thx!

[The Kooman]

Originally posted by kmj:
<STRONG>To make it a little simpler, instead of passing a pointer to a pointer, you could pass the pointer by reference...


template &lt;class T&gt;
void BinaryTree&lt;T&gt;::addElement(const T& val, BinaryTreeNode&lt;T&gt; &*where)
{
if ( where == 0 )
where = new BinaryTreeNode&lt;T&gt;(val);


Note the ampersand before where in the argument list; this means you're passing a reference, so changing anything inside the function will change it outside the function, too. Same as using pointers, but a little cleaner.</STRONG>

&lt;rant&gt;
Well, I've heard religious debates about whether or not passing by reference is better then an explicit "*" before the variable (since you'll know, in that case, that you're going to do something whose effects will be seen even after leaving the function)!!

But more than hiding behind those arguments, I'd simply say that it shows how long I've been away from C++ ... its been only C for a long time ... and boy am I glad ;)!

In fact, I'm beginning to miss pascal - I think its a pretty beautiful language! Hmmm, maybe I should brush .. no dig ... up my pascal knowledge ;)!
&lt;/rant&gt;

[Stuka]

Kooman-
You seriously frighten me...C better than C++???? :p Too bad this code is all in C++ - I've got to implement a parser (for relatively simple mathematical expressions) for a class, but I'm stuck using only C :( Oh, well, I'll muddle through.

[The Kooman]

Originally posted by Stuka:
<STRONG>Kooman-
You seriously frighten me...C better than C++???? :p Too bad this code is all in C++ - I've got to implement a parser (for relatively simple mathematical expressions) for a class, but I'm stuck using only C :( Oh, well, I'll muddle through.</STRONG>

Well, honestly, yes ;)! Like Bjarne Stroustrup himself says, "C allows you to shoot your own foot. C++ makes it a lot more difficult, but when it does, it blows away your whole foot" ;)!

I have worked on supporting a CDMA base station controller software that ran into millions of lines of C++ code but it was a pain! Classes were being inherited left, right and center! The data was so well hidden that debugging it was a nightmare ;)!

I agree that theoretically, C++ offers a much cleaner interface than C. But my experience has shown that more often than not, we don't need it to be that clean - and because C++ forces it on us, you have to put your hand round your head just to touch your nose!!

'Nyhow ... thats a seperate religious debate which I'd rather not go into ;)!

As for your assignments ... a wicked thought was to write your parser/evaluator in a language like scheme or haskell and then use the many scheme-&gt;C or haskell-&gt;C convertors ;-) heh, heh!

All the best.

[Stuka]

Koo-
Poorly written/designed C++ will indeed do that to you. But, as has been mentioned before, poor design and/or coding in ANY language is just that - poor design. Excessive inheritance is a Bad Thing. As to the Haskell/Scheme idea.. well, it'd be nice, but we're supposed to use prewritten data structures (stack/queue/list) as a backend, so I don't think it's possible (not to mention I don't KNOW Haskell or Scheme...)