Binary Tree insert function not working correctly C++

Question

I'm working on a program that uses a binary tree. The program reads from a text file, storing each word in a binary tree alphabetically and finds how many times the word appeared in the file.

The problem I'm having is that my insert function is not working (the program crashes when attempting to run it). I don't know what's exactly wrong, but I suspect it has to do with my else statement towards the end of the function that deals with the right side of the tree.

Any help with fixing it would be appreciated.

Header File

#include <iostream>
#include <string>

using namespace std;

#ifndef TREE_H
#define TREE_H

class Tree
{
public:
    Tree();
    Tree(string str);
    void traversal (Tree *);
    void read_file();
    void insert(string str);
    ~Tree();
private:
    Tree *left;
    Tree *right;
    string word;
    int count;
};

#endif // TREE_H

Cpp File

#include <iostream>
#include <string>
#include <fstream>
#include "tree.h"

using namespace std;

Tree::Tree()
{ 
    left = NULL;
    right = NULL;
    count = 0;
}

Tree::Tree(string s)
{
    word = s;
}

Tree::~Tree() { }

void Tree::read_file()
{
    ifstream myfile;
    myfile.open("input.txt", ios::out | ios::in | ios::binary);
    if(myfile.is_open()){
        while(myfile.good()) {
            string buffer;
            while(true) {
                char c = myfile.get();
                if(c == '-' || c == '\'' || isalpha(c) ){
                    if(isupper(c)) c = tolower(c); 
                    buffer+=c;
                }
                else break;
            }
            if(buffer.length() >= 4){
                insert(buffer);
            }
        }
    myfile.close();
    traversal(this);
    }
    else { cout << "Unable to open file!" << endl; }
}

void Tree::insert(string str) {
    if(str.empty()){  // Also I'm debating whether I need this or not since the string
                      // cannot possibly be empty as it's part of the condition before                     
                      //insert is even called.
        this->word = str;
        count++;
    }
    else if(this->word == str) count++;
    else if(str < this->word){
        if(this->left == NULL) this->left = new Tree(str);
        else this->left->insert(str);
    }
    else {
        if(this->right == NULL) this->right = new Tree(str);
        else this->right->insert(str);
    }
}

void Tree::traversal(Tree *T) {
    if(T != NULL) {
        traversal(T->left);
        cout << T->word << " (" << count << ")" << endl;
        traversal(T->right);
    }
}

Main

#include <iostream>
#include "tree.h"

using namespace std;

int main()
{
    Tree tree;
    tree.read_file();
    return 0;
}

CapelliC · Accepted Answer · 2013-11-16 07:35:09Z

2

the problem is that you have 2 constructors, and the second one doesn't initialize pointers left/right to NULL.

edit you are showing properties from different objects: use

cout << T->word << " (" << T->count << ")" << endl;

since the recursive procedure doesn't works calling the member function of the received T. You could do it static, or change it

void Tree::traversal() {
    if(this) {
        traversal(left);
        cout << word << " (" << count << ")" << endl;
        traversal(right);
    }
}

Personally, I do prefer this last 'style'.

edited Nov 16, 2013 at 7:35

answered Nov 16, 2013 at 7:03

CapelliC

60.1k5 gold badges50 silver badges94 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

micheal wal Over a year ago

Thank you that was it. Also do you know why my count isn't working? The program prints the words now, but my count prints 0 for the word frequency.

yanchong · Accepted Answer · 2013-11-16 07:07:05Z

0

Tree::Tree()
{ 
    word.clear();
    left = NULL;
    right = NULL;
    count = 0;
}

Tree::Tree(string s)
{
    word = s;
    left = NULL;
    right = NULL;
    count = 0;
}

answered Nov 16, 2013 at 7:07

yanchong

3761 silver badge9 bronze badges

Collectives™ on Stack Overflow

Binary Tree insert function not working correctly C++

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related