How to increment the value whenever I find the key? BST

Question

I'm able to retrieve all the words from a text file and put them in a tree, I just can't increment the occurence by one whenever I find the data in the tree. Each word is now displayed one time but with an occurence of 1, it doesn't increment.

this is my class Node

class Node{

    private:
        Node *left;                     //left child
        Node *right;                    //right child
        std::string num;
    public:
        int data;                       //number
        Node();                         //constructor
        void setData(string num, int data);         //sets number in node
        string getData();                   //return numbers from node
        int getOcc();
        void setLeft(Node *l);          //sets left child pointer
        Node* getLeft();                //returns left child pointer
        void setRight(Node *r);         //sets right child pointer
        Node* getRight();               //return right child pointer
};

Node::Node(){
    this->left = NULL;
    this->right = NULL;
}


void Node::setData(string num, int data){
    this->num = num;
    this->data = data;
}


string Node::getData(){
    return this->num;
}

int Node::getOcc(){
    return this->data;
}


void Node::setLeft(Node *l){
    this->left = l;
}

Node* Node::getLeft(){
    return this->left;
}

void Node::setRight(Node *r){
    this->right = r;
}

Node* Node::getRight(){
    return this->right;
}

this is my class BST

class BST{

    private:
        Node * root;        //root node pointer

    public:
        BST();                                  //constructor
        ~BST();                                 //destructor
        void Insert(string num, int data);                  //Inserts new number in tree
        bool find(string num);                      //finds whether a number is present in tree
        void min();                             //find and print minimum number in the tree
        void max();                             //find and print maximum number in the tree
        void save_file(string filename);        //save the tree to file
        void Delete(string num);                    //deletes a number from tree
        void LoadFromFile(string filename);     //loads numbers from file to tree
        void Print();                           //print tree to stdout


        //private functions used as helper functions in the public operations
    private:
        void printHelper(Node *root);
        bool findHelper(Node *root,string num);
        void InsertHelper(Node* current, Node* newnode);
        void findMinHelper(Node* current);
        void findMaxHelper(Node * current);
        void saveHelper(ofstream &fout, Node* current);
        Node* DeleteHelper(Node *current, string num);
        Node * findMaximum(Node * n);
        void clear(Node *currnt);
};

BST::BST(){
    this->root = NULL;      //root is NULL in the start
}

BST::~BST(){
    clear(root);            //delete all nodes
}


void BST::clear(Node* current){
    if(current == NULL)
        return;

    clear(current->getLeft());          //clear left subtree
    clear(current->getRight());         //clear right subtree
    delete current;                     //delete this node
}


void BST::Insert(string num, int data){

    //create new node to be inserted
    Node *n = new Node();
    n->setData(num, data);
    n->setLeft(NULL);
    n->setRight(NULL);


    if(this->root == NULL)      //if root is null, simply add at root
        root = n;


////////// IN HERE, I TRIED TO INCREMENT INCREMENTATION THE OCCURENCE BY 1
    else if (find(n->getData()) == true){
        int h = n->getOcc();
        h++;
        n->setData(num, h);
    }
    else
        InsertHelper(root,n);   //call helper to insert
}


void BST::InsertHelper(Node* current, Node* newnode){
    if(current == NULL)
        return;

    //node should be inserted at right subtree
    if(current->getData() <= newnode->getData()){

        //if no node at right
        if(current->getRight() == NULL )
            current->setRight(newnode);     //add at right node

        else
            InsertHelper(current->getRight(), newnode);     //insert in right subtree
    }
    else{

        if(current->getLeft() == NULL){         //if no node at left
            current->setLeft(newnode);          //add at left
        }else{
            InsertHelper(current->getLeft(), newnode);      //insert in left subtree
        }
    }
}


bool BST::find(string num){
    return findHelper(root,num);
}


bool BST::findHelper(Node *current,string num){
    if(current == NULL)
        return false;

    if(current->getData() == num)       //if number is found
        return true;

    if(num < current->getData())        //if number is less than current node
        return findHelper(current->getLeft(),num);      //go to left tree
    else
        return findHelper(current->getRight(),num);     //go to right tree
}


void BST::min(){
    findMinHelper(root);
}

void BST::findMinHelper(Node* current){
    if(current == NULL)
        return;

    if(current->getLeft() == NULL)          //if no node at right
        cout<<current->getData();           //current has min data
    else
        findMinHelper(current->getLeft());  //check on left subtree
}

void BST::max(){
    findMaxHelper(root);
}

void BST::findMaxHelper(Node * current){
    if(current == NULL)
        return;

    if(current->getRight() == NULL)             //if no node at right
        cout<<current->getData();               //current node has max data
    else
        findMaxHelper(current->getRight());     //check on right subtree
}



void BST::Print(){
    printHelper(root);
}

void BST::printHelper(Node *current){
    if(current == NULL)     //stop if NULL
        return;

    printHelper(current->getLeft());        //print left tree
    cout<<current->getData() << " " << current->getOcc() << " ";        //print current node data
    printHelper(current->getRight());       //print right tree
}

void BST::Delete(string num){
    root = DeleteHelper(root,num);
}

Node* BST::DeleteHelper(Node *current, string num){
    if(current == NULL)
        return NULL;

    Node *tobeReturned;

    if (current->getData() == num) {          //if key is found

        if (current->getLeft() == NULL) {        //no node at left

            tobeReturned = current->getRight();
            delete current;
            return tobeReturned;          //right subtree should replace this node

        } else if (current->getRight() == NULL) {

            tobeReturned = current->getLeft();
            delete current;
            return tobeReturned;
        } else {

            //find maximum node in the left subtree
            Node * maxnode = findMaximum(current->getLeft());

            //copy values from max node to this node
            //      current->setData(maxnode->getData());

            //delete the max node
            current->setLeft(DeleteHelper(current->getLeft(), num));
        }
        cout<<"Deleted!!!";
    } else {        //not found
        if (num < current->getData()) {
            current->setLeft(DeleteHelper(current->getLeft(),num));
        } else {
            current->setRight(DeleteHelper(current->getRight(), num));
        }
    }
    return current;
}

Node* BST::findMaximum(Node * n){
    if(n->getRight() == NULL)       //if no node at right, current is maximum
        return n;
    return findMaximum(n->getRight());      //find in right subtree
}

In my main, I insert the words one by one using a loop with a an occurence =1 tree.Insert(s,1); but the end result is always each word displayed with an occurence = 1

You may want to read this: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Andreas Wenzel, Jul 22 '20 at 22:15
You may want to read this official help page: [How to create a minimal reproducible example](https://stackoverflow.com/help/minimal-reproducible-example) — Andreas Wenzel, Jul 22 '20 at 22:18
Just as a side note: [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/q/1452721/12149471) — Andreas Wenzel, Jul 22 '20 at 22:37

score 2 · Answer 1 · answered Jul 22 '20 at 22:01

2

You need to make getOcc() return a reference so you can update the value. At the moment you are incrementing a copy of the occurence.

Try

Node.h

int &getOcc();

Node.cpp

int &Node::getOcc()
{
    return this->data;
}

and use it like this

int &h = n->getOcc();
++h;

answered Jul 22 '20 at 22:01

MatzZze

391
1
7

1

`else if (find(n->getData()) == true){` seems wrong to me. Please try `else if (find(num)) {` – MatzZze Jul 22 '20 at 22:13
same thing still 1, I've been stuck here for 2 days :'( – KingAzaiez Jul 22 '20 at 22:17
1

Have you tried debugging your find method? I would start there to see exactly what happens. – MatzZze Jul 22 '20 at 22:20
1

Another problem is that you always increment the root node instead of the one you really want – MatzZze Jul 22 '20 at 22:22
so it's better if i implement it in the insertHelper ? the current node ? – KingAzaiez Jul 22 '20 at 22:23
1

Got the problem hopefully now xD On Insert you are always creating a new Node. You then increment on the newly created object but not on the one in the tree. So you should rework your find method to return a Node*. If it is found it should return the matching node else nullptr. You can then increment the occurrence – MatzZze Jul 22 '20 at 22:27
thanks alooot my friend, I'm so thankful for your help :D – KingAzaiez Jul 22 '20 at 22:29

score 2 · Accepted Answer · answered Jul 22 '20 at 22:49

The member function Insert has a memory leak when a node with specified data already exists in the binary tree because in this code snippet

    else if (find(n->getData()) == true){
        int h = n->getOcc();
        h++;
        n->setData(num, h);
    }

it is not freed. And moreover the member function setData is applied to this newly created node that has nothing common with already existent nodes of the binary tree.

The function and its auxiliary function InsertHelper can be rewritten the following way

void BST::Insert(string num, int data)
{
    InsertHelper( root, num, data );   //call helper to insert
}

and

void BST::InsertHelper( Node * &current, string num, int data )
{
    if ( current == nullptr )
    {
        // create new node to be inserted
        current = new Node();
        current->setData( num, data );
        current->setLeft( nullptr );
        current->setRight( nullptr );
    }
    else if ( num < current->getData() )
    {
        InsertHelper( current.getLeft(), num, data );
    }
    else if ( current->getData() < num )
    {
        InsertHelper( current.getRight(), num, data );
    }
    else
    {
        int h = current->getOcc();
        h++;
        current->setData(num, h);
    }
}

To make the functions to work change also these two functions

Node * & getLeft();

Node * & Node::getLeft(){
    return this->left;
}

and

Node * & Node::getRight();

Node * & Node::getRight(){
    return this->right;
}

You just did it perfectly boss. THAAAANKKSSS How can I improve myself like this ? — KingAzaiez, Jul 22 '20 at 23:01
@KingAzaiez It is useful to try to make assignments described in other questions at SO. — Vlad from Moscow, Jul 22 '20 at 23:02
I can't thank you enough Mr Vlad. I've been stuck in this for 2 days, and you did it without even using the find function. — KingAzaiez, Jul 22 '20 at 23:03
@KingAzaiez The function find is not useful in this case because it makes the function Insert inefficient. — Vlad from Moscow, Jul 22 '20 at 23:05
I'll take your advice and make the questions I find here as assignments to improve. Thanks alooooot Mr Vlad — KingAzaiez, Jul 22 '20 at 23:06

How to increment the value whenever I find the key? BST

2 Answers2