Hi I'm fairly new to programming and have a project I was hoping to get some help with. I'm supposed to read some names and phone numbers from a text file and then use them to populate a binary search tree. Each line in the text file (there are 5 lines total) has one person's name (first and last) along with their phone number. I'm then supposed to use a search key to look for the name of each person. Here are the instructions:
Write a program that provides a way for you to store and retrieve telephone numbers. Design a console program that provides the following operations:
Add: Adds a person’s name and phone number to the phone book.
Delete: Deletes a given person’s name and phone number from the phone book, given only the name.
Find: Locates a person’s phone number, given only the person’s name.
Change: Changes a person’s phone number, given the person’s name and new phone number.
Quit: Quits the application, after first saving the phone book in a text file.
You can proceed as follows:
Design and implement the class Person, which represents the name and phone number of a person. You will store instances of this class in the phone book. Design and implement the class PhoneBook, which represents the phone book. The class should contain a binary search tree as a data field. This tree contains the people in the book. Add methods that use a text file to save and restore the tree. Design and implement the class Menu, which provides the program’s user interface.
The program should read data from a text file when it begins and save data into the text file when the user quits the program.
Where I'm having trouble is populating the BST. When I try to populate the tree I get this error message "incompatible types: String cannot be converted to KeyedItem" How do I change the KeyedItem class so that it will work? Also, if I can overcome the KeyedItem issues, will the code I've written in the Menu class be sufficient to populate the BST? I know there's a lot of info here; I thank you in advance for any help you can give me.
Here are my classes:
Menu class:
public static void main(String[]args) throws IOException{
String read = "";
PhoneBook btree = new PhoneBook(); //creates bst object from phonebook class
BufferedReader input = new BufferedReader(new FileReader("names.txt"));
for (int i=0; i<5; i++){
read = input.readLine(); //reads each lin of text file and stores it in var read
}
btree.insert(read); //this is where I get the ERROR message
}
}
KeyedItem search class:
public abstract class KeyedItem<KT extends Comparable<? super KT>> {
private KT searchKey;
public KeyedItem(KT key){ //constructor
searchKey = key;
}
Phonebook class:
public class PhoneBook<T extends KeyedItem<KT>, KT extends Comparable<? super KT>> extends BinaryTreeBasis<T> {
public PhoneBook(){
}
public PhoneBook(T rootItem){
super(rootItem);
}
public void setRootItem(T newItem) //I believe this class is not always used
throws UnsupportedOperationException {
throw new UnsupportedOperationException();
}
public void insert(T newItem){
root = insertItem(root, newItem);
}
public T retrieve(KT searchKey){
return retrieveItem(root, searchKey);
}
public void delete(KT searchKey) throws TreeException{
root = deleteItem(root, searchKey);
}
public void delete(T item) throws TreeException{
root = deleteItem(root, item.getKey());
}
protected TreeNode<T> insertItem(TreeNode<T> tNode, T newItem){
TreeNode<T> newSubtree;
if(tNode == null){
tNode = new TreeNode<T>(newItem, null, null);
return tNode;
}
T nodeItem = tNode.item;
if(newItem.getKey().compareTo(nodeItem.getKey()) < 0) {
newSubtree = insertItem(tNode.leftChild, newItem);
tNode.leftChild = newSubtree;
return tNode;
}
else {
newSubtree = insertItem(tNode.rightChild, newItem);
tNode.rightChild = newSubtree;
return tNode;
}
}
protected T retrieveItem (TreeNode<T> tNode, KT searchKey) {
T treeItem;
if(tNode == null){
treeItem = null;
}
else {
T nodeItem = tNode.item;
if (searchKey.compareTo(nodeItem.getKey()) == 0) {
treeItem = tNode.item;
}
else if (searchKey.compareTo(nodeItem.getKey()) < 0){
treeItem = retrieveItem(tNode.leftChild, searchKey);
}
else {
treeItem = retrieveItem(tNode.rightChild, searchKey);
}
}
return treeItem;
}
protected TreeNode<T> deleteItem(TreeNode<T> tNode, KT searchKey) {
TreeNode<T> newSubtree;
if (tNode == null){
throw new TreeException("TreeException: Item not found");
}
else{
T nodeItem = tNode.item;
if (searchKey.compareTo(nodeItem.getKey()) == 0){
tNode = deleteNode(tNode);
}
else if (searchKey.compareTo(nodeItem.getKey()) < 0){
newSubtree = deleteItem(tNode.leftChild, searchKey);
tNode.leftChild = newSubtree;
}
else {
newSubtree = deleteItem(tNode.rightChild, searchKey);
tNode.rightChild = newSubtree;
}
}
return tNode;
}
protected TreeNode<T> deleteNode(TreeNode<T> tNode){
T replacementItem;
if((tNode.leftChild == null) &&
(tNode.rightChild == null)){
return null;
}
else if (tNode.leftChild == null){
return tNode.rightChild;
}
else if (tNode.rightChild == null){
return tNode.leftChild;
}
else {
replacementItem = findLeftmost(tNode.rightChild);
tNode.item = replacementItem;
tNode.rightChild = deleteLeftmost(tNode.rightChild);
return tNode;
}
}
protected T findLeftmost(TreeNode<T> tNode){
if (tNode.leftChild == null) {
return tNode.item;
}
else {
return findLeftmost(tNode.leftChild);
}
}
protected TreeNode<T> deleteLeftmost(TreeNode<T> tNode){
if (tNode.leftChild == null){
return tNode.rightChild;
}
else{
tNode.leftChild = deleteLeftmost(tNode.leftChild);
return tNode;
}
}
}
public KT getKey(){
return searchKey;
}
}
Person class:
public class Person extends KeyedItem<String>{
private FullName name;
private String phoneNumber;
public Person(String id, FullName name, String phone){ //constructor
super(id);
this.name = name;
phoneNumber = phone;
}
public String toString(){
return getKey() + " # " + name;
}
}
TreeNode class:
public class TreeNode<T> {
T item;
TreeNode<T> leftChild;
TreeNode<T> rightChild;
public TreeNode(T newItem){ //constructor
item = newItem;
leftChild = null;
rightChild = null;
}
public TreeNode(T newItem, TreeNode<T> left, TreeNode<T> right){
item = newItem;
leftChild = left;
rightChild = right;
}
}
BinaryTreeBasis class:
public abstract class BinaryTreeBasis<T> {
protected TreeNode<T> root;
public BinaryTreeBasis(){ //default constructor
root = null;
}
public BinaryTreeBasis(T rootItem){
root = new TreeNode<T>(rootItem, null, null);
}
public boolean isEmpty(){
return root == null;
}
public void makeEmpty(){
root = null;
}
public T getRootItem() throws TreeException {
if (root == null){
throw new TreeException("Tree Exception: Empty Tree");
}
else{
return root.item;
}
}
public abstract void setRootItem(T newItem);
}
Fullname class:
public class FullName implements java.lang.Comparable<Object>{ //change from object?
private String firstName;
private String lastName;
public FullName(String first, String last){
firstName = first;
lastName = last;
}
public int compareTo(Object rhs){
FullName other = (FullName)rhs;
if(lastName.compareTo(((FullName)other).lastName)==0){
return firstName.compareTo(((FullName)other).firstName);
}
else {
return lastName.compareTo(((FullName)other).lastName);
}
}
}
Tree Iterator class:
public class TreeIterator<T> implements java.util.Iterator<T> {
private BinaryTreeBasis<T> binTree;
private TreeNode<T> currentNode;
private LinkedList <TreeNode<T>> queue;
public TreeIterator(BinaryTreeBasis<T> bTree){
binTree = bTree;
currentNode = null;
queue = new LinkedList <TreeNode<T>>();
}
public boolean hasNext(){
return !queue.isEmpty();
}
public T next()
throws java.util.NoSuchElementException{
currentNode = queue.remove();
return currentNode.item;
}
public void remove()
throws UnsupportedOperationException{
throw new UnsupportedOperationException();
}
public void setPreorder(){
queue.clear();
preorder(binTree.root);
}
public void setInorder(){
queue.clear();
inorder(binTree.root);
}
public void setPostorder(){
queue.clear();
postorder(binTree.root);
}
private void preorder(TreeNode<T> treeNode){
if(treeNode != null){
queue.add(treeNode);
preorder(treeNode.leftChild);
preorder(treeNode.rightChild);
}
}
private void inorder(TreeNode<T> treeNode){
if(treeNode != null){
inorder(treeNode.leftChild);
queue.add(treeNode);
inorder(treeNode.rightChild);
}
}
private void postorder(TreeNode<T> treeNode){
if(treeNode != null){
postorder(treeNode.leftChild);
postorder(treeNode.rightChild);
queue.add(treeNode);
}
}
}