Please help me

This is a discussion on Please help me within the C++ Programming forums, part of the General Programming Boards category; The first node in the tree is the only one that gets anything written to it. void build_tree(int size, LIST_I ...

  1. #1
    Registered User
    Join Date
    May 2002
    Posts
    4

    Please help me

    The first node in the tree is the only one that gets anything written to it.




    void build_tree(int size, LIST_I data, TREE& t)
    {

    int ct;
    for (ct = 0; ct < size; ++ct) {
    PT_NODE p = new NODE;
    p->info = data[ct];
    p->left = NULL;
    p->right = NULL;
    if (t == NULL)
    t = p;
    else {
    PT_NODE ptr = t,
    back = NULL;
    while (ptr){
    back = ptr;
    if (p->info < ptr->info)
    ptr = ptr->right;
    else
    ptr = ptr->left;
    }
    if (back != NULL && p->info < back->info)
    back->left = p;
    else if (back != NULL)
    back->right = p;
    }
    }

    }

  2. #2
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,493
    can you provide more information please?

    and use code tags.

  3. #3
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,600
    Hmm...I haven't done trees yet, but there are a couple of things that come to mind:

    (1) "back" is undeclared. Unless this is some sort of global variable...(bad idea anyway)

    (2) You attempt to point a type POINT_NODE to a type TREE. Are they really compatible?
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

  4. #4
    Ted
    Ted is offline
    Registered User
    Join Date
    Aug 2001
    Posts
    52
    It seems that the first node is the only node in your tree.
    You don't seem to be moving any pointers.
    Try not to batch process your tree. insert yor nodes one at a time.
    You need to first write out your pseudo code. Some thing like:
    Code:
    statusEnum insertNode( treeType *root, keyType key )
    {
        treeType *newNode, *current, *parent = NULL;
    
        current = root;
    
        // search for insertion point
        while current != to NULL
    	if key == current->key
                return duplicate_key
    	move parent instep with current
            compare if key < current->key
    		current = current->left
            else current = current->right
        end while
    
        // Allocate new node
        newNode = new treeType()
        newNode->parent = parent
        newNode->left = NULL
        newNode->right = NULL
        newNode->key = key
    
        // Insert node in tree
        if parent
            if newNode->key < parent->key
                parent->left = newNode
            else parent->right = newNode
        else root = newNode
    
        return status_ok
    } // end
    hth,

  5. #5
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,600
    I dunno. Try this, but modify it to fit your data declarations. I'm still working on printing the contents...


    Code:
    
    
    
    typedef struct TREE{
    TREE *right;
    TREE *left;
    TREE *back;
    int info;
    };
    
    
    
    
    
    
    
    int add_node(TREE *t, int info) {
    
    
    TREE * ptr = t;
         
         ptr->back = NULL;    ///...redundant but innocuous...will always be top node...
         
         while (ptr)   //...could just as well be "while(1)"
           {
            if(ptr->info == info)
             return -1;
    
            if (info < ptr->info)
             {
               if(ptr->right != NULL)
                 ptr = ptr->right;
               else
                 break;
              }
            
             else
              {
                if(ptr->left != NULL)
                  ptr = ptr->left;
                else
                  break;
              }
            }
    
    
    
      TREE * p = new TREE;
    
      p->info = info;
      
      p->left = NULL; 
    
      p->right = NULL;
    
      p->back = ptr;
    
      if (t == NULL) t = p; 
    
      if ( p->info < ptr->info)
        ptr->right = p;
     
      else
        ptr->left = p;
    
    return 0;
    }
    
    
    
    
    
    
    
    
    
    void build_tree(int *size, int data[], TREE *t)
    { 
    
    int ct;
    int duplicate;
    
    for (ct = 0; ct < *size; ++ct)
     { 
    
      duplicate = add_node( t, data[ct]);
    
      if(duplicate) *size--;
    
    
     }
    
    }
    
    
    
    
    
    
    
    int main(int argc, char *argv[])
    {
     TREE tree;
     tree.left = 0;
     tree.right = 0;
     tree.back = 0;
     tree.info = 0;
    
     int i;
     int size = 10;
     int array[ size ];
    
     for(i = 1; i <= size; i++)
     array[i - 1] = i;              //...edited...//
    
    
     build_tree( &size, array, &tree);
    
    
    
      return 0;
    }
    Last edited by Sebastiani; 05-06-2002 at 09:25 PM.
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

  6. #6
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,600
    I still don't know if this is right.

    Ted: can you tell me if I am doing it right/wrong?

    ...here was the printout to file:



    Starting from the top, again...
    Attaching to left side!


    Starting from the top, again...
    Taking a left!
    Attaching to left side!


    Starting from the top, again...
    Taking a left!
    Taking a left!
    Attaching to left side!


    Starting from the top, again...
    Taking a left!
    Taking a left!
    Taking a left!
    Attaching to left side!


    Starting from the top, again...
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Attaching to left side!


    Starting from the top, again...
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Attaching to left side!


    Starting from the top, again...
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Attaching to left side!


    Starting from the top, again...
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Attaching to left side!


    Starting from the top, again...
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Attaching to left side!


    Starting from the top, again...
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Taking a left!
    Attaching to left side!




    Here's the printing code...


    Code:
    
    #include <stdio.h>
    
    
    FILE *fp;
    
    typedef struct TREE{
    TREE *right;
    TREE *left;
    TREE *back;
    int info;
    };
    
    
    
    
    int add_node(TREE *t, int info) {
    
    
    TREE * ptr = t;
         
         ptr->back = NULL;    ///...redundant but innocuous...will always be top node...
         
         fprintf(fp,"\n\nStarting from the top, again...\n");
    
         while (ptr)   //...could just as well be "while(1)"
           {
            if(ptr->info == info)
             { fprintf(fp,"Duplicate !\n");  return -1; }
    
            if (info < ptr->info)
             {
               if(ptr->right != NULL)
                 { fprintf(fp,"Taking a right!\n");  ptr = ptr->right; }
               else
                 break;
              }
            
             else
              {
                if(ptr->left != NULL)
                 { fprintf(fp,"Taking a left!\n"); ptr = ptr->left; }
                else
                  break;
              }
            }
    
    
    
      TREE * p = new TREE;
    
      p->info = info;
      
      p->left = NULL; 
    
      p->right = NULL;
    
      p->back = ptr;
    
      if (t == NULL) t = p; 
    
      if ( p->info < ptr->info)
        { fprintf(fp,"Attaching to right side!\n");  ptr->right = p; }
     
      else
        { fprintf(fp,"Attaching to left side!\n");  ptr->left = p; }
    
    return 0;
    }
    
    
    
    
    
    
    
    
    void build_tree(int *size, int data[], TREE *t)
    { 
     fp = fopen("DEBUG.txt", "w");
    
     if(!fp) return;
    
    int ct;
    int duplicate;
    
    for (ct = 0; ct < *size; ++ct)
     { 
    
      duplicate = add_node( t, data[ct]);
    
      if(duplicate) *size--;
     }
    
     fclose(fp);
    }
    
    
    
    
    
    
    
    int main(int argc, char *argv[])
    {
     TREE tree;
     tree.left = 0;
     tree.right = 0;
     tree.back = 0;
     tree.info = 0;
    
     int i;
     int size = 10;
     int array[ size ];
    
     for(i = 1; i <= size; i++)
     array[i-1] = i;
    
     build_tree( &size, array, &tree);
    
    
    
    
    
    
    
      return 0;
    }
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

  7. #7
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,600
    BTW: I just wanted to point out to "teedee" that although not a big "no-no", this thread belongs on the C board.
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

  8. #8
    Registered User
    Join Date
    May 2002
    Posts
    4
    Thanks for everyone's help. I actually have it working now after hours and hours of work.

    Why does this belong on the c board?

  9. #9
    Ted
    Ted is offline
    Registered User
    Join Date
    Aug 2001
    Posts
    52
    Your add_node() and your buildTree() logic is out of whack.

    Follow my psuedo code. Normally your inout data will be read
    from a file or from the keyboard. Call insertNode( treeType *,
    keyType ) from main or a getKeyInput(). Pass the root pointer
    and the key value to insertNode(). Normally, you don't move the
    root pointer, there for:
    Code:
      current = root;
    
    
    Next, we must search for the insertion point, this continues until
    current points to NULL.  If the tree is empty, the root is NULL
    Else keep moving current until it points to a NULL child pointer
    
        // search for insertion point
        while current   // while the root or current are not NULL
    
    Usually we don't want duplicate keys, so you need a means to deal with them
    	if key == current->key
                            return duplicate_key // an enum
    
    
        // Update your pointers
    	parent = current   // move parent instep with current
        
        // compare 
        if key < current->key
            current = current->left
        else
            current = current->right
        end while
    
    
        you don't need a newNode->parent pointer, or what you refer
    to as a back pointer.
    
    
    
    // Insert node in tree, when current points at a NULL child
    pointer, parent is pointing to the NULL child pointer's parent
        if parent  
            if newNode->key < parent->key
                parent->left = newNode
            else parent->right = newNode
        else root = newNode
    I hope this explains it for you.

  10. #10
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,600
    Hmm, thanks. I will work on it.



    Why does this belong on the c board?
    Because typically, if this were implemented with C++, there would be no functions taking the "parent" pointer as arguments (except in special cases) because it is usually the "parent" calling the function.:

    instead of calling build_tree like traditional C, such as:

    TREE t;
    LIST_I data;
    int size;

    build_tree(size, data, &t) ;



    It would look more like:

    TREE t;
    LIST_I data;
    int size;

    t.build_tree(size, data) ;

    Later in the program, you could call functions with "t" taking no parameters since the data could be referenced internally.

    For instance, "size" and "data" could become "unofficial" members using a special set of member functions:





    class TREE { public:

    //...stuff




    int set_size( int Size = 0) {

    static int size = Size; //...initialized just once...

    return size;
    }




    int get_size() { return set_size(); } //...access "unofficial" member



    void build_tree(int Size, int data[]) {

    set_size( Size );

    //...rest of function...
    }




    ///...rest of class...




    };




    There are many other advantages to using C++. You might look into it.
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

Popular pages Recent additions subscribe to a feed

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