0

Im having a bit of a problem with my binary search tree. For some reason my pointers arent connecting correctly. I'm pretty sure everything is correct but when i run it I keep getting this as the result.

It inputs the numbers 1 5 7 9.

void insert(string word,vector<treeNode> &x) //*&x
{    
      bool inserted = true;
      int node = 0;
      treeNode *t = new treeNode;
      treeNode *f = new treeNode;    
      if(x.size() == 0)
         { 
        t->word=word;   
        x.push_back(*t);
         }
      else
        {   
            t=&x[0];
            f->word=word;
            while(inserted)
          {
              if(word == t->word)
              {
              t->count++;
              inserted = false;  
              break;
              }
               if(word > t->word)
               {  
                      
                      if (t->right == NULL)
                       {
                       t->right=f;
                       x.push_back(*f);
                       inserted = false;
                       }else{ t=t->right; }
                        
               }
               else {
                      
                      if (t == NULL)
                       {
                       t->left=f;
                       x.push_back(*f);
                       inserted = false;
                       }else{ t=t->left;}
               }
               
         }
   }          
       
}

Output is this.

Populating Data table...

1 5 7 9
Reading back words
[0] [count 1] 1[] [5]
[1] [count 1] 5[] []
[2] [count 1] 7[] []
[3] [count 1] 9[] []

2
Contributors
1
Reply
2
Views
6 Years
Discussion Span
Last Post by Greywolf333
0

Im having a bit of a problem with my binary search tree. For some reason my pointers arent connecting correctly. I'm pretty sure everything is correct but when i run it I keep getting this as the result.

It inputs the numbers 1 5 7 9.

void insert(string word,vector<treeNode> &x) //*&x
{    
      bool inserted = true;
      int node = 0;
      treeNode *t = new treeNode;
      treeNode *f = new treeNode;    
      if(x.size() == 0)
         { 
        t->word=word;   
        x.push_back(*t);
         }
      else
        {   
            t=&x[0];
            f->word=word;
            while(inserted)
          {
              if(word == t->word)
              {
              t->count++;
              inserted = false;  
              break;
              }
               if(word > t->word)
               {  

                      if (t->right == NULL)
                       {
                       t->right=f;
                       x.push_back(*f);
                       inserted = false;
                       }else{ t=t->right; }

               }
               else {

                      if (t == NULL)
                       {
                       t->left=f;
                       x.push_back(*f);
                       inserted = false;
                       }else{ t=t->left;}
               }

         }
   }          

}     

Output is this.

Populating Data table...

1 5 7 9
Reading back words
[0]  [count 1] 1[] [5]
[1]  [count 1] 5[] []
[2]  [count 1] 7[] []
[3]  [count 1] 9[] []

end quote.

You're missing the recursion part. After you do these:

else{ t=t->right; }

}else{ t=t->left;}

You are stopping. The concept is that once it's found that t->right (for example) is not null, you have to do the search all over again, except that you start the search at t->right or t->left, until you finally reach a spot that's null where it can be placed.

But to do this you have to recall your function recursively from inside your function. And you have to have a way of saving your current location in the tree. To do this you have to change your function to accept the current node. The current node when you start will be the root. Do not rely on a vector to save your root.

void insert(string word,treeNode* x)

Then, you would have something like:

...else{insert(word, t->right);}  //note you shouldn't set t=t->right... just PASS t->right.
...//and further down below
...else(insert(word, t->left);}

There may be other minor problems, but that is the biggest one. Hope this helps.
Greywolf

Edited by mike_2000_17: Fixed formatting

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.