Mixing
Search Key for a Binary Search Tree populated by text file (Java)
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(Stringargs) 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);
}
}
}
java binary-search-tree search-keywords
asked Nov 20 '18 at 2:19
MatthewMatthew
132
|
show 1 more comment
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(Stringargs) 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);
}
}
}
java binary-search-tree search-keywords
asked Nov 20 '18 at 2:19
MatthewMatthew
132
You are usingGenericsand as such you need to use aPhoneBookwhich is also usingGenericswith a type ofPersonPhoneBook<Person> btree = new PhoneBook<Person>();
– Scary Wombat
Nov 20 '18 at 2:26
Also within theforloop afterread = input.readLine();you need to construct a Person Object and add that to thebtreewithin the loop
– Scary Wombat
Nov 20 '18 at 2:28
The string "read" in your main method cannot be passed into your bTree because the type that your insert takes is generic T that extends KeyedItem. String doesnt extend KeyedItem. You have to somehow extract the info from that string read and construct a Person with that information. You can insert a Person into the bTree because it extends KeyedItem
– JRowan
Nov 20 '18 at 2:40
I'm curious if you wrote all the KeyedItem/TreeNode generic stuff. No offense intended, but I'm slightly surprised to see such complex concepts implemented reasonably well given the nature of your question. If you didn't write all that, why are you using it? Was it part of the class assignment? I'd personally start with a much simpler implementation of all that.
– Yona Appletree
Nov 20 '18 at 2:44
Second, you probably don't want to hard code the number5in your file reading code, since the idea is for the file to be modified by this application. You should probably read each line until you reach the end of the file.
– Yona Appletree
Nov 20 '18 at 2:45
|
show 1 more comment
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(Stringargs) 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);
}
}
}
java binary-search-tree search-keywords
asked Nov 20 '18 at 2:19
MatthewMatthew
132
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(Stringargs) 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);
}
}
}
java binary-search-tree search-keywords
java binary-search-tree search-keywords
asked Nov 20 '18 at 2:19
MatthewMatthew
132
asked Nov 20 '18 at 2:19
MatthewMatthew
132
asked Nov 20 '18 at 2:19
MatthewMatthew
132
asked Nov 20 '18 at 2:19
MatthewMatthew
132
asked Nov 20 '18 at 2:19
MatthewMatthew
132
132
You are usingGenericsand as such you need to use aPhoneBookwhich is also usingGenericswith a type ofPersonPhoneBook<Person> btree = new PhoneBook<Person>();
– Scary Wombat
Nov 20 '18 at 2:26
Also within theforloop afterread = input.readLine();you need to construct a Person Object and add that to thebtreewithin the loop
– Scary Wombat
Nov 20 '18 at 2:28
The string "read" in your main method cannot be passed into your bTree because the type that your insert takes is generic T that extends KeyedItem. String doesnt extend KeyedItem. You have to somehow extract the info from that string read and construct a Person with that information. You can insert a Person into the bTree because it extends KeyedItem
– JRowan
Nov 20 '18 at 2:40
I'm curious if you wrote all the KeyedItem/TreeNode generic stuff. No offense intended, but I'm slightly surprised to see such complex concepts implemented reasonably well given the nature of your question. If you didn't write all that, why are you using it? Was it part of the class assignment? I'd personally start with a much simpler implementation of all that.
– Yona Appletree
Nov 20 '18 at 2:44
Second, you probably don't want to hard code the number5in your file reading code, since the idea is for the file to be modified by this application. You should probably read each line until you reach the end of the file.
– Yona Appletree
Nov 20 '18 at 2:45
|
show 1 more comment
You are usingGenericsand as such you need to use aPhoneBookwhich is also usingGenericswith a type ofPersonPhoneBook<Person> btree = new PhoneBook<Person>();
– Scary Wombat
Nov 20 '18 at 2:26
Also within theforloop afterread = input.readLine();you need to construct a Person Object and add that to thebtreewithin the loop
– Scary Wombat
Nov 20 '18 at 2:28
The string "read" in your main method cannot be passed into your bTree because the type that your insert takes is generic T that extends KeyedItem. String doesnt extend KeyedItem. You have to somehow extract the info from that string read and construct a Person with that information. You can insert a Person into the bTree because it extends KeyedItem
– JRowan
Nov 20 '18 at 2:40
I'm curious if you wrote all the KeyedItem/TreeNode generic stuff. No offense intended, but I'm slightly surprised to see such complex concepts implemented reasonably well given the nature of your question. If you didn't write all that, why are you using it? Was it part of the class assignment? I'd personally start with a much simpler implementation of all that.
– Yona Appletree
Nov 20 '18 at 2:44
Second, you probably don't want to hard code the number5in your file reading code, since the idea is for the file to be modified by this application. You should probably read each line until you reach the end of the file.
– Yona Appletree
Nov 20 '18 at 2:45
You are using
Generics and as such you need to use a PhoneBook which is also using Generics with a type of Person PhoneBook<Person> btree = new PhoneBook<Person>();– Scary Wombat
Nov 20 '18 at 2:26
You are using
Generics and as such you need to use a PhoneBook which is also using Generics with a type of Person PhoneBook<Person> btree = new PhoneBook<Person>();– Scary Wombat
Nov 20 '18 at 2:26
Also within the
for loop after read = input.readLine(); you need to construct a Person Object and add that to the btree within the loop– Scary Wombat
Nov 20 '18 at 2:28
Also within the
for loop after read = input.readLine(); you need to construct a Person Object and add that to the btree within the loop– Scary Wombat
Nov 20 '18 at 2:28
The string "read" in your main method cannot be passed into your bTree because the type that your insert takes is generic T that extends KeyedItem. String doesnt extend KeyedItem. You have to somehow extract the info from that string read and construct a Person with that information. You can insert a Person into the bTree because it extends KeyedItem
– JRowan
Nov 20 '18 at 2:40
The string "read" in your main method cannot be passed into your bTree because the type that your insert takes is generic T that extends KeyedItem. String doesnt extend KeyedItem. You have to somehow extract the info from that string read and construct a Person with that information. You can insert a Person into the bTree because it extends KeyedItem
– JRowan
Nov 20 '18 at 2:40
I'm curious if you wrote all the KeyedItem/TreeNode generic stuff. No offense intended, but I'm slightly surprised to see such complex concepts implemented reasonably well given the nature of your question. If you didn't write all that, why are you using it? Was it part of the class assignment? I'd personally start with a much simpler implementation of all that.
– Yona Appletree
Nov 20 '18 at 2:44
I'm curious if you wrote all the KeyedItem/TreeNode generic stuff. No offense intended, but I'm slightly surprised to see such complex concepts implemented reasonably well given the nature of your question. If you didn't write all that, why are you using it? Was it part of the class assignment? I'd personally start with a much simpler implementation of all that.
– Yona Appletree
Nov 20 '18 at 2:44
Second, you probably don't want to hard code the number
5 in your file reading code, since the idea is for the file to be modified by this application. You should probably read each line until you reach the end of the file.– Yona Appletree
Nov 20 '18 at 2:45
Second, you probably don't want to hard code the number
5 in your file reading code, since the idea is for the file to be modified by this application. You should probably read each line until you reach the end of the file.– Yona Appletree
Nov 20 '18 at 2:45
|
show 1 more comment
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53385299%2fsearch-key-for-a-binary-search-tree-populated-by-text-file-java%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53385299%2fsearch-key-for-a-binary-search-tree-populated-by-text-file-java%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
You are using
Genericsand as such you need to use aPhoneBookwhich is also usingGenericswith a type ofPersonPhoneBook<Person> btree = new PhoneBook<Person>();– Scary Wombat
Nov 20 '18 at 2:26
Also within the
forloop afterread = input.readLine();you need to construct a Person Object and add that to thebtreewithin the loop– Scary Wombat
Nov 20 '18 at 2:28
The string "read" in your main method cannot be passed into your bTree because the type that your insert takes is generic T that extends KeyedItem. String doesnt extend KeyedItem. You have to somehow extract the info from that string read and construct a Person with that information. You can insert a Person into the bTree because it extends KeyedItem
– JRowan
Nov 20 '18 at 2:40
I'm curious if you wrote all the KeyedItem/TreeNode generic stuff. No offense intended, but I'm slightly surprised to see such complex concepts implemented reasonably well given the nature of your question. If you didn't write all that, why are you using it? Was it part of the class assignment? I'd personally start with a much simpler implementation of all that.
– Yona Appletree
Nov 20 '18 at 2:44
Second, you probably don't want to hard code the number
5in your file reading code, since the idea is for the file to be modified by this application. You should probably read each line until you reach the end of the file.– Yona Appletree
Nov 20 '18 at 2:45