I am looking for a java program that implements a dictionary, using a binary sea
ID: 3579462 • Letter: I
Question
I am looking for a java program that implements a dictionary, using a binary search tree, to store English words as the keys. Such a dictionary could be used, for example, to translate English words to the equivalent French words. For this assignment, the data stored in the tree is irrelevant and can be ignored. The words should be stored in such a way as to minimize the number of comparisons needed to find a word in the tree based on the known frequency of occurrences of English words. That is, you want to store the words in the BST so that words that occur more commonly, such as 'the', will be closer to the root of the tree, and hence require fewer comparisons to find, and words that are less commonly used, say 'fatal', will be toward the bottom of the BST. In fact, you want to minimize the expected number of comparisons needed to find an English word in the tree ( freq(word) * #comparisons(word)). A list of the number of occurrences of the words in a large corpus of English text is given and can be used to compute the frequencies (freq(word) = #occurrences(word)/total occurrences of all words
Explanation / Answer
OR
IN C LANGUAGE
=======================================================================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct BSTnode {
char word[128], meaning[256];
struct BSTnode *left, *right;
};
struct BSTnode *root = NULL;
struct BSTnode * createNode(char *word, char *meaning) {
struct BSTnode *newnode;
newnode = (struct BSTnode *)malloc(sizeof(struct BSTnode));
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) {
printf("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) {
printf("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) {
printf("Binary Search Tree is out of station!! ");
return;
}
temp = root;
while (temp) {
if ((res = strcasecmp(temp->word, str)) == 0) {
printf("Word : %s", str);
printf("Meaning: %s", temp->meaning);
flag = 1;
break;
}
temp = (res > 0) ? temp->left : temp->right;
}
if (!flag)
printf("Search Element not found in Binary Search Tree ");
return;
}
void inorderTraversal(struct BSTnode *myNode) {
if (myNode) {
inorderTraversal(myNode->left);
printf("Word : %s", myNode->word);
printf("Meaning : %s", myNode->meaning);
printf(" ");
inorderTraversal(myNode->right);
}
return;
}
int main() {
int ch;
char str[128], meaning[256];
while (1) {
printf(" 1. Insertion 2. Deletion ");
printf("3. Searching 4. Traversal ");
printf("5. Exit Enter ur choice:");
scanf("%d", &ch);
getchar();
switch (ch) {
case 1:
printf("Word to insert:");
fgets(str, 100, stdin);
printf("Meaning:");
fgets(meaning, 256, stdin);
insert(str, meaning);
break;
case 2:
printf("Enter the word to delete:");
fgets(str, 100, stdin);
deleteNode(str);
break;
case 3:
printf("Enter the search word:");
fgets(str, 100, stdin);
findElement(str);
break;
case 4:
inorderTraversal(root);
break;
case 5:
exit(0);
default:
printf("You have entered wrong option ");
break;
}
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.