Recursive Tree Traversal

I have an algorithm for a recursive tree traversal. It's job is to traverse a tree adding up all the number values stored inside the tree. The tree stores, integers, doubles, strings, and tree's themselves as data members. So node's containing strings and tree's are just skipped, but other nodes are summed together to find out the total of all the values in the tree (not including other values inside a tree as a data value). There is a stub method inside the tree class that calls the actual method inside the Node class to do the work. Unfortunately i get a bogus number returned. Any ideas???

Code:

double Node::total() { double result; IntTreeItem *x; FloatTreeItem *y; if( this->getLeft() != NULL ) { if( typeid( this->getLeft()->getValue() ).name() == typeid( x ).name() || typeid( this->getLeft()->getValue() ).name() == typeid( y ).name() ) result += this->getLeft()->total(); //it gets added else this->getLeft()->total(); //it isn't the right type, skip it } //this is where the value gets calculated if( typeid( this->getValue() ).name() == typeid( x ).name() ) { result += (double)( ( dynamic_cast<IntTreeItem*>( this->getValue() ) )->getValue() ); //cast TreeItem down to IntTreeItem, envoke it's value method, then convert to double } else if( typeid( this->getValue() ).name() == typeid( y ).name() ) { result += ( ( dynamic_cast<FloatTreeItem*>( this->getValue() ) )->getValue() ); //cast TreeItem down to FloatTreeItem, envoke it's value method (which gives a double) } if( this->getRight() != NULL ) { if( typeid( this->getLeft()->getValue() ).name() == typeid( x ).name() || typeid( this->getLeft()->getValue() ).name() == typeid( y ).name() ) result += this->getLeft()->total(); //it gets added else this->getLeft()->total(); //wrong type, it doesn't get added } return result; }

Low-hanging fruit: result is never initialized to 0. If that doesn't fix it, we'll look harder. :)

ha, guess I overlooked that. Unfortunately, after initializing result to zero, I get an answer back of 0 after the algorithm is implemented. Am I doing the type casting properly? I cast it down to the object it's supposed to be, then implement that objects getValue() method in order to grab the number it's holding. I'm also excluding strings or trees from being processed...any other ideas? Thanks.

Does getValue() return a pointer? You're comparing types at the top, to a IntTreeItem * and a FloatTreeItem *. You should compare to the types returned by those functions.

Or alternatively, maybe you meant to test tree->getLeft() instead of tree->getLeft()->getValue().

All Node's store generic data items, which can be an int, double, string, or tree. A node's getValue() returns a generic data item object. invoking the objects getValue() method returns the value stored in that object, either int, double because string and tree do not contain that method. So a node's getValue() returns an object (in a hierarchy), while the objects getValue() returns a primitive type stored in that object. I hope that makes sense....I use recursion to traverse the nodes, but I also want to see what's being stored in those nodes, then see what's being stored inside those objects.

So a Node->getValue() returns a ____TreeItem pointer, for some fill in the blank? And then a ____TreeItem->getValue() returns an actual value? I'm getting a little lost in the same names here, but that's what I see in the code. Is that right?

Also, in your left and right hand cases, I think you do need to add the total into your result; for example, if your tree had strings in both first-level children, you would get 0, because you wouldn't add any of the grandchildren (or great-grandchildren, etc.) into the total. Rely on the middle case not adding in to deal with the string/tree cases.

Yes, your initial conclusion on my code is right. Except string and tree objects do not have a getValue() method. Which is why I have to check what kind of object it is before I envoke the getValue() method. I've tried simply using the recursive call to the method and adding it to the result in the top and bottom code. However I thought the middle code was correct. And I do only add to the result if it's the right kind of object.

p.s. By top, bottom, and middle code I'm referring to the three blocks, top and bottom are the recursive call if statements, and middle is the if/else statement which adds to the result.

Quote:

Originally Posted by John_L

Yes, your initial conclusion on my code is right. Except string and tree objects do not have a getValue() method. Which is why I have to check what kind of object it is before I envoke the getValue() method. I've tried simply using the recursive call to the method and adding it to the result in the top and bottom code. However I thought the middle code was correct. And I do only add to the result if it's the right kind of object.

p.s. By top, bottom, and middle code I'm referring to the three blocks, top and bottom are the recursive call if statements, and middle is the if/else statement which adds to the result.

I think you may have got what I said backward: your middle case is correct; don't try to check types in the top and bottom cases: just add what comes back in. (Note that if, for instance, the left child is a string and has no children, it will return 0 to you just like you want, since the middle case won't trigger and there is no left or right and you initialized to zero at the start.) You will have to check if there is a left child first, of course, but not what type it is.

I think I get it, here's what I changed. The changed code still gives a result of 0 however.

Code:

double Node::total() { double result = 0; IntTreeItem *x; FloatTreeItem *y; //Write the if statement like this? if( this->getLeft() != NULL ) { result += this->getLeft()->total(); //it gets added } if( typeid( this->getValue() ).name() == typeid( x ).name() ) { result += (double)( ( dynamic_cast<IntTreeItem*>( this->getValue() ) )->getValue() ); //cast TreeItem down to IntTreeItem, envoke it's value method, then convert to double } else if( typeid( this->getValue() ).name() == typeid( y ).name() ) { result += ( ( dynamic_cast<FloatTreeItem*>( this->getValue() ) )->getValue() ); //cast TreeItem down to FloatTreeItem, envoke it's value method (which gives a double) } //write the if statement like this? if( this->getRight() != NULL ) { result += this->getRight()->total(); //it gets added } return result; }

The if statements are right (you don't want to try to do something like NULL->total(), that's bad).

Okay, another thought: if this->getValue() is an IntTreeItem*, why the dynamic_cast? (I'm guessing the answer is: otherwise the compiler doesn't know what kind it is.)

We can definitively say that nothing is getting added (unless you have 1 and -1 of your nodes). Thought: print out (this->getValue()).name() each time through. It'll probably be a mangled thing, but you might be able to tell whether or not you're getting an IntTreeItem* (you can always print typeid(x).name() too). I don't have enough experience with C++ to know whether the return of getValue() is always going to be cast to the base Node* type (I'm assuming Node is the base for all these things).

And speaking of casting, the cast to double should be irrelevant and useless in that integer case.

The dynamic cast is to cast the Generic object into the object I need in order to envoke the certain objects method. But I know the problem now after printing the typeid name. in the middle if/else block i'm always getting a Generic Data Item (TreeItem) as the typeid name. I thought it wouldn't give me the top of the hierarchy, but the specific object in the hierarchy that it was. How can I ask the program what object i'm working with, I want to know if the object in the node is a StringItem, IntItem, FloatItem etc..I know all nodes contain generic items, but I want to specificlly know which item it really is.

Quote:

Originally Posted by John_L

The dynamic cast is to cast the Generic object into the object I need in order to envoke the certain objects method. But I know the problem now after printing the typeid name. in the middle if/else block i'm always getting a Generic Data Item (TreeItem) as the typeid name. I thought it wouldn't give me the top of the hierarchy, but the specific object in the hierarchy that it was. How can I ask the program what object i'm working with, I want to know if the object in the node is a StringItem, IntItem, FloatItem etc..I know all nodes contain generic items, but I want to specificlly know which item it really is.

I don't know where all the people who know C++ went, so I'll keep going. I'm guessing you have a virtual TreeItem* getValue() defined? If so, you'll always only ever get a TreeItem* back. One idea (which seems like a silly hack, probably because it is) is to define a virtual function like getType() which returns values from an enum (1 for integer, 2 for float, or whatever) that you can check. (Obviously each class would know which type it is so it can return the right thing.) If you get INT or DOUBLE back (or whatever you call the things), you can then dynamic_cast to the appropriate class and call getValue().

thanks for your help. I decided just to use two try catch blocks, try doing a dynamic cast and getting the value inside to add it to the result, and catching the exception and do nothing. Seems to work fine.