Thread: Binary Tree Insertion Problem

  1. #1
    Registered User
    Join Date
    Jan 2002
    Posts
    63

    Binary Tree Insertion Problem

    howdy boyz n gals:

    I am finally able to insert and find an item in my binary tree!! However we has a couple of small problems still. I don't think i'm inserting properly. My desired tree is as follows; based on this input file 1(2,3(10)),4(5(8),6(9),7) i wish to achieve 1 as the root (which i get based on the following code, but thats it i think) followed with 2 at the left of 1 and 4 at the right of 1. to the right of 2 i want 3 and to the left of 3 i want 10. that makes the left branch of the root. on the right i would like 5 at the left of 4 and 8 to the left of 5 and 6 to the right of 5. and 9 and seven to the left and right of 6. i'm pretty sure its my insertion method and telling 'insert' which node to insert after, and not my printtree function. here is my code for the insert and print functions, any help appreciated. thanks.

    Code:
    //from my main function
    
                                       cout << "root: " << number << '\n';
    							t.insert(number);
        							
                                       char child;
    							while(in >> child)
                                       {
                                               
                                               switch(child)
                                               {
                                               case '(':in >> number;
                                                       cout << "Insert Left Subtree: " << 
                                                               number <<'\n';t.insert(number);break;
    											
                                               case ')':if(in >> child){
    											while(child != ',')
    												in >>child;
    											}
    											else break;
                                               case ',':in >> number;
                                                       cout << "Insert Right Subtree: " << number << 
                                                                        '\n';t.insert(number);break;
    											
                                               default:cout << "Unknown char\n";break;
                                               }
                                               
                                       }
           
    
                t.printTree();
    
    //from my class function for insert
    template <class Comparable>
            void BinarySearchTree<Comparable>::
            insert( const Comparable & x, BinaryNode<Comparable> * & t ) const
            {
                if( t == NULL )
                    t = new BinaryNode<Comparable>( x, NULL, NULL );
                else if( x < t->element )
                    insert( x, t->left );
                else if( t->element < x )
                    insert( x, t->right );
                else
                    ;  // Duplicate; do nothing
            }
    
    //my print function
     template <class Comparable>
            void BinarySearchTree<Comparable>::printTree( BinaryNode<Comparable> *t ) const
            {
                if( t != NULL )
                {
                    printTree( t->left );
                    cout << t->element << endl;
                    printTree( t->right );
                }
            }
    SS3X

  2. #2
    Xcal82
    Guest

    This looks familiar...

    This looks just like an assignment i have to do for CS 202...hmmm

  3. #3
    xcal82
    Guest
    Anyway, I'm having a hard time with this too, but what I think you need to do is you need to keep track of the left and right parenthesis. Everytime you see a left parenthesis, think of it as advancing, whenever you have a right parenthesis, you are going back where you came from. Using that type of logic, I think you can get it, but then again, I'm working on it too.

  4. #4
    Unregistered
    Guest
    yea u know it man.. 202 it is.. lol

    i got the parenthesis down, thanks

    but what i don't got is when i return from FIND, which is in the weiss book.. its returning a pointer. how do i get it to return the NODE that the pointer has? u know how insert gives you root back, i want the NODE that find returns.. thats the real prollem...

  5. #5
    Xcal82
    Guest
    Do you think you can point me in the right direction as far as getting the tree implemented correctly? I made an extra node going to the previous node...do you think that will help?

    Frusterated

  6. #6
    Registered User
    Join Date
    Jan 2002
    Posts
    552
    >1(2,3(10)),4(5(8),6(9),7)
    I dont understand the format for the input. What are the exact specifications for the input?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Tree scope? problem
    By tms43 in forum C++ Programming
    Replies: 5
    Last Post: 11-01-2006, 10:13 PM
  3. problem in storing data in a binary search tree
    By alavardi in forum C Programming
    Replies: 5
    Last Post: 02-13-2005, 03:20 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. Problem with binary search tree :(
    By Unregistered in forum C Programming
    Replies: 10
    Last Post: 05-01-2002, 10:31 PM