C++ binary tree word frequency counter

[dylan9]

Hey guys, this is my first time posting. I'm almost done with the whole program but the only problem left is the word frequency counter. I have file(.txt) that the program reads on and it outputs the words aphabetically and if the word has been seen, it adds a count to it. I just couldn't figure out the codes for it using binary tree.

By the way, I've done the program using variable string and not char. I also looked in some forums but most of solution codes are in char. I need a code in string as much as possible but if not, anything will do as long as it solves my problem.

The output should be similar to this:

a (3)
at (7)
bit (1)

Here's the complete code. I just need additional code for word frequency.

#include<iostream>
#include<string>
#include<fstream>
#include<algorithm>
#include<iomanip> 

using namespace std;

string readLine(istream& fin)
{
	char buff[256];

	if(fin.peek()=='\n')
	{
		fin.ignore();
	}
	fin.getline(buff, 256, '\n');
	return string(buff);
}

struct Stats 
{
	int unique;
	int distinct;
	int total;
	int multiple;
};

struct Display
{
	string words;
	int frequency;
};

struct Percentage
{
	double distinct;
	double uniqueWords;
	double uniqueDistincts;
};

struct Node
{
	Display value;
	Node* pLeft;
	Node* pRight;
};

Node* addNode(Node* tree, Node* toAdd);
Node* add(Node* tree, Display value);
Node* addNodeFrequency(Node* tree, Node* toAdd);
Node* addFrequency(Node* tree, Display value);

Node* find(Node* tree, string name);
int countNodes(Node *root);
bool duplicate(Node *same, string word);
void display(Node* tree);

void main()
{	
	Display value;
	Stats stats;
	Percentage percentage;
	
	Node* tree = 0;
	Node* tree2 = 0;
	
	stats.total = 0;
	stats.multiple = 0;
	stats.unique = 0;			
	
value.frequency = 0;

	string extract;
	int proceed = 0;
	bool eofReached = false; 
	Node* result;
	cout<<"Enter filename: ";
	cin>>extract;
	
	string fName = extract;
	ifstream inFile(fName.c_str());
	
	if(!inFile)
	{
		cout << "Error, can't open file" << endl;
		exit(0);
	}
	else
	{		
		while(!inFile.eof()) 
		{
			inFile >> value.words;	
			eofReached = inFile.eof();
			stats.total += 1;
			
			
			if(!eofReached)
			{
				proceed++;	
			}	

			if (duplicate(tree, value.words) == false)
			{
				tree = add(tree, value);
			
				if (value.frequency == 1)
				{
					stats.unique += 1;
				}
				else
				{
					stats.multiple += 1;
				}
			}					
			stats.distinct = countNodes(tree);
		}
		inFile.close();
	}
	
	percentage.distinct = (double(stats.distinct) / double(stats.total)) * 100;
	percentage.uniqueWords = (double(stats.unique) / double(stats.total)) * 100;
	percentage.uniqueDistincts = (double(stats.unique) / double(stats.distinct)) * 100;

	string choiceStr;
	char choice;
	
	do
	{
		cout << endl;
		cout << "--------------------------------" << endl;
		cout << "|  a - Display alphabetic list |" << endl;
		cout << "|  f - Display frequency list  |" << endl;
		cout << "|  s - Display statistics      |" << endl;
		cout << "|  x - Exit program            |" << endl;
		cout << "--------------------------------" << endl;
		cout << "Enter choice: " ;
		cin >> choiceStr;
		cout << endl;
		if(choiceStr.length() == 0)
		{
			choice = 'e';
		}
		else
		{
			choice = choiceStr[0];
		}

		switch(choice)
		{
		case 'a':
		case 'A':
			display(tree);
			cout<<"---------------------"<<endl;
			cout<<"Total words   : "<<stats.total<<endl;
			break;
		case 'f':
		case 'F':
			display(tree2);
			cout<<"---------------------"<<endl;
			cout<<"Total words   : "<<stats.total<<endl;
			break;
		case 's':
		case 'S':
			cout<<"Total words   : "<<stats.total<<endl;
			cout<<"Distinct words: "<<stats.distinct<<endl;
			cout<<"Unique words  : "<<stats.unique<<endl;
			cout<<"Multiple words: "<<stats.multiple<<endl;
			cout<<"-------------------------------------------"<<endl;
			cout<<setprecision(2)<<fixed<<"Distinct words as % of words       : "<<percentage.distinct<<"%"<<endl;
			cout<<setprecision(2)<<fixed<<"Unique words as % of total words   : "<<percentage.uniqueWords<<"%"<<endl;
			cout<<setprecision(2)<<fixed<<"Unique words as % of distinct words: "<<percentage.uniqueDistincts<<"%"<<endl;
			cout<<"-------------------------------------------"<<endl;
			break;
		case 'x':
		case 'X':
			break;
		default:
			cout << "Error, invalid choice" << endl;
			break;
		}
	}
	while(choice != 'x');	
}

Node* addNode(Node* tree, Node* toAdd)
{
	if (tree == 0)
	{
		return toAdd;
	}
	else
	{
		if(toAdd->value.words < tree->value.words)
		{
			tree->pLeft = addNode(tree->pLeft, toAdd);
			return tree;
		}
		else
		{
			tree->pRight = addNode(tree->pRight, toAdd);
			return tree;
		}
	}
}

Node* addNodeFrequency(Node* tree, Node* toAdd)
{
	if (tree == 0)
	{
		return toAdd;
	}
	else
	{
		if(toAdd->value.frequency < tree->value.frequency)
		{
			tree->pLeft = addNodeFrequency(tree->pLeft, toAdd);
			return tree;
		}
		else
		{
			tree->pRight = addNodeFrequency(tree->pRight, toAdd);
			return tree;
		}
	}
}

Node* add(Node* tree, Display value)
{
	Node* tempPtr = new Node;
	tempPtr->value  = value;
	tempPtr->pLeft  = 0;
	tempPtr->pRight = 0;
	return addNode(tree, tempPtr);
}

int countNodes(Node *root) 
{
    if (root == NULL)
	{
       return 0;
	}
    else 
	{
       int count = 1;
       count += countNodes(root->pLeft);  
       count += countNodes(root->pRight);
       return count;
    }
} 

bool duplicate(Node *same, string word) 
{
     while (true) 
	 {
        if (same == NULL) 
		{
           return false;
        }
        else if (word == same->value.words) 
		{
           return true;
        }
        else if (word < same->value.words) 
		{
           same = same->pLeft;
        }
        else 
		{
           same = same->pRight;
        }
     }
}

void display(Node* tree)
{	
    if(tree != 0)
	{		
		display(tree->pLeft);		
		cout<<tree->value.words<<" "<<"'"<<tree->value.frequency<<"'"<<endl;
		display(tree->pRight);	
	}
}

Thanks in advance...

[abhimanipal]

I have file(.txt) that the program reads on and it outputs the words aphabetically and if the word has been seen, it adds a count to it

This is being done with which data structure ?
If you want to use the binary tree for counting the frequency of the words, you can use inorder to check if the word exists in the tree. If it does, increment the count by 1. If it does not, create a new node

[thelamb]

Well that's all nice and dandy, but no one is going to read through your source if you just ignore the rules this board has (How did you even miss the fact that you should use code tags?).

"I need a code in string as much as possible but if not, anything will do as long as it solves my problem."

People will help you if you ask a concrete problem, where are you stuck, what have you tried yourself. If you expect source code you're in the wrong place: ask concrete questions, try out what people tell you, if it works, celebrate your new knowledge, else try again until you got it.

[dylan9]

Sorry for not being able to follow some rules. I already tried the char codes but it ruined the whole code that I have, its like changing it to a new set of codes. I've been trying to fix this for 1month now and just trying my luck here so I posted it.

To abhimanipal - thank you for the idea. I'll try to work on the inorder..

[abhimanipal]

@thelamb, dylan9

the reason why the program blows up when you use char codes is that in the addNode function, he is comparing string by using relational operator. This is possible only only in the string class, but if we substitute the string by char array the comparison part will get shot to hell

@thelamb
dylan has posted a lot of code. For the part he/she was stuck he/she is not asking the code but just the general idea. I dont this this is the case of a typical leech who comes here with the sole purpose of getting his work done by others