1
私は一種の私を混乱させています。この宿題に取り組んでいます
私は、次のBinarySearchTreeクラスを提供しています
import java.util.NoSuchElementException;
/**
*
* @param <T> The type of data stored in the nodes of the tree, must implement Comparable<T> with the compareTo method.
*/
public class BinarySearchTree<T extends Comparable<T>> {
BinaryTree<T> tree;
int size;
public BinarySearchTree() {
tree = new BinaryTree<T>();
size = 0;
}
public boolean isEmpty() {
return tree.isEmpty();
}
protected BinaryTree<T> recursiveSearch(BinaryTree<T> root, T key) {
if (root == null) {
return null;
}
int c = key.compareTo(root.data);
if (c == 0) {
return root;
}
if (c < 0) {
return recursiveSearch(root.left, key);
} else {
return recursiveSearch(root.right, key);
}
}
public T search(T key) {
if (tree.isEmpty()) {
return null;
}
return recursiveSearch(tree, key).data;
}
public void insert(T item) {
if (tree.isEmpty()) { // insert here
tree.makeRoot(item);
size++;
return;
}
// do an iterative descent
BinaryTree<T> root = tree;
boolean done=false;
BinaryTree<T> newNode = null;
while (!done) {
int c = item.compareTo(root.data);
if (c == 0) { // duplicate found, cannot be inserted
throw new OrderViolationException();
}
if (c < 0) { // insert in left subtree
if (root.left == null) { // insert here as left child
newNode = new BinaryTree<T>();
root.left = newNode;
done=true;
} else { // go further down left subtree
root = root.left;
}
} else { // insert in right subtree
if (root.right == null) { // insert here as right child
newNode = new BinaryTree<T>();
root.right = newNode;
done=true;
} else { // go further down right subtree
root = root.right;
}
}
}
// set fields of new node
newNode.data = item;
newNode.parent = root;
size++;
}
/**
* @param deleteNode Node whose parent will receive new node as right or left child,
* depending on whether this node is its parent's right or left child.
* @param attach The node to be attached to parent of deleteNode.
*/
protected void deleteHere(BinaryTree<T> deleteNode, BinaryTree<T> attach) {
// deleteNode has only one subtree, attach
BinaryTree<T> parent = deleteNode.parent;
deleteNode.clear(); // clear the fields
if (parent == null) {
return;
}
if (deleteNode == parent.left) {
// left child of parent, attach as left subtree
parent.detachLeft();
parent.attachLeft(attach);
return;
}
// attach as right subtree
parent.detachRight();
parent.attachRight(attach);
}
protected BinaryTree<T> findPredecessor(BinaryTree<T> node) {
if (node.left == null) {
return null;
}
BinaryTree<T> pred = node.left; // turn left once
while (pred.right != null) { // keep turning right
pred = pred.right;
}
return pred;
}
public T delete(T key) {
if (tree.isEmpty()) { // can't delete from an empty tree
throw new NoSuchElementException();
}
// find node containing key
BinaryTree<T> deleteNode = recursiveSearch(tree, key);
if (deleteNode == null) { // data not found, can't delete
throw new NoSuchElementException();
}
BinaryTree<T> hold;
// case c: deleteNode has exactly two subtrees
if (deleteNode.right != null && deleteNode.left != null) {
hold = findPredecessor(deleteNode);
deleteNode.data = hold.data;
deleteNode = hold; // fall through to case a or b
}
// case a: deleteNode is a leaf
if (deleteNode.left == null && deleteNode.right == null) {
deleteHere(deleteNode, null);
size--;
return deleteNode.data;
}
// case b: deleteNode has exactly one subtree
if (deleteNode.right != null) {
hold = deleteNode.right;
deleteNode.right = null;
} else {
hold = deleteNode.left;
deleteNode.left = null;
}
deleteHere(deleteNode,hold);
if (tree == deleteNode) { // root deleted
tree = hold;
}
size--;
return deleteNode.data;
}
public T minKey() {
if (tree.data == null) { // tree empty, can't find min value
throw new NoSuchElementException();
}
BinaryTree<T> root = tree;
T min=root.data;
root = root.left; // turn left once
while (root != null) { // keep going left to leftmost node
min = root.data;
root = root.left;
}
return min;
}
public T maxKey() {
if (tree.getData() == null) { // tree empty, can't find max value
throw new NoSuchElementException();
}
BinaryTree<T> root=tree;
T max=root.data;
root = root.right; // turn right once
while (root != null) { // keep going to rightmost node
max = root.data;
root = root.right;
}
return max;
}
public int size() {
return size;
}
protected void recursivePreOrder(BinaryTree<T> root, Visitor<T> visitor) {
if (root != null) {
visitor.visit(root);
recursivePreOrder(root.left, visitor);
recursivePreOrder(root.right, visitor);
}
}
public void preOrder(Visitor<T> visitor) {
if (tree.isEmpty()) {
return;
}
recursivePreOrder(tree, visitor);
}
protected void recursiveInOrder(BinaryTree<T> root, Visitor<T> visitor) {
if (root != null) {
recursiveInOrder(root.left, visitor);
visitor.visit(root);
recursiveInOrder(root.right, visitor);
}
}
public void inOrder(Visitor<T> visitor) {
if (tree.isEmpty()) {
return;
}
recursiveInOrder(tree, visitor);
}
protected void recursivePostOrder(BinaryTree<T> root, Visitor<T> visitor) {
if (root != null) {
recursivePostOrder(root.left, visitor);
recursivePostOrder(root.right, visitor);
visitor.visit(root);
}
}
public void postOrder(Visitor<T> visitor) {
if (tree.isEmpty()) {
return;
}
recursivePostOrder(tree, visitor);
}
}
====== ========================================== ==========================
今私は別のクラスの学生がいる.... 私は学生オブジェクトのバイナリ検索ツリーを作成したい..
BinarySearchTree<Student> tree = new BinarySearchTree<Student>();
しかし、私は、私は次のエラーを取得することを行うとき：
バウンド不一致を：タイプBinarySearchTreeのタイプの学生は、有界パラメータの有効な代わるものではありません>
任意のアイデアここで何が起こっていますか。 ..私はそれを把握することはできません。
「BinarySearchTree>」の代わりに、「Comparable >」を拡張します。あなたが持っている方法は、必要以上に制限があり、Comparableを実装しているクラスのサブクラスがあるときに問題に遭遇します。 –
newacct