I copied exactly the BinarySearchTree class from the java textbook data structures third ed. by william collins. I went to try and implement the tree in an address book class, but when I add elements and try to iterate through them, the embedded iterator class in the BinarySearchTree class and some methods it uses only shows three: the root and its two children for some reason. It also may be a problem with the add method but I know that at least the code in each loop in the add method for adding entries always executes because the size of the tree is incremented each time I add any entry, only like I said, when I try and iterate through the tree, no matter how many elements I tried to add (which is correctly represented when the size method is called) only the root and it's two children are printed out. I made sure multiple times all the methods I have been using in the program are exactly the same as the ones the textbook has in the binarysearchtree class it gives us. I have been reviewing them for hours trying to see what is wrong, but everything I have seems to me like it should work, I don't know why it is not. Can some one please help me?
Thank you!
Here is the Binary Search Tree Class
package cs302project1;
import java.util.AbstractSet;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class BinarySearchTree<E> extends AbstractSet<E> {
protected Entry<E> root;
protected int size;
public BinarySearchTree(){
root=null;
size=0;
}
public BinarySearchTree(BinarySearchTree<? extends E> otherTree){
root=copy(otherTree.root,null);
}
//recursive copy method
protected Entry<E> copy(Entry<? extends E> p,Entry<E> parent){
if(p!=null)
{
Entry<E> q=new Entry<E>(p.element,parent);
q.left=copy(p.left,q);
q.right=copy(p.right,q);
return q;
}
return null;
}
//size method
public int size(){
return size;
}
//iterator method
public Iterator<E> iterator() {
return new TreeIterator();
}
public boolean add(E element) {
if(root==null){
root=new Entry(element,null);
size++;
return true;
} else {
Entry<E> temp=root;
int comp;
while(true){
comp=((Comparable)element).compareTo(temp.element);
if(comp==0)
return false;
if(comp<0){
if(temp.left!=null)
temp=temp.left;
else{
temp.left=new Entry<E> (element,temp);
size++;
return true;
}
} else if (temp.right!=null)
temp=temp.right;
//here theres another else im not sure what it does
//oh now I see make temp.right a new entry
else
temp.right=new Entry<E> (element,temp);
size++;
return true;
}
}
}
public boolean contains(Object obj) {
/*
Entry<E> temp = root;
int comp;
if(obj==null)
throw new NullPointerException();
while (temp != null){
comp = ((Comparable)obj).compareTo(temp.element);
if (comp == 0)
return true;
if(comp<0)
temp=temp.left;
else
temp=temp.right;
}
return false;
*/
//the above is the original contains but it is the exact same method
//as the get entry, so I can rewrite it now in one line
return getEntry(obj)!=null;
}
protected Entry<E> successor(Entry<E> e){
if(e==null)
return null;
else if (e.right!=null){
//in this case successor(next element in an inorder traversal) is the
//left most node in the right subtree of e
Entry<E> p = e.right;
while(p.left!=null)
p=p.left;
return p;
}
//if there is no right child than go up tree to left as far as can go
//then go to parent
else{
Entry<E> p=e.parent;
Entry<E> ch=e;
while(p!=null&&ch==p.right){
ch=p;
p=p.parent;
}
return p;
}
}
//method delete entry
//deletes a certain Entry
protected Entry<E> deleteEntry (Entry<E> p){
size--;
//if p has two elements than replace ps element with successors element than make p a reference
//to that successor
//is needed for remove method also used in iterator class
if(p.left!=null&&p.right!=null){
Entry<E> s=successor(p);
p.element=s.element;
p=s;
}
//here p has no children or one child
Entry<E> replacement;
if(p.left!=null)
replacement=p.left;
else
replacement=p.right;
// so if there was a child than link replacement to parent
if(replacement!=null)
{
replacement.parent=p.parent;
if(p.parent==null)
root=replacement;
else if(p==p.parent.left)
p.parent.left=replacement;
else
p.parent.right=replacement;
}
//if theres no children and the only element is the root, just set root to null
else if(p.parent==null)
root=null;
//otherwise just set the left or right in parent in the entry to null
else
{
if(p==p.parent.left)
p.parent.left=null;
else
p.parent.right=null;
}
return p;
}
//get entry is needed for remove method
public Entry<E> getEntry(Object obj) {
Entry<E> e = root;
int comp;
if(obj==null)
throw new NullPointerException();
while (e != null){
comp = ((Comparable)obj).compareTo(e.element);
if (comp == 0)
return e;
else if(comp<0)
e=e.left;
else
e=e.right;
}
return null;
}
//the remove method
//needs to use the getEntry and delete entry methods
public boolean remove(Object obj){
Entry<E> e=getEntry(obj);
if(e==null)
return false;
deleteEntry(e);
return true;
}
protected static class Entry<E> {
protected E element;
protected Entry<E> left = null,
right = null,
parent;
// Initializes this Entry object from element
// and parent.
public Entry(E element, Entry<E> parent) {
this.element = element;
this.parent = parent;
} // constructor
} // class Entry
//embedded tree iterator
protected class TreeIterator implements Iterator<E>{
protected Entry<E> lastReturned=null;
protected Entry<E> next;
protected TreeIterator(){
next=root;
if(next!=null){
while(next.left!=null)
next=next.left;
}
}
@Override
public boolean hasNext() {
// TODO Auto-generated method stub
return next!=null;
}
@Override
public E next() {
if (next==null)
throw new NoSuchElementException();
lastReturned=next;
next=successor(next);
return lastReturned.element;
}
//method remove
//removes the element returned from the most recent call to the next method
public void remove(){
if (lastReturned==null)
throw new IllegalArgumentException();
if(lastReturned.left!=null&&lastReturned.right!=null)
next=lastReturned;
//delete entry last returned
}
}
}
Here is the address book class
package cs302project1;
import java.io.*;
import java.util.ArrayList;
import java.util.Scanner;
import cs302project1.BinarySearchTree.TreeIterator;
public class AddressBook {
//fields
//data structure for people
BinarySearchTree addressBook=new BinarySearchTree();
ArrayList<Person> list=new ArrayList<Person>();
//methods
//enter
public void enter(String name,String address,String phoneNumber){
Person person=new Person(name,address,phoneNumber);
addressBook.add(name);
list.add(person);
}
//delete
public void delete(String name){
if(addressBook.contains(name)){
addressBook.remove(name);
}
for(Person person:list){
if(person.getName().equals(name)){
list.remove(person);
}
}
}
//modify
public void mod(String oldName,String newName,String newAddress,String newPhoneNumber){
addressBook.remove(oldName);
for(Person person:list){
if(person.getName().equals(oldName)){
list.remove(person);
}
}
Person change=new Person(newName,newAddress,newPhoneNumber);
addressBook.add(newName);
list.add(change);
}
//search
public String search(String name){
TreeIterator itr=(TreeIterator) addressBook.iterator();
/*
while(itr.hasNext()){
String current=(String) itr.next();
System.out.println(current);
}
System.out.println(addressBook.size());
//*/
/*
for(Person person:list)
System.out.println(person.toString());
*/
if(addressBook.contains(name)){
for(Person person:list){
if(person.getName().equals(name)){
return person.toString();
}
}
}
return null;
}
//write to file
public void write() throws IOException{
TreeIterator itr=(TreeIterator) addressBook.iterator();
PrintWriter out = new PrintWriter(new FileWriter("Address Book.txt"));
out.println("tst");
out.println(addressBook.size);
while(itr.hasNext()){
String current=(String) itr.next();
/*
for(Person p:list){
if(p.getName().equals(current)){
out.println(p.toString()+"n");
}
}
*/
out.println(current);
}
out.close();
}
}
for example, if I add h, f, i and u than try iterate over them and call the size method. The size is four but the only elements that are printed are f, h and i
another example: I add h, f, e and than try to iterate, only f and then h are printed although the size returned is three. It is the same for any entry that extends past the right child of the root: it is not shown.
There are also two other classes in my program I use, I don't think them relevant to my question but I'll include them anyway
package cs302project1;
import java.io.IOException;
import java.util.Scanner;
public class AddressBookDriver {
//scanner
Scanner scan=new Scanner(System.in);
//help section
private static final String cmdList="MAKE SURE YOU SPELL THE COMMANDS THE SAME WAY I DOn"
+ "type enter to add a new entryntype del to delete an entryntype mod to modify"
+ " an entryntype search to search for an entryntype write to write the address book to a file";
//addressBook
private AddressBook addressBook = new AddressBook();
public static void main(String[] args){
AddressBookDriver driver=new AddressBookDriver();
driver.run();
}
public void run(){
userInterface();
}
//with scanner get commands from user and execute proper methods
//to add to or edit the binary search tree
//add the information to it with the scanner too
public void userInterface(){
String cmd="";
while(cmd!="quit"){
System.out.println("Enter a command (help for command list)");
cmd=scan.nextLine();
if(cmd.equals("help"))
System.out.println("n"+cmdList);
else if(cmd.equals("enter")){
String name,address,phone;
System.out.println("nenter a name");
name=scan.nextLine();
System.out.println("nenter an address");
address=scan.nextLine();
System.out.println("nenter a phone number");
phone=scan.nextLine();
addressBook.enter(name,address,phone);
} else if(cmd.equals("del")){
System.out.println("Type the name of the person you wish to delete");
String name=scan.nextLine();
addressBook.delete(name);
} else if(cmd.equals("search")){
System.out.println("type the name of the person you wish to search");
String name=scan.nextLine();
System.out.println(addressBook.search(name));
} else if(cmd.equals("mod")){
System.out.println("enter the name of a person whose information you wish to modify");
String oldName,newName,newAddress,newPhoneNumber;
oldName=scan.nextLine();
System.out.println("enter a new a new name");
newName=scan.nextLine();
System.out.println("enter a new address");
newAddress=scan.nextLine();
System.out.println("enter a new phone number");
newPhoneNumber=scan.nextLine();
addressBook.mod(oldName, newName, newAddress, newPhoneNumber);
} else if(cmd.equals("search")){
System.out.println("type the name of person to search for");
String name=scan.nextLine();
addressBook.search(name);
if(name==null)
System.out.println("nThat name is not in the address book");
} else if(cmd.equals("write")){
try {
addressBook.write();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
}
}
package cs302project1;
public class Person {
//fields
//name
public String name;
//address
public String address;
//phone number
public String phoneNumber;
//methods
public Person(String name,String address,String phoneNumber){
this.name=name;
this.address=address;
this.phoneNumber=phoneNumber;
}
//getname
public String getName(){
return name;
}
//tostring
public String toString(){
return "name: "+name+"naddress: "+address+"nphone number: "+phoneNumber;
}
}
Aucun commentaire:
Enregistrer un commentaire