Binary search tree driving me insane!

Discussion in 'OT Technology' started by hurleyint1386, Apr 17, 2007.

  1. hurleyint1386

    hurleyint1386 Someone has sand in their vagina

    Joined:
    Jan 6, 2005
    Messages:
    3,687
    Likes Received:
    0
    Location:
    Rochester, NY
    This is killing me. Almost everything is finished, but I cannot figure out my problem... one way I do my code, I get a Bus Error when deleting the root of the tree, then the other way, it deletes it, but has some memory leaks it seems. I'm trying so hard to figure it out, tracing it as much as I can. Can anyone figure out what's going on?

    tree.cpp:
    Code:
    #include <iostream>
    #include "tree.h"
    
    using namespace std;
    
    Tree::Tree() : Root( NULL ) {}  // Constructor 
    
    Tree::~Tree() 
    { 
         DestroyTree(Root); 
    } 
    
    void Tree::DestroyTree( Ptr& T ) 
    { 
         if( T !=NULL) { 
             DestroyTree( T->Left ); 
              DestroyTree( T->Right ); 
              delete T; 
              T = NULL; 
         } 
    } 
    
    void Tree::FindNode( int NewItem, Ptr &ParentPtr, Ptr &NodePtr ) 
    { 
         int Flag=0; 
         ParentPtr= NULL; 
         NodePtr = Root; 
         while ( NodePtr!=NULL && !Flag ) 
         { 
              if( NodePtr -> Item == NewItem ) 
                  Flag =1; 
              else 
              { 
                   ParentPtr = NodePtr; 
                   if( NodePtr->Item > NewItem ) 
                NodePtr = NodePtr->Left; 
                   else NodePtr = NodePtr -> Right; 
              } 
         } 
    } 
    
    void Tree::FindAndRemoveMax (Ptr DelNodePtr, Ptr & MaxElPtr)
    {
    
        if (DelNodePtr->Right==NULL)
        {
            MaxElPtr = DelNodePtr;
            DelNodePtr = DelNodePtr -> Left;
            
        }
        else
            FindAndRemoveMax(DelNodePtr->Right, MaxElPtr);
            
    
    }             
    
    void  Tree::DeleteNode(Ptr & NodePtr) 
    { 
            Ptr TempPtr ;  
            TempPtr = NodePtr ;     
            if ( NodePtr->Right == NULL) 
                NodePtr= NodePtr->Left ;
            else      
            {
                if (NodePtr->Left == NULL)  
                    NodePtr = NodePtr->Right ;    
                else  
                {     
                    FindAndRemoveMax(NodePtr->Left, TempPtr) ;
                    NodePtr->Item = TempPtr->Item;     
                } 
             }
                  
            delete TempPtr ; 
    }
    
    void Tree::DeleteElement ( int NewItem) 
    { 
        Ptr  NodePtr, ParentPtr;  
        FindNode(NewItem, ParentPtr, NodePtr) ;
        if (NodePtr == Root)
            DeleteNode(Root);
        else
        {
            if (ParentPtr->Left == NodePtr)
                DeleteNode(ParentPtr->Left);          
            else  
                DeleteNode(ParentPtr->Right);   
        }
    
    } 
    
    
    
    void Tree::InsertItem( int NewItem ) 
    { 
        Ptr ParentPtr, NodePtr, NewNodePtr; 
         NewNodePtr = new Node; 
         NewNodePtr -> Item = NewItem; 
     
        NewNodePtr->Left = NewNodePtr->Right = NULL; 
         FindNode( NewItem, ParentPtr, NodePtr ); 
         if( ParentPtr == NULL ) // Fist Node 
          Root = NewNodePtr; 
         else 
         {
          if( ParentPtr->Item > NewItem ) 
           ParentPtr->Left = NewNodePtr; 
          else ParentPtr->Right = NewNodePtr; 
         } 
    } 
    
    
    void Tree::PrintInOrder( Ptr T) 
    { 
        
         if( T !=NULL) 
         { 
              PrintInOrder( T->Left); 
              cout<<T->Item<<"\t"; 
              PrintInOrder( T->Right ); 
         } 
    } 
    
    void Tree::PrintInPreorder( Ptr T ) 
    { 
         if( T != NULL ) 
         { 
              cout<<T->Item<<"\t"; 
              PrintInPreorder( T->Left ); 
              PrintInPreorder( T->Right ); 
         } 
    } 
    
    void Tree::PrintInPostorder( Ptr T ) 
    { 
         if( T!= NULL ) 
         { 
              PrintInPostorder( T->Left ); 
             PrintInPostorder( T->Right ); 
              cout<<T->Item << "\t"; 
         } 
    }
    
    main.cpp:
    Code:
    #include <iostream>
    #include <fstream>
    #include <string>
    #include "tree.h"
    
    using namespace std;
    
    int main()
    {
         Tree tree; 
         int number, menuItem;
         do
         {
            cout<<"Please choose a menu option: "<<endl;
            cout<<"1. Insert nodes into the tree"<<endl;
            cout<<"2. Delete nodes from the tree"<<endl;
            cout<<"3. Print the current list in Pre Order"<<endl;
            cout<<"4. Print the current list in In Order"<<endl;
            cout<<"5. Print the current list in Post Order"<<endl;
            cout<<"6. Quit program"<<endl;
            cout<<"==============================="<<endl;
            cin>>menuItem;
            if (menuItem == 1)
            {
                 do
                 {
                     cout<<"Enter a number to insert into the tree (9999 to stop): "; 
                     cin>>number; 
                     if (number==9999)
                         break;
                     else
                     {
                          tree.InsertItem( number );  
                    }
                }while(number != 9999); 
            }
            if (menuItem == 2)
            {
                cout<<"Enter a number to delete from the tree: ";
                cin>>number;
                tree.DeleteElement(number);//, tree.Root);
            }
            if (menuItem == 3)
            {
                cout<<"\nPreOrder : "; 
                 tree.PrintInPreorder( tree.Root ); 
                 cout<<endl<<endl;
             }
             if (menuItem == 4)
             {
                 cout<<"\nIn Order : "; 
                 tree.PrintInOrder( tree.Root ); 
                 cout<<endl<<endl;
              }
              if (menuItem == 5)
              {
                 cout<<"\nPostOrder : "; 
                 tree.PrintInPostorder( tree.Root );
                 cout<<endl<<endl;
             }
         } while (menuItem != 6);
         cout<<endl;
    return 0;
    }
    
    with this version, i get the memory leaks. if i change the DeleteElement function to this, then i get the bus error:
    Code:
    void Tree::DeleteElement ( int NewItem) 
    { 
        Ptr  NodePtr, ParentPtr;  
        FindNode(NewItem, ParentPtr, NodePtr) ;
        if (NodePtr == Root)
            DeleteNode(Root);
        if (ParentPtr->Left == NodePtr)
            DeleteNode(ParentPtr->Left);          
        else  
            DeleteNode(ParentPtr->Right);   
    
    } 
    
    Help!
     
  2. hurleyint1386

    hurleyint1386 Someone has sand in their vagina

    Joined:
    Jan 6, 2005
    Messages:
    3,687
    Likes Received:
    0
    Location:
    Rochester, NY
    by the way, i forgot to mention, for the first DeleteElement function, I get the output, but when the new root is changed, the old element stays where it used to be before
     
  3. GOGZILLA

    GOGZILLA Double-Uranium Member

    Joined:
    Jan 16, 2003
    Messages:
    10,760
    Likes Received:
    3
    Location:
    Plantation, FL
    can you post your tree.h? whens this due? i'll take a look when i get a chance
     
  4. hurleyint1386

    hurleyint1386 Someone has sand in their vagina

    Joined:
    Jan 6, 2005
    Messages:
    3,687
    Likes Received:
    0
    Location:
    Rochester, NY
    tree.h
    Code:
    #include <iostream> 
    
    using namespace std;
    
    struct Node { int Item; Node* Right; Node* Left; }; 
     
    typedef Node* Ptr; 
     
    class Tree { 
    
        public: 
             Tree();      // Constructor 
             ~Tree(); 
             void FindNode( int, Ptr&, Ptr& );  // Finds a place to insert new node 
             void PrintInOrder( Ptr );  // Prints in order recrusively 
             void PrintInPostorder( Ptr );  // Prints in Postorder 
             void PrintInPreorder( Ptr );  // Prints in Preorder 
             void InsertItem( int );   // Inserts item into tree 
             void DeleteNode ( Ptr& ); //Deletes item from tree
             void DeleteElement (int);
             void DestroyTree( Ptr& );  // Destroys the entire tree 
             void FindAndRemoveMax (Ptr, Ptr&);
             Ptr Root;      // Pointer to the root of the tree 
    }; 
    

    it's due tomorrow. i've gotten so far. it sucks that it's one little part that i cant seem to fix
     
  5. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán

    In either case, you're not reassigning the pointers for root, right, left. You're leaving them pointing at deleted memory.
     
  6. deusexaethera

    deusexaethera OT Supporter

    Joined:
    Jan 27, 2005
    Messages:
    19,712
    Likes Received:
    0
    That would be your memory leak, right there. Ouch.

    When you start an "If(){" block, your next line should be "}", and only then should you put your code inside the block. Likewise, when you set a pointer, your next line should nullify the pointer, and only then should you insert the code that uses the pointer.
     
  7. hurleyint1386

    hurleyint1386 Someone has sand in their vagina

    Joined:
    Jan 6, 2005
    Messages:
    3,687
    Likes Received:
    0
    Location:
    Rochester, NY
    I'm sorry if I don't understand you, but what do you mean? For every opening bracket, there is a closing bracket. Also, if it's an if statement, and there's only one line afterwards, then there's no need for the brackets, right? I'm sorry, maybe I'm misunderstanding you though
     
  8. deusexaethera

    deusexaethera OT Supporter

    Joined:
    Jan 27, 2005
    Messages:
    19,712
    Likes Received:
    0
    I was just using the "If(){" block as an example. My overall point is that whenever you start something, you should finish it before you write the code that runs in between the start and finish. In the case of your pointers, as soon as you set one = to an address, you should go to the spot in your code where the pointer will be set = 0 and write that statement before you write any other code that uses the pointer.

    And yes, technically you can write an If() block with a single line of conditional code without using {} to contain that single line of code, but it's a bad habit to get into. Anything that you have to explicitly start/open/create, you should explicitly end/close/destroy so you can be absolutely sure that it will work the way you intend. Don't fall back on Java's automated garbage collection either; if you're done using an object, destroy it then and there.
     
  9. hurleyint1386

    hurleyint1386 Someone has sand in their vagina

    Joined:
    Jan 6, 2005
    Messages:
    3,687
    Likes Received:
    0
    Location:
    Rochester, NY
    Never used Java, so that's not an issue lol but I'll see what I can do to fix things up
     
  10. hurleyint1386

    hurleyint1386 Someone has sand in their vagina

    Joined:
    Jan 6, 2005
    Messages:
    3,687
    Likes Received:
    0
    Location:
    Rochester, NY
    Ahhh I still can't figure it out. I thought that what you meant was to assign ParentPtr = NULL and NodePtr = Root, but that's not it.
     

Share This Page