Write a client program that allows the user to pick one of your three spell chec

Question

Write a client program that allows the user to pick one of your three spell checkers (the unbalanced BST, the balanced BST, or the trie). The program should create a spell checker object of that type and then allow the user to enter any number of sentences to check. For each sentence, show the misspelled words and a list of suggested corrections for each one. Also have your program display the time required to read the word list when it creates the spell checker object.

Explanation / Answer

#include using namespace std; struct Node { int data; Node* left, *right; }; /* This function traverse the skewed binary tree and stores its nodes pointers in vector nodes[] */ void storeBSTNodes(Node* root, vector &nodes) { // Base case if (root==NULL) return; // Store nodes in Inorder (which is sorted // order for BST) storeBSTNodes(root->left, nodes); nodes.push_back(root); storeBSTNodes(root->right, nodes); } /* Recursive function to construct binary tree */ Node* buildTreeUtil(vector &nodes, int start, int end) { // base case if (start > end) return NULL; /* Get the middle element and make it root */ int mid = (start + end)/2; Node *root = nodes[mid]; /* Using index in Inorder traversal, construct left and right subtress */ root->left = buildTreeUtil(nodes, start, mid-1); root->right = buildTreeUtil(nodes, mid+1, end); return root; } // This functions converts an unbalanced BST to // a balanced BST Node* buildTree(Node* root) { // Store nodes of given BST in sorted order vector nodes; storeBSTNodes(root, nodes); // Constucts BST from nodes[] int n = nodes.size(); return buildTreeUtil(nodes, 0, n-1); } // Utility function to create a new node Node* newNode(int data) { Node* node = new Node; node->data = data; node->left = node->right = NULL; return (node); } /* Function to do preorder traversal of tree */ void preOrder(Node* node) { if (node == NULL) return; printf("%d ", node->data); preOrder(node->left); preOrder(node->right); } // Driver program int main() { /* Constructed skewed binary tree is 10 / 8 / 7 / 6 / 5 */ Node* root = newNode(10); root->left = newNode(8); root->left->left = newNode(7); root->left->left->left = newNode(6); root->left->left->left->left = newNode(5); root = buildTree(root); printf("Preorder traversal of balanced " "BST is : "); preOrder(root); return 0; }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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