0
因此，對於我的數據結構和算法類，我們已經重建了java.util包。我知道在這裏發佈了一個類似的問題：BinarySearchTree remove method malfunctioning when removing integers，但遺憾的是，這個問題還不夠具體。這裏是驅動&輸出：TreeSet類中的迭代器移除方法問題
import set.*;
import list.*;
public class HwTreeSetDriver
{
public static void main()
{
Set <Integer> values;
values = new TreeSet <Integer>();
if (!values.isEmpty())
System.err.println ("Error in isEmpty ");
values.add (3);
values.add (5);
values.add (3);
// No news is good news
if (values.size() != 2)
System.err.println ("Error in size ");
if (values.isEmpty())
System.err.println ("Error in isEmpty ");
for (int j=0; j<5; j++)
values.add (j * 10);
if (values.contains (15))
System.err.println ("Error in contains ");
if (!values.contains (20))
System.err.println ("Error in contains ");
if (values.remove (2))
System.err.println ("Error in remove ");
if (!values.remove (0))
System.err.println ("Error in remove ");
if (values.size() != 6)
System.err.println ("Error in size or remove ");
Iterator<Integer> itty = values.iterator();
while (itty.hasNext())
if (itty.next() % 2 == 1)
itty.remove(); // remove odd numbers
System.out.println ("After removing odd values, set is " + values);
System.out.println ("size is " + values.size());
if (values.size() != 4)
System.err.println ("Error in size or iterator ");
values.clear();
if (!values.isEmpty())
System.err.println ("Error in clear or isEmpty ");
values.add (17);
System.out.println ("Testing complete");
}
}
司機提供以下的輸出：
After removing odd values, set is [3, 5, 10, 20, 30, 40]
size is 6
Testing complete
Error in size or iterator
的問題是，當值樹進行檢查，值都還在那裏，但是當你看在TreeIterator裏面的值樹（見下面）裏面的樹是正確的。它似乎永遠不會更新原始樹（值）。我一直在試圖找出爲什麼它沒有，但我似乎無法找出問題。使用java.util。*的驅動函數來證明它會給出正確的輸出。
這裏是TreeSet類：
package set;
import tree.*;
import list.*;
public class TreeSet<E extends Comparable <E>> implements Set<E>{
BinaryTree<E> tree = new EmptyBinarySearchTree<E>();
int size = 0;
public int size(){
return size;
}
public boolean add(E value){
if(tree.containsKey(value))
return false;
tree = tree.add(value);
size++;
return true;
}
public boolean contains(Object obj){
E value;
try{
value = (E) obj;
return tree.containsKey(value);
}
catch(ClassCastException cce){
return false;
}
}
public void clear(){
tree = new EmptyBinarySearchTree();
size = 0;
}
public boolean remove(Object obj){
if(!(contains(obj)))
return false;
tree = tree.remove(obj);
size--;
return true;
}
public Iterator<E> iterator(){
return tree.iterator();
}
public boolean isEmpty(){
return size == 0;
}
public String toString(){
return tree.toString();
}
}
這裏是BinarySearchTree它使用：
package tree;
import list.*;
public class BinarySearchTree<E extends Comparable<E>> implements BinaryTree<E>{
BinaryTree<E> left;
BinaryTree<E> right;
E value;
public BinarySearchTree(E value){
this.value=value;
left=new EmptyBinarySearchTree<E>();
right=new EmptyBinarySearchTree<E>();
}
public BinaryTree<E> getLeft(){
return left;
}
public BinaryTree<E> getRight(){
return right;
}
public BinaryTree<E> add(E value){
int cmp = value.compareTo(this.value);
if(cmp<0)
left = left.add(value);
if(cmp>0)
right = right.add(value);
return this;
}
public boolean containsKey(E value){
int cmp = value.compareTo(this.value);
if(cmp==0)
return true;
if(cmp<0)
return left.containsKey(value);
return right.containsKey(value);
}
public E getValue(){
return this.value;
}
public E get(E value){
int cmp = value.compareTo(this.value);
if(cmp<0)
return left.get(value);
if(cmp>0)
return right.get(value);
return this.value;
}
private BinaryTree<E> smallest(){
if(left instanceof BinarySearchTree){
return ((BinarySearchTree<E>)left).smallest();
}
return this;
}
public BinaryTree<E> remove(Object obj){
try{E value = (E) obj;
int cmp = value.compareTo(this.value);
if(cmp==0){
List<BinaryTree<E>>kids = children();
if(kids.size()==0)
return new EmptyBinarySearchTree<E>();
if(kids.size()==1)
return kids.get(0);
//2 Children
BinaryTree<E> successor = ((BinarySearchTree)right).smallest();
BinaryTree<E> result = remove(successor.getValue());
result.setValue(successor.getValue());
return result;
}
if(cmp<0)
left = left.remove(value);
if(cmp>0)
right = right.remove(value);
}
catch(ClassCastException ece){}
return this;
}
private List<BinaryTree<E>> children(){
List<BinaryTree<E>>result = new ArrayList<>();
if(left instanceof BinarySearchTree){
result.add(left);
}
if(right instanceof BinarySearchTree){
result.add(right);
}
return result;
}
public void setValue(E value){
this.value=value;
}
public Iterator<E> iterator(){
return new TreeIterator<E>(this);
}
public String toString(){
String result = "[";
Iterator<E> itty = iterator();
while(itty.hasNext()){
result+=itty.next();
if(itty.hasNext()){
result+=", ";
}
}
result+="]";
return result;
}
public void setRight(BinaryTree<E>right){
right=right;
}
public void setLeft(BinaryTree<E>left){
left=left;
}
public boolean isEmpty(){
return value == null;
}
public E getLargest(){
if(right instanceof BinarySearchTree){
return ((BinarySearchTree<E>)right).getLargest();
}
return this.value;
}
}
最後這裏是它採用了TreeIterator：
package tree;
import list.*;
import queue.*;
public class TreeIterator<E> implements Iterator<E>{
private BinaryTree<E>tree;
private QueueADT<E>queue = new ArrayQueue<>();
private E lastGotten;
/**
* Constructor for objects of class TreeIterator
*/
public TreeIterator(BinaryTree<E> tree){
this.tree=tree;
this.buildQ(tree);
}
private void buildQ(BinaryTree<E> tree){
if(tree.getLeft() instanceof BinarySearchTree)
buildQ(tree.getLeft());
queue.add(tree.getValue());
if(tree.getRight() instanceof BinarySearchTree)
buildQ(tree.getRight());
}
public boolean hasNext(){
return !queue.isEmpty();
}
public E next(){
lastGotten=queue.remove();
return lastGotten;
}
public void remove(){
tree=tree.remove(lastGotten);
}
}
這些都是供參考的，因爲沒有使用java.util。