Tree traversal eating/creating elements?

This is a discussion on Tree traversal eating/creating elements? within the C++ Programming forums, part of the General Programming Boards category; (Relevant code below, .cpp and .h attached) Funny title, I know, but that's what it seems to be doing. OK, ...

  1. #1
    Registered User
    Join Date
    Jun 2006
    Posts
    121

    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
    Attached Files Attached Files

  2. #2
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    Nobody has any ideas?

    -Patrick

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,546
    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?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    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. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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");
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  6. #6
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    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. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    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. #8
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  9. #9
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    Thanks, guys, I actually got it working. Thanks for all of your help!

    -Patrick

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Tree traversal
    By recluse in forum C Programming
    Replies: 4
    Last Post: 12-05-2004, 03:00 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21