We want to write a C++ program that ask the user to inputs as many words as he/s

Question

We want to write a C++ program that ask the user to inputs as many words as he/she wishes. Every time a word is input by the user, this word is inserted in a Binary Search Tree (BST) based on its alphabetical order. Once the tree is created, we want to do the followings:

• Display the content of the tree in pre-order.

• Ask the user to input a new word and check if this words exists already in the Tree.

• Ask the user to input a character and display all the words in the tree that end with this character.

Explanation / Answer

C++ Code:

/*
* C++ Program To Implement BST
*/
# include <iostream>
# include <cstdlib>
# include <string.h>

using namespace std;
/*
* Node Declaration
*/
struct node
{
char word[100];
struct node *left;
struct node *right;
}*root;

/*
* Class Declaration
*/
class BST
{
public:
void find(char*);
void insert(node *tree, node *newnode);
void preorder(node *);
void find_all(node *, char c);
void display(node *, int);
BST()
{
root = NULL;
}
};

/*
* Main Contains Menu
*/
int main()
{
int choice, num;
BST bst;
char word[100], c;
node *temp;
while (1)
{
cout<<"-----------------"<<endl;
cout<<"Operations on BST"<<endl;
cout<<"-----------------"<<endl;
cout<<"1.Insert Element "<<endl;
cout<<"2.Preorder Traversal"<<endl;
cout<<"3.Find a word"<<endl;
cout<<"4.Find a word with matching trailing character"<<endl;
cout<<"5.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
temp = new node;
cout<<"Enter the word to be inserted : ";
cin>>temp->word;
bst.insert(root, temp);
break;

case 2:
cout<<"Preorder Traversal of BST:"<<endl;
bst.preorder(root);
cout<<endl;
break;

case 3 :
cout << "Enter the word to be found : "<<endl;
cin >> word;
bst.find(word);
break;

case 4 :
cout << "Enter the character : "<<endl;
cin >> c;
bst.find_all(root,c);
break;

case 5:
exit(1);
break;

default:
cout<<"Wrong choice"<<endl;
exit(1);
}
}
}

/*
* Find Element in the Tree
*/
void BST::find(char* item)
{
node * ptr ;

if (root == NULL)
{
cout << "Word not found" << endl;
return;
}
if (strcmp(item,root->word) == 0)
{
cout << "Word found" <<endl;
return;
}
if (strcmp(item, root->word) < 0)
ptr = root->left;
else
ptr = root->right;

while (ptr != NULL)
{
if (strcmp(item, ptr->word) == 0)
{
cout << "Word found" <<endl;
return;
}
if (strcmp(item, ptr->word) < 0)
ptr = ptr->left;
else
ptr = ptr->right;
}
cout << "Word not found" <<endl;
return;
}

/*
*display all the words in the tree that end with this character
*/
void BST::find_all(node * ptr, char c)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
if ((ptr->word)[strlen(ptr->word)- 1] == c)
cout<<ptr->word<<" ";
find_all(ptr->left, c);
find_all(ptr->right, c);
}
}

/*
* Inserting Element into the Tree
*/
void BST::insert(node *tree, node *newnode)
{
if (root == NULL)
{
root = new node;
strcpy(root->word,newnode->word);
root->left = NULL;
root->right = NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (strcmp(tree->word, newnode->word) == 0)
{
cout<<"Element already in the tree"<<endl;
return;
}
if (strcmp(tree->word, newnode->word) > 0)
{
if (tree->left != NULL)
{
insert(tree->left, newnode);
}
else
{
tree->left = newnode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout<<"Node Added To Left"<<endl;
return;
}
}
else
{
if (tree->right != NULL)
{
insert(tree->right, newnode);
}
else
{
tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout<<"Node Added To Right"<<endl;
return;
}
}
}

/*
* Pre Order Traversal
*/
void BST::preorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
cout<<ptr->word<<" ";
preorder(ptr->left);
preorder(ptr->right);
}
}

Output shown after running this program:

$ ./a.out
-----------------
Operations on BST
-----------------
1.Insert Element
2.Preorder Traversal
3.Find a word
4.Find a word with matching trailing character
5.Quit
Enter your choice : 1
Enter the word to be inserted : rohit
Root Node is Added
-----------------
Operations on BST
-----------------
1.Insert Element
2.Preorder Traversal
3.Find a word
4.Find a word with matching trailing character
5.Quit
Enter your choice : 1
Enter the word to be inserted : jindal
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element
2.Preorder Traversal
3.Find a word
4.Find a word with matching trailing character
5.Quit
Enter your choice : 2
Preorder Traversal of BST:
rohit jindal
-----------------
Operations on BST
-----------------
1.Insert Element
2.Preorder Traversal
3.Find a word
4.Find a word with matching trailing character
5.Quit
Enter your choice : 4
Enter the character :
rohit
Tree is empty
Tree is empty
Tree is empty
-----------------
Operations on BST
-----------------
1.Insert Element
2.Preorder Traversal
3.Find a word
4.Find a word with matching trailing character
5.Quit
Enter your choice : Wrong choice
[rojindal@hax-ampandey-1 ~]$ ./a.out
-----------------
Operations on BST
-----------------
1.Insert Element
2.Preorder Traversal
3.Find a word
4.Find a word with matching trailing character
5.Quit
Enter your choice : 1
Enter the word to be inserted : rohit
Root Node is Added
-----------------
Operations on BST
-----------------
1.Insert Element
2.Preorder Traversal
3.Find a word
4.Find a word with matching trailing character
5.Quit
Enter your choice : 1
Enter the word to be inserted : jindal
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element
2.Preorder Traversal
3.Find a word
4.Find a word with matching trailing character
5.Quit
Enter your choice : 2
Preorder Traversal of BST:
rohit jindal
-----------------
Operations on BST
-----------------
1.Insert Element
2.Preorder Traversal
3.Find a word
4.Find a word with matching trailing character
5.Quit
Enter your choice : 3
Enter the word to be found :
rohit
Word found
-----------------
Operations on BST
-----------------
1.Insert Element
2.Preorder Traversal
3.Find a word
4.Find a word with matching trailing character
5.Quit
Enter your choice : 4
Enter the character :
t
Tree is empty
Tree is empty
Tree is empty
-----------------
Operations on BST
-----------------
1.Insert Element
2.Preorder Traversal
3.Find a word
4.Find a word with matching trailing character
5.Quit
Enter your choice : ^]q
Wrong choice
[rojindal@hax-ampandey-1 ~]$ vim main.cpp
[rojindal@hax-ampandey-1 ~]$ g++ main.cpp
[rojindal@hax-ampandey-1 ~]$ ./a.out
-----------------
Operations on BST
-----------------
1.Insert Element
2.Preorder Traversal
3.Find a word
4.Find a word with matching trailing character
5.Quit
Enter your choice : 1
Enter the word to be inserted : rohit
Root Node is Added
-----------------
Operations on BST
-----------------
1.Insert Element
2.Preorder Traversal
3.Find a word
4.Find a word with matching trailing character
5.Quit
Enter your choice : 1
Enter the word to be inserted : jindal
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element
2.Preorder Traversal
3.Find a word
4.Find a word with matching trailing character
5.Quit
Enter your choice : 4
Enter the character :
t
rohit -----------------
Operations on BST
-----------------
1.Insert Element
2.Preorder Traversal
3.Find a word
4.Find a word with matching trailing character
5.Quit
Enter your choice : 3
Enter the word to be found :
rohit
Word found
-----------------
Operations on BST
-----------------
1.Insert Element
2.Preorder Traversal
3.Find a word
4.Find a word with matching trailing character
5.Quit
Enter your choice : 4
Enter the character :
l
jindal -----------------
Operations on BST
-----------------
1.Insert Element
2.Preorder Traversal
3.Find a word
4.Find a word with matching trailing character
5.Quit
Enter your choice : 5

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.