Homework SourseThis lab involves either AVL trees or RedBlack trees Overvie
This lab involves either AVL trees or Red-Black trees.
Overview: The game involves asking a player how many letters they want, then generating a list of that many random letters. The user must then generate as many random words as s/he can using only those letters. When the user is done, the user should enter a dummy value (I used “-1”). The list of words entered is then checked with the dictionary. For every word entered that is in the dictionary, the user gets 3 points. For every word entered that is not in the dictionary, the user loses 6 points. That’s basically it.
A couple of notes:
When generating the list of x random letters, the game is pretty dull if no vowels are included. So I generated a random number y between 1 and x, and then got that many random vowels. I then got x-y consonants.
letters can be repeated.
The AVL tree should be designed so that no duplicates are allowed in the tree.
To test to see whether you’ve loaded the file and created the AVL tree properly, you should write an in-order printTree method as part of your AVL class and call it. If the words print out in order alphabetically, your AVL tree is most likely being created correctly.
The dictionary I used was a scrabble dictionary, which means that most if not all of the words are 8 characters or less. You may not want to pick a number much bigger than 8, or, as an alternative, you may want to find your own dictionary.
You can use .size() to get the number of characters in a string. You must include <string>.
The text file I am giving you is called dict.txt, and has over 80000 words in it. Every time I ran the program, it took my computer about a minute to load the entire dictionary into the AVL tree (and my computer is relatively fast – feel free to one-up me with your faster computer!). Thus for testing purposes, I created a much smaller dictionary file so I didn’t have to wait that whole minute while I was debugging. I’ve included that as well. Equally, for testing my tree, I created a much smaller file. I’ve included it, along with the pre-order, in-order, and post-order printout. I included my output so you can test your tree from the test file.
Outline:
I am including a general outline, which you may or may not choose to use for this lab:
Files created include:
BSTB.hpp // the Binary Search Tree class declarations
BSTB.cpp // the Binary Search Tree class method definitions (using AVL balanced tree methods)
/* note: you can start writing this as a regular binary search tree, then modify it to be an AVL tree later */
NodeTB.hpp // the NodeTree class declaration
NodeTB.cpp // the NodeTree class method definitions (this is for the tree)
Game.hpp // the class declarations for the Boggle-ish game
Game.cpp // the class definitions for the Boggle-ish game
Main.cpp // the main file, which creates a game object and then runs the game’s startGame method
More Details:
My BSTB.hpp:
(not including include files)
class BSTB {
NodeTB *root;
int score; //for wordlist when calculating score, initialized to 0
public:
BSTB(); // constructor – sets root to NULL
~BSTB(); // destructor – deletes tree
bool insert(string x);
/* recursively inserts x into the tree with the current root (possibly of a
subtree) being n */
bool insert(string x, NodeTB *n);
/* Note the overloading of methods – this is nice if you choose to write this method recursively. If a string is already in the tree, you may want to print out a warning, but otherwise it can just be ignored. */
/* Note: you can choose to not write this recursively, but it’s just so nice recursively */
void printTreeio();
/* prints out the data in the tree in order (this should print out the
dictionary alphabetically ) */
void printTreeio(NodeTB *n); /* again, nice if you choose recursion
void printTreePre(); /* for testing purposes, prints out tree in preorder
void printTreePre(NodeTB *n); /* for printing recursively
void printTreePost(); /* for testing purposes, prints out tree in postorder
void printTreePost(NodeTB *n); /* for printing recursively
bool search(string x);
/* searches tree for x – returns true if found, false otherwise */
bool search(NodeTB *n, string x); /*if recursive */
void adjustBalances(NodeTB *n); /* adjusts heights of trees */
NodeTB *rotateRight(NodeTB *n); /* for right rotation*/
NodeTB * rotateLeft(NodeTB *n); /* for left rotation */
};
My Game.hpp:
(not including include files)
class Game {
BSTB *dict; // the AVL tree
int numletters; // the number of letters the user wants
char *currletters; //the random set of letters
int numright; // the count of the number of words in the AVL tree
int totalwords; // the count of the total number of words generated
BSTB wordlist; // The Binary Search tree for the word list – used because you //want to make sure there are no duplicates in the word list typed in
public:
/*constructor, initializes AVL tree from “dict.txt” by calling ReadTreeFromFile
*/
Game();
/* constructor, initializes AVL tree by calling ReadTreeFromFile with infile
*/
Game(string infile);
/* startGame(): this is the user interface part – it asks how many letters the user wants, reads that number in, prints out the set of random letters (including at least one vowel, and then tells the user to start typing in words. Each word typed in is added to the wordlist (the linked list). When the user enters -1,(see note at bottom about a timer) the function then calculates the user’s total score by calling a function that first checks to make sure that each word only includes letters in the set of random letters and then checks to see if each word in the list is in the AVL tree. It then prints out the list of valid words and the user’s score. This function loops until the user no longer wants to play again.
*/
void startGame();
void readTreeFromFile (string dictfile); /* see below for this method*/
/* getLetters(): this method (called by the startGame method) gets a set of x random letters
and returns it.
*/
char * getLetters(int x);
/* getWords():this method (called by the startGame method) loops while the user enters potential words. Each word gets added to the wordlist tree.
*/
void getWords();
/* checkWLetters(): checks to see if s only contains letters in currletters (the random set of letters) and returns true if s only contains valid letters, false otherwise
*/
bool checkWLetters(string s);
/* checkWordsForScore(): Goes through the list of words, checks to see if each word contains only letters in the random list (by calling checkWLetters), then checks to see if the valid words are in the avl tree and, if it is, increase the user’s score, and if it isn’t decreases the user’s score.
*/
void checkWordsForScore();
};
The readTreeFromFile method involves file input/output (file io). In this function I create an infile, and then read in from it until I hit the end of file (eof). I included:
#include <fstream>
Here is my code for this function:
void Game::readTreeFromFile (string dictfile) {
dict = new BSTB();
ifstream file(dictfile.c_str()); // converts a string to a character array
string word;
while (!file.eof()) { // checks for end of file
file >> word;
if (!file.eof()) {
dict->insert(word);
}
}
return;
}
That’s it. When you’re done, zip up the 8 files (including dict.txt) and submit it.
Here are some of examples of the outputs you should get...
PreOrder printout of test file:
lose dunce believe babe appease deject grange fabric frisbee juice hand shawn rest might master older running super sort wanton tint
InOrder printout:
appease babe believe deject dunce fabric frisbee grange hand juice lose master might older rest running shawn sort super tint wanton
PostOrder printout:
appease babe deject believe frisbee fabric hand juice grange dunce master older might running rest sort tint wanton super shawn lose
Solution
main.cpp
#include <iostream>
#include <string>
#include \"Game.hpp\"
#include \"AVLTY.hpp\"
using namespace std;
int main(){
Game *game = new Game(\"dictionary.txt\");
game->startGame();
}
AVLTY.cpp
#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <string>
#include \"NodeL.hpp\"
#include \"AVLTY.hpp\"
using namespace std;
AVLTY::AVLTY(){
root = NULL;
}
AVLTY::~AVLTY(){
}
NodeTY *AVLTY::AVLTYinsert(string word,NodeTY *n){
if (n == NULL)
{
n = new NodeTY(word);
n->data = word;
n->ptrL = NULL;
n->ptrR = NULL;
return n;
}
else if (word < n->data)
{
n->ptrL = AVLTYinsert(word,n->ptrL);
n = AVLTYbalance (n);
}
else if (word >= n->data)
{
n->ptrR = AVLTYinsert(word,n->ptrR);
n = AVLTYbalance (n);
}
return n;
}
int AVLTY::getHeight(NodeTY *n){
int h=0;
if (n!=NULL){
int leftHeight= getHeight(n->ptrL);
int rightHeight=getHeight(n->ptrR);
int maxHeight = max(leftHeight,rightHeight);
h=maxHeight+1;
}
return h;
}
int AVLTY::getDifference(NodeTY *n){
int leftHeight = getHeight(n->ptrL);
int rightHeight = getHeight(n->ptrR);
int balanceFactor = leftHeight-rightHeight;
return balanceFactor;
}
NodeTY *AVLTY::rRotation(NodeTY *n){
NodeTY *temp;
temp = n->ptrR;
n->ptrR=temp->ptrL;
temp->ptrL=n;
return temp;
}// called for right rotations
NodeTY *AVLTY::lRotation(NodeTY *n){
NodeTY *temp;
temp= n->ptrL;
n->ptrL=temp->ptrR;
temp->ptrR=n;
return temp;
}// called for rotating right
NodeTY *AVLTY::lrRotation(NodeTY *n){
NodeTY *temp;
temp = n->ptrL;
n->ptrL = rRotation(temp);
return lRotation(n);
}// called for rotating left then right
NodeTY *AVLTY::rlRotation(NodeTY *n){
NodeTY *temp;
temp = n->ptrR;
n->ptrR = lRotation(temp);
return rRotation(n);
}//for doing right left rotations
NodeTY *AVLTY::AVLTYbalance(NodeTY *n){
int balanceFactor = getDifference (n);
if (balanceFactor > 1)
{
if (getDifference (n->ptrL) > 0)
n = lRotation (n);
else
n = lrRotation (n);
}
else if (balanceFactor < -1)
{
if (getDifference (n->ptrR) > 0)
n = rlRotation (n);//if
else
n = rRotation (n);
}//elif/elif
return n;
}
void AVLTY::printTreeio(NodeTY *n){
if (n==NULL)
return;
printTreeio (n->ptrL);
cout<<n->data<<\" \";
printTreeio (n->ptrR);
}//prints out the binary AVLtree
bool AVLTY::search(string x){
NodeTY *temp = root;
while(temp !=NULL){
if(x == temp->data){
return true;
}//if
else if(x < temp->data){
temp = temp->ptrL;
}//elif
else if(x > temp->data){
temp = temp->ptrR;
}//elif
}//while
return false;
}//returns true or false if string is in tree
AVLTY.hpp
#include <iostream>
#include <string>
#include \"NodeTY.hpp\"
using namespace std;
#ifndef AVLTY_HPP_
#define AVLTY_HPP_
class AVLTY{
public:
NodeTY *root;
AVLTY();
~AVLTY();
NodeTY *AVLTYinsert(string word,NodeTY *root);
NodeTY *AVLTYbalance(NodeTY *n); //finds the height difference between the trees branches and then uses that difference to determine
//the kind of rotation necessary in order to balance the tree
int getHeight(NodeTY *n);
int getDifference(NodeTY *n);
NodeTY *rRotation(NodeTY *n);
NodeTY *lRotation(NodeTY *n);
NodeTY *rlRotation(NodeTY *n);
NodeTY *lrRotation(NodeTY *n);
bool search(string x, NodeTY *n);
bool search(string x);
NodeTY *rotateleft(NodeTY *n);
NodeTY *rotateright(NodeTY *n);
NodeTY *rotatelr(NodeTY *n);
NodeTY *rotaterl(NodeTY *n);
void printTreeio(NodeTY *n);
};
#endif /* AVLTY_HPP_ */
Game.cpp
#include <iostream>
#include <string>
#include <stdlib.h>
#include <time.h>
#include \"Game.hpp\"
#include \"AVLTY.hpp\"
using namespace std;
Game::Game(){
dict = NULL;
readTreeFromFile(\"dictionary.txt\");
numberletters = 0;
currletters = NULL;
totalwords = 0;
numright = 0;
}
Game::Game(string infile){
dict = NULL;
readTreeFromFile(infile);
numberletters = 0;
currletters = NULL;
totalwords = 0;
numright = 0;
}//Sets things up for funcitons to fill in the feilds
char * Game::getLetters(int x){
srand(time(NULL));
x = numberletters;
int vowels = 1+rand()%x/2;
char Letters[x];
char c[21] = {\'b\',\'c\',\'d\',\'f\',\'g\',\'h\',\'j\',\'k\',\'l\',\'m\',\'n\',\'p\',\'q\',\'r\',\'s\',\'t\',\'v\',\'w\',\'x\',\'y\',\'z\'};
char y[5] = {\'a\',\'e\',\'i\',\'o\',\'u\'};//char letter arrays
for(int i=0;i<vowels;i++){
int e = rand()%5;
Letters[x] += y[e];
}//for
for(int i=0;i<x-vowels;i++){
int q = rand()%21;
Letters[x] +=c[q];
}//for
currletters = Letters;
return Letters;// this may need some adjusting
}
void Game::getWords(){
cout << \"Enter possible words when done enter value(-1): \";
string response2;
cin >> response2;
while(response2 !=\"-1\"){
wordlist.push(response2);//adds user words to LL
totalwords++;
}//while
return;
}
void Game::startGame(){
int response;
cout << \"How many letters do you want: \";
cin >> response;
numberletters = response;
getLetters(response);
cout << \"\"<< endl;
cout << currletters << endl;
getWords();
checkWordsForScore();
}//runs through the motions of the running the game
bool Game::checkWLetters(string s){
for(unsigned int i=0; i < s.size() ;i++){
char LetterOfString = s[i];
for(int j=0; numberletters < j;j++){
char * randomLetters = currletters;
unsigned int numberofMatches = 0;
if(randomLetters[j]== LetterOfString ){
numberofMatches++; //checks each letter of the string with the random letters a
// and if the length of the word = the number of corret letters the word is ok
if (numberofMatches == s.size()){
return true;
}//if
else{
return false;
}//else
}//if
}//for
}//for
return true;
}//checkWLetters(Sorry this is so gross looking)
void Game::readTreeFromFile(string dictfile) {
dict = new AVLTY();
NodeTY *temp = dict->root;
ifstream file(dictfile.c_str()); // converts a string to a character array
string word;
while (!file.eof()) { // checks for end of file
file >> word;
if (!file.eof()) {
dict->AVLTYinsert(word,temp);
}//if
}
return;
}//reads in the dictionary to create the tree
void Game::checkWordsForScore(){
int Score = 0;
NodeL *temp = wordlist.first;
while(temp != NULL){
if(checkWLetters(temp->data)){
if (dict->search(temp->data)){
Score+=3;
}
else Score-=6;//scores things
temp = temp->next;
}//while
}
}
Game.hpp
#include <iostream>
#include <fstream>
#include \"AVLTY.hpp\"
#include \"LL.hpp\"
using namespace std;
#ifndef GAME_HPP_
#define GAME_HPP_
class Game{
AVLTY *dict;// the AVL tree
int numberletters;// the number of letters the user wants
char *currletters; //the random set of letters
int numright; // the count of the number of words in the AVL tree
int totalwords; // the count of the total number of words generated
LL wordlist; // the linked list of words the user typed in.
public:
/*constructor, initializes AVL tree from dict.txt by calling ReadTreeFromFile
*/
Game();
/* constructor, initializes AVL tree by calling ReadTreeFromFile with infile
*/
Game(string infile);
/* this is the user interface part it asks how many letters the user wants,
reads that number in, prints out the set of random letters (including at least
one vowel, and then tells the user to start typing in words. Each word typed
in is added to the wordlist (the linked list). When the user enters -1, the
function then calculates the users total score by calling a function that
first checks to make sure that each word only includes letters in the set of
random letters and then checks to see if each word in the list is in the AVL
tree. It then prints out the list of valid words and the users score. This
function loops until the user no longer wants to play again.
*/
void startGame();
void readTreeFromFile (string dictfile); /* see below for this method*/
/* this method (called by the startGame method) gets a set of x random letters
and returns it.
*/
char * getLetters(int x);
/* this method (called by the startGame method) loops while the user enters
potential words. Each word gets added to the linked list wordlist.
*/
void getWords();
/* checks to see of s only contains letters in currletters (the random set of
letters) and returns true if s only contains valid letters, false otherwise
*/
bool checkWLetters(string s);
/* Goes through the list of words, checks to see if each word contains only
letters in the random list (by calling checkWLetters), then checks to see if
the valid words are in the avl tree and, if it is, increase the users score,
and if it isnt decreases the users score.
*/
void checkWordsForScore();
};
#endif /* GAME_HPP_ */
LL.cpp
#include <iostream>
#include <string>
#include \"NodeL.hpp\"
#include \"LL.hpp\"
using namespace std;
LL::LL(){
first = NULL;
last = NULL;
currentSize = 0;
}
void LL::push(string word){
NodeL *temp;
if(first == NULL){
first = new NodeL(word);
temp = first;
}//if
else{
temp = first;
while (temp->next != NULL) {
temp = temp->next;
}//while
temp->next = new NodeL(word);
temp = temp->next;
}
currentSize++;
last = temp;
return;
}
LL::~LL(){
if(currentSize > 0){
NodeL *temp = first;
while(temp->next != NULL){
first = temp->next;
temp->next = NULL;
delete temp;
temp = first;
}
delete temp;
first = NULL;
last = NULL;
currentSize = 0;
}
}
LL.hpp
#include <string>
#include \"NodeL.hpp\"
using namespace std;
#ifndef LL_HPP_
#define LL_HPP_
class LL{
friend class Game;
NodeL *first;
NodeL *last;
int currentSize;
public:
LL();
~LL();
void push(string word);
};
#endif /* LL_HPP_ */
NodeL.cpp
#include \"NodeL.hpp\"
#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;
NodeL::NodeL(string word){
data = word;
ptr = NULL;
next = NULL;
}
NodeL::~NodeL(){
if(ptr != NULL){
cout << \"deleting this may cuase memory leaking\" << endl;
}//if
}
NodeL.hpp
#include <iostream>
#include <string>
using namespace std;
#ifndef NODEL_HPP_
#define NODEL_HPP_
class NodeL{
friend class Game;
friend class LL;
string data;
NodeL *ptr;
NodeL *next;
public:
NodeL(string data);
~NodeL();
};
#endif /* NODEL_HPP_ */
NodeTY.cpp
#include \"NodeTY.hpp\"
#include <iostream>
#include <string>
#include <stdlib.h>
#include <fstream>
using namespace std;
NodeTY::NodeTY(string Dictword){
data = Dictword;
ptrL = NULL;
ptrR = NULL;
root = NULL;
}//creates Tree nodes
NodeTY.hpp
/*
* NodeTY.hpp
*
* Created on: Mar 30, 2015
* Author: Curtis
*/
#include <string>
using namespace std;
#ifndef NODETY_HPP_
#define NODETY_HPP_
class NodeTY{
friend class AVLTY;
string data;
NodeTY *root;
NodeTY *ptrL;
NodeTY *ptrR;
public:
NodeTY(string data);
~NodeTY();
};
#endif /* NODETY_HPP_ */
dictionary.txt
babe
redrills
losel
wanton
shawn
dunches
fabliau
dejecta
chars
mastered
lose
belaud
grange
jayvees
superjet
sorter
unhand
freebase
ruddiest
