0

I am loading a set of integers int a binary which is no problem, its when Im trying to increase their frequencies I am running into some difficulties. As it stands the program crashs if any of the numbers repeat themselves, any suggestions?

void BST::insert(int d)
{  
    tree_node* t = new tree_node;
    tree_node* parent;
    t->data = d;
    t->freq = 1;
    t->left = NULL;
    t->right = NULL;
    parent = NULL;
    bool found = false;
    // is this a new tree?
    if(isEmpty()) 
    root = t; 
    else
    {
        found = search(d);
        if(found==true)
        {
          t->freq=t->freq + 1;
        }
        else  
         {
             //insertions are as leaf nodes
             tree_node* curr;
             curr = root;
             while(curr)
             { 
             // Find the Node's parent
                 parent = curr;
                 if(t->data > curr->data) 
                 curr = curr->right;
                 else curr = curr->left;
             }

        if(t->data < parent->data)
           parent->left = t;
        else
           parent->right = t;
        }
    }
}

bool BST::search(int d)
{
tree_node * t = root;
bool found = false;
while (!found && t!=0)
 {
      if (d < t->data) // descend left
      t = t->left;
      else if (t->data < d) // descend right
      t = t->right;
      else // item found
      found = true;
 }
 return found;
}
2
Contributors
1
Reply
3
Views
5 Years
Discussion Span
Last Post by firstPerson
0

Your logic seems false.

Line 3: You create a node t
Line 16: You search for the int value then then updated t's frequency? But t is a new node not necessarily inside the binary tree!

What you want is a helper function that returns the Node who has the value x. Then increment that node's frequency.

tree_node * _find(const tree_node& root,const int val){
 if(!tree_node) return NULL;
 else if(val > root.value()) _find( root.rightNode(),val);
 else if(val < root.value()) _find( root.leftNode(),val);
 else{ return root; /* found */ }
}

void insert(int val){
  tree_node *n = _find(val);
  if(n != NULL){
    /* added previously, so just updated count */
       n->incrementCount();
  }else{ 
      /* not found */
      _insertHelper( val ); //just inserts a new node with val into the tree
  }
}
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.