Binary search tree will be a collection class similar to the list classes we wor
ID: 3734568 • Letter: B
Question
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 objects 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 user chooses the flashcard 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 incrementally, 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 traversal
Please write in C++
Explanation / Answer
#include<bits/stdc++.h>
using namespace std;
#define MAXLEN 9
struct node
{
char *str;
struct node* left;
struct node* right;
};
typedef int (*Compare)(const char *, const char *);
int CmpStr(const char *a, const char *b)
{
return (strcmp (a, b));
}
void insert(char* key, struct node** leaf, Compare cmp)
{
int res;
if( *leaf == NULL ) {
*leaf = (struct node*) malloc( sizeof( struct node ) );
(*leaf)->str = (char *)malloc( strlen (key) +1 );
strcpy ((*leaf)->str, key);
(*leaf)->left = NULL;
(*leaf)->right = NULL;
} else {
res = cmp (key, (*leaf)->str);
if( res < 0)
insert( key, &(*leaf)->left, cmp);
else if( res > 0)
insert( key, &(*leaf)->right, cmp);
else
printf ("Word '%s' already in tree ", key);
}
}
void edit(char* key,char *str, struct node** leaf, Compare cmp)
{
int res;
if( leaf != NULL ) {
res = cmp(key, (*leaf)->str);
if( res < 0)
edit( key, str,&(*leaf)->left, cmp);
else if( res > 0)
edit( key, str,&(*leaf)->right, cmp);
else
strcpy ((*leaf)->str, str);
}
else printf(" Not in tree ");
return;
}
void inOrder(struct node *root)
{
if( root != NULL ) {
inOrder(root->left);
printf(" %s ", root->str);
inOrder(root->right);
}
}
void preOrder(struct node *root)
{
if( root != NULL ) {
printf(" %s ", root->str);
preOrder(root->left);
preOrder(root->right);
}
}
void postOrder(struct node *root)
{
if( root != NULL ) {
postOrder(root->left);
postOrder(root->right);
printf(" %s ", root->str);
}
}
void search(char* key, struct node* leaf, Compare cmp)
{
int res;
if( leaf != NULL ) {
res = cmp(key, leaf->str);
if( res < 0)
search( key, leaf->left, cmp);
else if( res > 0)
search( key, leaf->right, cmp);
else
printf(" '%s' found! ", key);
}
else printf(" Not in tree ");
return;
}
void delete_tree(struct node** leaf)
{
if( *leaf != NULL ) {
delete_tree(&(*leaf)->left);
delete_tree(&(*leaf)->right);
free( (*leaf)->str );
free( (*leaf) );
}
}
main()
{
ifstream file;
file.open("file.txt");
string str;
struct node* root=NULL;
while(file>>str) {
char *line = &str[0u];
insert(line, &root, (Compare)CmpStr);
}
file.close();
cout<<"hello";
while(1) {
int option;
cout<< "press 1.Add a word 2.Edit a word 3.Display a word 4.View all words 5.Show FlashCard 6.Delete 7.Quit program"<<endl;
cin>>option;
switch(option) {
case 1: {
cout<<"Enter the word which you want to insert"<<endl;
cin>>str;
char *inp = &str[0u];
insert(inp, &root, (Compare)CmpStr);
break;
}
case 2: {
cout<<"Enter the word which you want to Edit"<<endl;
cin>>str;
char *inp = &str[0u];
cout<<"Enter new word"<<endl;
string newstr;
cin>>newstr;
char *ip = &newstr[0u];
edit(inp,ip, &root, (Compare)CmpStr);
break;
}
case 3: {
cout<<"Enter the word which you want to search"<<endl;
cin>>str;
char *inp = &str[0u];
search(inp, root, (Compare)CmpStr);
break;
}
case 4: {
cout<<"All words in list"<<endl;
inOrder(root);
break;
}
case 5: {
cout<<"FlashCards"<<endl;
cout<<"Press 1.Inorder Traversal 2.Preorder Traversal 3.Postorder Traversal 4.Random Traversal"<<endl;
int opt;
cin>>opt;
switch(opt) {
case 1: {
inOrder(root);
break;
}
case 2: {
preOrder(root);
break;
}
case 3: {
postOrder(root);
break;
}
case 4: {
//random_order(root);
break;
}
default : {
cout<<"You choose wrong option"<<endl;
break;
}
}
break;
}
case 6: {
delete_tree(&root);
break;
}
default : {
exit(1);
}
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.