Thread: 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

Nobody has any ideas?

-Patrick

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

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

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.

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

-Patrick