Set二分探索木を使用してジェネリックを実装するクラスを作成しています。toString()括弧式を表示するようにメソッドを実装していますが、うまく動作しません。たとえば、基本的なバイナリ ツリーは次のとおりです。
toString メソッドでこのバイナリ ツリーを次のように出力したいと思います。
(10 (5 (4 () ()) (6 () ())) (20 (15 () ()) (25 () ())))
where()は空のツリーを意味します。
これが toString メソッドを持つ私のクラスです。どんな助けでも大歓迎です！
// Allow short name access to following classes
import csc143.data_structures.*;
public class MySet<E> implements SimpleSet<E> {
// the root of the "tree" that structures the set
private BTNode root;
// the current number of elements in the set
private int numElems;
public MySet() {
root = null;
numElems = 0;
}
/**
* Add an element to the set.
*
* @param e The element to be added to the set.
* @return <tt>true</tt> If this operation updated the contents of the set.
*/
public boolean add(E e) {
try {
root = addToSubtree(root, (Comparable) e);
return true;
} catch(DuplicateAdded exc) {
// duplicate trying to be added
return false;
}
}
// This helper method adds the element "e" to tree rooted at r. Returns
// (possibly new) tree containing "e", or throws DuplicateAdded exception
// if "e" already exists in tree.
private BTNode addToSubtree(BTNode r, Comparable elem)
throws DuplicateAdded {
if(r == null) {
numElems++;
return new BTNode(elem);
}
int compare = elem.compareTo(r.item);
// element already in tree
if(compare == 0) {
throw new DuplicateAdded();
} else if(compare < 0) {
r.left = addToSubtree(r.left, elem);
} else { // compare > 0
r.right = addToSubtree(r.right, elem);
}
// element has been added
return r;
}
/**
* Remove all elements from this set.
*/
public void clear() {
root = null;
numElems = 0;
}
/**
* Checks for the existance of the specified value within the set.
*
* @param e The value sought.
* @return <tt>true</tt> If the value exists in the set.
*/
public boolean contains(E e) {
return subtreeContains(root, (Comparable) e);
}
// This helper method returns whether element "elem" is in
// (sub-)tree with root "r".
private boolean subtreeContains(BTNode r, Comparable elem) {
if(r == null) {
return false;
} else {
int compare = elem.compareTo(r.item);
// found element
if(compare == 0){
return true;
} else if(compare < 0) {
return subtreeContains(r.left, elem);
} else { // compare > 0
return subtreeContains(r.right, elem);
}
}
}
/**
* Check for the existance of elements in the set.
*
* @return <tt>true</tt> If there are no elements in the set.
*/
public boolean isEmpty() {
return root == null;
}
/**
* Return the number of elements in the set.
*
* @return The number of elements in the set.
*/
public int size() {
return numElems;
}
/**
* Returns a String representation of the contents of the set.
*
* @return The String representation of the set.
*/
public String toString() {
return subtreeToString(root);
}
private String subtreeToString(BTNode r) {
String str = "";
if(r == null) {
str += "() ";
return str;
}
str += "(" + r.item;
str += subtreeToString(r.left) +
subtreeToString(r.right) + ")";
return str;
}
// this inner class creates the node that compose the binary tree structure
class BTNode<E> {
/**
* The item stored in the node.
*/
public E item;
/**
* The node to the left of "this" node.
*/
public BTNode left;
/**
* The node to the right of "this" node.
*/
public BTNode right;
/**
* Constructs the BTNode object (three parameters).
*
* @param item The item to be stored in the node.
* @param left The node to the left of "this" node.
* @param right The node to the right of "this" node.
*/
@SuppressWarnings("unchecked")
public BTNode(Object item, BTNode left, BTNode right) {
// bind to references
this.item = (E) item;
this.left = left;
this.right = right;
}
/**
* Constructs the BTNode (one parameter).
*
* @param The item to be stored in the node.
*/
public BTNode(Object item) {
// call three parameter constructor
this(item, null, null);
}
}
}