Question

13inary Search Tree Using a binary search tree, you are tasked with building a dictionary program which you can store a word with its definition. Each node of the tree will contain the word and definition. The word is what will be used as the key to sort our data. The dictionary should allow you to search for a word. If the word exist then the definition will display. You can also add words to the dictionary. For testing you should be able to display the current word list. The dictionary will populate from a data file and new words will be saved to the file as well. We are still covering Binary trees in class, but we have covered enough to get you started.

Answer 1

I have provided the code with proper comments and screenshots for proper indentation. If you still have any doubts then please ask in the comments section. I would love to revert back to you.

Code:

------------------------------------------------------------------------------------------------------------------------------------

#include<bits/stdc++.h>
using namespace std;

// Structure for the Nodes of the tree
struct node {
    // String used for storing word and meaning
    string word, meaning;
    // Pointers to left and right tree
    struct node *left, *right;
};
//Root of the Tree
struct node *root = NULL;
// Helper Function to Create a New Node and return it's pointer
struct node * new_node(string word, string meaning) {
    struct node *temp; // Temporary Node
    temp = new node(); // Allocating the space to the pointer
    temp->word = word; // Assigning the word
    temp->meaning = meaning; // Assigning the meaning
    temp->left = temp->right = NULL; // Setting the left and right as NULL
    return temp; // Returning the pointer to the newly created node
}
// Function to insert the new word into the tree
struct node * insert(struct node* Node,string word,string meaning) {
    // Checking if the current Node on which we are is empty or not
    // If empty then insert the word here only
    if(Node == NULL) return new_node(word,meaning);
    // If the word is smaller than the word of the current node
    // Then insert on the left part of the tree
    if(Node->word > word) Node->left = insert(Node->left,word,meaning);
    // else insert on the right part of the tree
    else if (Node->word < word) Node->right = insert(Node->right,word,meaning);
    // Returning the node after inserting the word
    return Node;  
}
// Function to search a word in the tree
void search(string str) {
    // Temporary node to traverse the tree
    struct node *temp = root;
    // Run the loop until Leaves of the tree are encountered
    // Which are BTW NULL
    while (temp) {
        // Checking if the word is equal to the word of current node
        // And hence output the meaning
        if (temp->word == str) {
                cout << "Word : " << str << endl;
                cout << "Meaning: " << temp->meaning;
                return;
        }
        // Else if the word is smaller than the current node's word
        // Go for the left tree
        else if(temp->word > str) temp = temp->left;
        // Else go for the right tree
        else temp = temp->right;
    }
    // If the word is not found print the same
    cout << "Word Not Found";
    return;
}
// Inorder Traveral of the tree
void inorder_traversal(struct node *Node) {
    // If the node is NULL then return
    if(Node == NULL) return;
    // Traverse the left subtree
    inorder_traversal(Node->left);
    // print the word and meaning of the current Node
    cout << "Word : " << Node->word << " Meaning : " << Node->meaning << endl;
    // Traverse the right subtree
    inorder_traversal(Node->right);
}

//Driver Code to Test the above functions.
int main() {
    int ch;
    string str,mean;
    // Code to take input from a file
    // ifstream inFile;
    // inFile.open("data.txt");
    // if (!inFile) {
    //     cout << "Unable to open file";
    //     exit(1);
    // }
  
    // while (inFile >> str) {
    //     inFile >> mean;
    //     root = insert(root,str,mean);
    // }
    // inFile.close();
    while (1) {
            printf("\n1. Insertion\n2. Searching\n3. Traversal\n4. Exit\n");
            printf("Enter ur choice:");
            cin >> ch;
            switch (ch) {
                    case 1:
                            printf("Word to insert:");
                            cin >> str;
                            printf("Meaning:");
                            cin >> mean;
                            root = insert(root,str, mean);
                            break;
                    case 2:
                            printf("Enter the search word:");
                            cin >> str;
                            search(str);
                            break;
                    case 3:
                            inorder_traversal(root);
                            break;
                    case 4:
                            exit(0);
                    default:
                            printf("You have entered wrong option\n");
                            break;
            }
    }
    return 0;
}

------------------------------------------------------------------------------------------------------------------------------------

Screenshots of the code:

1.

1 #include<bits/stdc++.h> using namespace std; // Structure for the Nodes of the tree struct node { // String used for storing word and meaning string word, meaning; // Pointers to left and right tree struct node *left, *right; 12 //Root of the Tree struct node *root = NULL; // Helper Function to Create a New Node and return it's pointer struct node * new_node(string word, string meaning) { struct node *temp; // Temporary Node temp = new node(); // Allocating the space to the pointer temp->word = word; // Assigning the word temp->meaning = meaning; // Assigning the meaning temp->left = temp->right = NULL; // Setting the left and right as NULL return temp; // Returning the pointer to the newly created node // Function to insert the new word into the tree struct node * insert(struct node* Node, string word, string meaning) { // Checking if the current Node on which we are is empty or not // If empty then insert the word here only if(Node == NULL) return new_node (word, meaning); // If the word is smaller than the word of the current node // Then insert on the left part of the tree if(Node->word > word) Node->left = insert(Node->left, word, meaning); // else insert on the right part of the tree else if (Node->word < word) Node->right = insert(Node->right,word, meaning); // Returning the node after inserting the word return Node;

2.

35 // Function to search a word in the tree void search(string str) { // Temporary node to traverse the tree struct node *temp = root; // Run the loop until Leaves of the tree are encountered // which are BTW NULL while (temp) { // Checking if the word is equal to the word of current node // And hence output the meaning if (temp->word == str) { cout << "Word : " << str << endl; cout << "Meaning: " << temp->meaning; return; // Else if the word is smaller than the current node's word // Go for the left tree else if(temp->word > str) temp = temp-left; // Else go for the right tree else temp = temp->right; // If the word is not found print the same cout << "Word Not Found"; return; // Inorder Traveral of the tree void inorder_traversal(struct node *Node) { // If the node is NULL then return if(Node == NULL) return; // Traverse the left subtree inorder_traversal(Node->left); // print the word and meaning of the current Node cout << "Word : " << Node->word « " Meaning : " << Node->meaning << endl; // Traverse the right subtree inorder_traversal(Node->right);

3.

//Driver Code to test the above functions. int main() { int ch; string str,mean; // Code to take input from a file // ifstream inFile; // infile.open("data.txt"); // if (!inFile) { // cout << "Unable to open file"; // exit(1); // while (inFile >> str) { // inFile >> mean; // root = insert(root, str,mean); 87 // infile.close();

4.

while (1) { printf("\ni. Insertion\n2. Searching\n3. Traversal\n4. Exit\n"); printf("Enter ur choice:"); cin >> ch; switch (ch) { case 1: printf("Word to insert:"); cin >> str; printf("Meaning:"); cin >> mean; root = insert(root,str, mean); break; case 2: printf("Enter the search word: "); cin >> str; search(str); break; case 3: inorder_traversal(root); break; case 4: exit(0); default: printf("You have entered wrong option\n"); break; 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 return 0; ]

Sample Run :

Run 1:

1. Insertion 2. Searching 3. Traversal 4. Exit Enter ur choice: 1 Word to insert:apple Meaning: fruiti 1. Insertion 2. Searching 3. Traversal 4. Exit Enter ur choice:2 Enter the search word: banana Word Not Found 1. Insertion 2. Searching 3. Traversal 4. Exit Enter ur choice:3 Word : apple Meaning : fruiti 1. Insertion 2. Searching 3. Traversal 4. Exit Enter ur choice: 4

Run 2:

1. Insertion 2. Searching 3. Traversal 4. Exit Enter ur choice:1 Word to insert: apple Meaning: fruiti 1. Insertion 2. Searching 3. Traversal 4. Exit Enter ur choice:2 Enter the search word: apple Word : apple Meaning: fruiti 1. Insertion 2. Searching 3. Traversal 4. Exit Enter ur choice:4

For any doubts ask in the comments section I would love to revert back to you.

Happy Learning Data Structures !