In C++ In this individual assignment, you will create a binary search tree for a
ID: 3732513 • Letter: I
Question
In C++
In this individual assignment, you will create a binary search tree for a word-based dictionary. The suggested use is that of learning a new language. The data dass will consist of a word and its translation or meaning. An alternative implementation for this assignment would consist of words in a glossary and their meaning. Your binary search tree will be a collection class similar to the list classes we worked with earlier. The tree class will have a root data attribute that will also be a node pointer, thus making the tree a collection of nodes with their data and node pointers. Use the word as the sorting key for your binary search tree. When the program starts, it should read an initial group of at least 16 data abjects and add those objects to a binary search tree. The words should be placed in the tree according to the alphabetical order but should not be added to the tree in alphabetical order to keep the tree reasonably balanced After the data has been loaded from the text file, a menu should appear that prompts the user to (1) add a word and its meaning, (2) edit a word, (3) find and display a word, (4) view all words in a list, (5) show flashcards, (6) delete a word, or 7) quit the program. When the program quits, all the words in the current program, indluding thase just added, are saved to the text file so that they will be available for the next time the program runs When the user chooses the fleshcard option, a new menu should appear prompting the user to choose between the following traversals: (1) in-order traversal, [2) pre-order traversal, (3) post-order traversal, or (4] random traversal. With the choice of traversal made, the words and their meanings should be displayed one by one incrementaly, with the word coming first, and then the user pressing a key for the meaning to appear. With the meaning the user should also be prompted to either (1) view next word or (2) quit traversalExplanation / Answer
#include<iostream>
#include<string>
#include<cstdlib>
struct Bstnode{
char word[150],meaning[500];
struct BSTnodestnode *left, *right;
}b;
struct BSTnode *root = NULL;
struct BSTnode * createNode(char *word, char *meaning) {
struct BSTnode *newnode;
newnode = (b *)malloc(sizeof(b));
strcpy(newnode->word, word);
strcpy(newnode->meaning, meaning);
newnode->left = newnode->right = NULL;
return newnode;
}
void insert(char *word, char *meaning) {
struct BSTnode *parent = NULL, *current = NULL, *newnode = NULL;
int res = 0;
if (!root) {
root = createNode(word, meaning);
return;
}
for (current = root; current !=NULL;
current = (res > 0) ? current->right : current->left) {
res = strcasecmp(word, current->word);
if (res == 0) {
cout<<"Duplicate entry!! ";
return;
}
parent = current;
}
newnode = createNode(word, meaning);
res > 0 ? (parent->right = newnode) : (parent->left = newnode);
return;
}
void deleteNode(char *str) {
struct BSTnode *parent = NULL, *current = NULL, *temp = NULL;
int flag = 0, res = 0;
if (!root) {
cout<<"BST is not present!!";
return;
}
current = root;
while (1) {
res = strcasecmp(current->word, str);
if (res == 0)
break;
flag = res;
parent = current;
current = (res > 0) ? current->left : current->right;
if (current == NULL)
return;
}
/* deleting leaf node */
if (current->right == NULL) {
if (current == root && current->left == NULL) {
free(current);
root = NULL;
return;
} else if (current == root) {
root = current->left;
free (current);
return;
}
flag > 0 ? (parent->left = current->left) :
(parent->right = current->left);
} else {
/* delete node with single child */
temp = current->right;
if (!temp->left) {
temp->left = current->left;
if (current == root) {
root = temp;
free(current);
return;
}
flag > 0 ? (parent->left = temp) :
(parent->right = temp);
} else {
/* delete node with two children */
struct BSTnode *successor = NULL;
while (1) {
successor = temp->left;
if (!successor->left)
break;
temp = successor;
}
temp->left = successor->right;
successor->left = current->left;
successor->right = current->right;
if (current == root) {
root = successor;
free(current);
return;
}
(flag > 0) ? (parent->left = successor) :
(parent->right = successor);
}
}
free (current);
return;
}
void findElement(char *str) {
struct BSTnode *temp = NULL;
int flag = 0, res = 0;
if (root == NULL) {
cout<<"Not available"<<endl;
return;
}
temp = root;
while (temp) {
if ((res = strcasecmp(temp->word, str)) == 0) {
cout<<"Word :" <<str
cout<<"Meaning:"<<temp->meaning
flag = 1;
break;
}
temp = (res > 0) ? temp->left : temp->right;
}
if (!flag)
cout<<"Search Element not found in Binary Search Tree ";
return;
}
void modify(char *str,char *meaning)
{
struct BSTnode *temp = NULL;
int flag = 0, res = 0;
if (root == NULL) {
cout<<"Not available"<<endl;
return;
}
temp = root;
while (temp) {
if ((res = strcasecmp(temp->word, str)) == 0) {
strcpy(temp->meaning,meaning);
flag = 1;
break;
}
temp = (res > 0) ? temp->left : temp->right;
}
if (!flag)
cout<<"Plese enter the existing word."
return;
}
void inorderTraversal(struct BSTnode *myNode) {
int ch;
if (myNode) {
inorderTraversal(myNode->left);
cout<<"Word :" <<str
cout<<"Meaning:"<<temp->meaning
cout<<endl
cin>>ch
if(ch==q){
return;}
else{
inorderTraversal(myNode->right);}
}
return;
}
void preorderTraversal(struct BSTnode *myNode) {
int ch;
if (myNode) {
cout<<"Word :" <<str
cout<<"Meaning:"<<temp->meaning
cout<<endl
cin>>ch
if(ch==q)
return;
else
preorderTraversal(myNode->left);
preorderTraversal(myNode->right);
}
return;
}
void postorderTraversal(struct BSTnode *myNode) {
int ch;
if (myNode) {
postorderTraversal(myNode->left);
postorderTraversal(myNode->right);
cout<<Word:<<myNode->word;
cout<<Meaning<<myNode->meaning;
cout<<endl
cin>>ch
if(ch==q)
return;
else
}
return;
}
int main()
{
int ch;
char str[128], meaning[256];
while (1) {
cout<<1. Add word<<endl<<2. Edit word<<endl<<3. Delete word<<endl
cout<<4.View all<<endl 5.Find word<<endl 6. Flashing<<endl
cout<<6. Exit<<endl<<Enter ur choice:
cin>>ch
getchar();
switch (ch) {
case 1:
cout<<"Word to insert:";
fgets(str, 100, stdin);
cout<<"Meaning:";
fgets(meaning, 256, stdin);
insert(str, meaning);
break;
case 2:cout<<"Enter to modify word:";
fgets(str,100,stdin);
cout<<"Meaning:";
fgets(meaning, 256, stdin);
modify(str,meaning);
case 3:
cout<<"Enter the word to delete:";
fgets(str, 100, stdin);
deleteNode(str);
break;
case 5:
cout<<"Enter the search word:";
fgets(str, 100, stdin);
findElement(str);
break;
case 6: Traversal();
break;
case 7:
exit(0);
default:
printf("You have entered wrong option ");
break;
}
}
return 0;
}
void Traversal()
{
int ch;
cout<<1.in-order Traversal<<endl<<2.Pre-order Traversal<<endl
cout<<3.Post-order Traversal<<endl<<4.random-order Traversal<<endl
cin>>ch;
if (ch==3)
{
ch=rand()%2+1;
}
switch(ch)
{
case 1: inorderTraversal(root);
break;
case 2: preorderTraversal(root);
break;
case 3: postorderTraversal(root);
break;
default: cout<<"choose the above";
break;
}
}