# Thread: Tree traversal eating/creating elements?

1. ## Tree traversal eating/creating elements?

(Relevant code below, .cpp and .h attached)

Funny title, I know, but that's what it seems to be doing. OK, explanation:

I'm supposed to read in a fictitious list of teachers from a text file, which contains: name, availability and courses they are qualified to teach. I also create an array of binary search trees, each one representing a subject. I put the teachers' names in an array names[], sort the array, then insert the int corresponding to the names array in the subjects[] array if they are qualified for that course. So far, so good, I think. The problem is two-fold:

1) When I traverse the trees and cout the node->key values, it turns out that they are a bit off. For example, the key values are initially 3 4 6 |0 3 6 7| 1 3 7 9| 0 1 2 5 9| 0 3 4 5 7 8| 0 2 4 5 7 8 9 , then when using traversal to find them (inorder traversal, MorrisInorder, to be specific), they become (no bars here for separation, because I don't know what it is doing) 3 4 6 6 4 3 7 6 3 0 9 7 3 1 9 5 2 1 0 8 7 5 4 3 0 9 8 7 5 4 2 0. Not only that, after applying my break-it-down-into-an-array-and-send-it-back function, they are a tiny bit more off. Maybe I did some fuzzy math with the multiplication and modulus division? Looks right to me. Which brings me to the second problem:

2) I broke the elements off of the tree into an array because I need to balance the tree, and in order to do that, need to put the elements in an array. I have a nice balance() function from my textbook, but it doesn't give details about the function. Specifically: what do the ints 'first' and 'last' represent? I can pass it the array easily enough, but what the heck are the other two arguments?:

Code:
```template<class T>
void BST<T>::balance(T data[], int first, int last) {
if (first <= last) {
int middle = (first + last)/2;
insert(data[middle]);
balance(data,first,middle-1);
balance(data,middle+1,last);
}
}```
Function for putting node->keys in an array and deciphering on the other end w/modulus division
Code:
```template<class T>
int BST<T>::MorrisInorder() {
char myArr[50];
char b[2];
BSTNode<T> *p = root, *tmp;
static int y = 1;
static int total = 0;

while (p != 0)
if (p->left == 0) {
cout << p->key;
p->key *= y;
p = p->right;
}
else {
tmp = p->left;
while (tmp->right != 0 &&// go to the rightmost node of
tmp->right != p)  // the left subtree or
tmp = tmp->right;   // to the temporary parent of p;
if (tmp->right == 0) {   // if 'true' rightmost node was
tmp->right = p;     // reached, make it a temporary
p = p->left;        // parent of the current root,
}
else {
cout << p->key << " ";          // else a temporary parent has been
p->key *= y;
y *= 10;
total += y;
// found; visit node p and then        cut
tmp->right = 0;     // the right pointer of the current
p = p->right;       // parent, whereby it ceases to be
}                        // a parent;
}
return (total);
system("PAUSE");
}```
and here's how I decipher it when it comes back as a big int:

Code:
```int myIntArray[50];
for(int z = 0; z < 6; z++)
{
int v = 0;
int w = 0;
int aa = 10;
int myInt = subject[z].MorrisInorder();//combined with balance function
while(aa < 10*myInt)
{
myIntArray[w] = myInt%aa;
myInt = myInt%aa;
aa *= 10;
w++;
v++;
//balance.myIntArray()??????????
//insert myIntArray el's
int ab = 0;
while(myIntArray[ab] >= 0 && myIntArray[ab] <= 9)
{

subject[z].insert(myIntArray[ab]);
ab++;
}
}
}```
I've tried program tracing, but I can't tell where the error is, or why it happens. Any help would be greatly appreciated.

Thanks,

-Patrick

2. Nobody has any ideas?

-Patrick

3. Wading through over 15K of someone elses template code isn't something you do in a casual moment.

Have you tried to simplify the problem at all?

Like testing your ideas on a non-templated version just to see what happens?

4. I'm pretty sure the one of the two snippets I pasted (or both) are the problem, so the .cpp and .h are probably unnecessary (not 100% sure, though). I was hoping someone would notice some glaring error that I'm overlooking.

-Patrick

5. This looks like a strong candidate for a for loop:
Code:
```                  int ab = 0;
while(myIntArray[ab] >= 0 && myIntArray[ab] <= 9)
{

subject[z].insert(myIntArray[ab]);
ab++;
}```
Can't you think of a better way to do this?
Code:
```                        switch(tmp)
{
case 0:
subject[0].insert(k); // Insert the teacher array element into the tree
break;
case 1:
subject[1].insert(k); // Insert the teacher array element into the tree
break;
case 2:
subject[2].insert(k); // Insert the teacher array element into the tree
break;
case 3:
subject[3].insert(k); // Insert the teacher array element into the tree
break;
case 4:
subject[4].insert(k); // Insert the teacher array element into the tree
break;
case 5:
subject[5].insert(k); // Insert the teacher array element into the tree
break;
}```
This system call is never executed, being after the return statement:
Code:
```        return (total);
system("PAUSE");```

6. dwks,

Thanks for the style critique (not trying to be a smartass, really - your constructive criticism is appreciated). Do you a no-no that really sticks out in either of those snippets?

-Patrick

7. Specifically: what do the ints 'first' and 'last' represent? I can pass it the array easily enough, but what the heck are the other two arguments?:
They represent the min and max indexes from your array. Pass 0 as first and the array length-1 as last.
You should then notice that the function causes inserts to happen in the depth-first order of a nicely a balanced binary tree.

8. You could have a look at Prelude's pages: http://eternallyconfuzzled.com/brain.html

Also see aihorizon's page: http://www.aihorizon.com/essays/basiccs/trees/index.htm

9. Thanks, guys, I actually got it working. Thanks for all of your help!

-Patrick