AVL Tree based dictionary

[codingchick94]

Implement an AVL tree based dictionary. Using your dictionary write a program
that reads a text file specified as a command-line argument and prints out a lexicographically
sorted list of all the words that occur in this file along with the frequency with each
word occurs.

Your dictionary class must be called Dictionary. Your dictionary will be represented
as an AVL tree. Each node in the tree will be an object of class WordNode that
contains: a word, the number of times the word has been accessed, a boolean variable to
support lazy deletion, its height in the tree and links to its left and right children.
The following public methods of Dictionary class must be implemented:
bool isEmpty() const - returns true if empty, false otherwise.
int getSize() - returns how many words are stored in the dictionary.
void insert (String word) - insert word into dictionary if not already present,
else update.
bool find(String word, WordNode & x) - returns true if the word is present and
place data in x.
void printSorted() const - prints the words in the tree in lexicographic order
void remove (String word) - implements the lazy deletion of a node.

In lazy deletion, instead of deleting the desired node and modifying the
structure of the tree, we merely mark the node as deleted. During find operations,
we return false if the desired node is found but marked. This way, the balance of
a tree is never disturbed by deletion operations. However, if too many nodes are
deleted, then operations start to become expensive, since too much of the tree is
devoted to nodes that don’t represent valid data.

This project requires you to learn how to use command line arguments and the
string manipulation package <string>.



HERE IS WHAT I HAVE SO FAR:

----------

#include <iostream>
#include<cctype>
#include <stdlib.h>
#include <conio.h>
#include <string>
using namespace std;

struct node
{
string element;
node *left;
node *right;
int height;
};
typedef struct node *nodeptr;
class bstree
{
public:
void insert(string,nodeptr &);
void del(string, nodeptr &);
bool find(string,nodeptr &);
void isEmpty(nodeptr &);
void copy(nodeptr &,nodeptr &);
nodeptr nodecopy(nodeptr &);
void printSorted(nodeptr);
int bsheight(nodeptr);
nodeptr srl(nodeptr &);
nodeptr drl(nodeptr &);
nodeptr srr(nodeptr &);
nodeptr drr(nodeptr &);
int nonodes(nodeptr);
int deletemin(nodeptr &);
};
// Inserting a node
void bstree::insert(string x,nodeptr &p)
{
if (p == NULL)
{
p = new node;
p->element = x;
p->left=NULL;
p->right = NULL;
p->height=0;
if (p==NULL)
{
cout<<"Out of Space\n"<<endl;
}
}
else
{
if (x<p->element)
{
insert(x,p->left);
if ((bsheight(p->left) - bsheight(p->right))==2)
{
if (x < p->left->element)
{
p=srl(p);
}
else
{
p = drl(p);
}
}
}
else if (x>p->element)
{
insert(x,p->right);
if ((bsheight(p->right) - bsheight(p->left))==2)
{
if (x > p->right->element)
{
p=srr(p);
}
else
{
p = drr(p);
}
}
}
else
{
cout<<"Element Exists\n"<<endl;
}
}
string m,n,d;
m=bsheight(p->left);
n=bsheight(p->right);
d=max(m,n);
p->height = d + 1;
}

// Finding an element
bool bstree::find(string x,nodeptr &p)
{
if (p==NULL)
{
return false;
}
else
{
if (x < p->element)
{
find(x,p->left);
}
else
{
if (x>p->element)
{
find(x,p->right);
}
else
{
return true;
}
}
}
}
// Copy a tree
void bstree::copy(nodeptr &p,nodeptr &p1)
{
isEmpty(p1);
p1 = nodecopy(p);
}
// Make a tree empty
void bstree::isEmpty(nodeptr &p)
{
nodeptr d;
if (p != NULL)
{
isEmpty(p->left);
isEmpty(p->right);
d=p;
free(d);
p=NULL;
}
}
// Copy the nodes
nodeptr bstree::nodecopy(nodeptr &p)
{
nodeptr temp;
if (p==NULL)
{
return p;
}
else
{
temp = new node;
temp->element = p->element;
temp->left = nodecopy(p->left);
temp->right = nodecopy(p->right);
return temp;
}
}

// Deleting a node
void bstree::del(string x,nodeptr &p)
{
nodeptr d;
if (p==NULL)
{
cout<<"Sorry! element not found\n"<<endl;
}
else if ( x < p->element)
{
del(x,p->left);
}
else if (x > p->element)
{
del(x,p->right);
}
else if ((p->left == NULL) && (p->right == NULL))
{
d=p;
free(d);
p=NULL;
cout<<"Element deleted successfully\n"<<endl;
}
else if (p->left == NULL)
{
d=p;
free(d);
p=p->right;
cout<<"Element deleted successfully\n"<<endl;
}
else if (p->right == NULL)
{
d=p;
p=p->left;
free(d);
cout<<"Element deleted successfully\n"<<endl;
}
else
{
p->element = deletemin(p->right);
}
}
int bstree::deletemin(nodeptr &p)
{
int c;
cout<<"inside deltemin\n"<<endl;
if (p->left == NULL)
{
c=p->element;
p=p->right;
return c;
}
else
{
c=deletemin(p->left);
return c;
}
}
// printSorted Printing
void bstree::printSorted(nodeptr p)
{
if (p!=NULL)
{
printSorted(p->left);
cout<<p->element<<"\t";
printSorted(p->right);
}
}

nodeptr bstree:: srl(nodeptr &p1)
{
nodeptr p2;
p2 = p1->left;
p1->left = p2->right;
p2->right = p1;
p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
p2->height = max(bsheight(p2->left),p1->height) + 1;
return p2;
}
nodeptr bstree:: srr(nodeptr &p1)
{
nodeptr p2;
p2 = p1->right;
p1->right = p2->left;
p2->left = p1;
p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
p2->height = max(p1->height,bsheight(p2->right)) + 1;
return p2;
}
nodeptr bstree:: drl(nodeptr &p1)
{
p1->left=srr(p1->left);
return srl(p1);
}
nodeptr bstree::drr(nodeptr &p1)
{
p1->right = srl(p1->right);
return srr(p1);
}

int bstree::nonodes(nodeptr p)
{
int count=0;
if (p!=NULL)
{
nonodes(p->left);
nonodes(p->right);
count++;
}
return count;
}

int main()
{
//clrscr();
nodeptr root,root1,min,max;//,flag;
string a,findele,delele;
int choice;
char ch='y';
bstree bst;

//system("clear");
root = NULL;
root1=NULL;

do
{
cout<<"Enter 1 to insert a new node"<<endl;
cout<<"Enter 2 to search a value"<<endl;
cout<<"Enter 3 to delete a value"<<endl;
cout<<"Enter 4 to display printSorted"<<endl;
cout<<"Enter 5 to display the height of the tree"<<endl;
cout<<"Enter 0 to exit"<<endl;

cout<<"\nEnter the choice: ";
cin>>choice;

switch(choice)
{
case 1:
cout<<"\n\t\tADDING NEW NODE"<<endl;
cout<<"\t\t:::::::::::::\n"<<endl;
cout<<"Enter a new value: ";
cin>>a;
bst.insert(a,root);
cout<<"\nThe new value have been added to your tree successfully\n"<<endl;
break;
case 2:
cout<<"\nEnter node to search: ";
cin>>findele;
if (root != NULL)
{
bst.find(findele,root);
}
break;
case 3:
cout<<"\nEnter node to delete: ";
cin>>delele;
bst.del(delele,root);
bst.printSorted(root);
cout<<endl;
break;
case 4:
cout<<"\n\t\tIN-ORDER TRAVERSAL"<<endl;
bst.printSorted(root);
cout<<endl;
break;
case 5:
cout<<"\n\t\tHEIGHT\n"<<endl;
cout<<"The height of the tree is: " <<bst.bsheight(root)<<endl;

break;
case 0:
cout<<"\n\tThank your for using AVL tree program\n"<<endl;
break;
default:
cout<<"Sorry! wrong input\n"<<endl;
break;
}
system("pause");
}while(choice != 0);
return 0;
}

[Smac89]

Can you wrap your code in code tags? I recognize that this is your first post on the forum, so here is the guide to using code tags:
http://www.cplusplus.com/articles/z13hAqkS/

You seem to have shown us code you wrote(?) But you haven't said what is wrong with it or why you are posting it here. What do you need help with?

I think this might help:
http://www.cplusplus.com/forum/beginner/108093/