Java汎用バイナリ検索ツリータイプの問題
https://stackoverflow.com/questions/814212
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
この宿題に取り組んでいるので、ちょっと混乱します...
次の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);
}
}
=============================================== ==================================
別のクラスの生徒がいます。 Studentオブジェクトのバイナリ検索ツリーを作成したい。.
BinarySearchTree<Student> tree = new BinarySearchTree<Student>();
しかし、それを行うと、次のエラーが表示されます。
バウンドミスマッチ：タイプStudentは、バウンドパラメーター<！> gt;の有効な代替ではありません。タイプBinarySearchTree
のここで何が起きているのか考えてみてください...わかりません。
解決
public class BinarySearchTree<T extends Comparable<T>>
正式なジェネリック引数は、Tの場合、クラスが有効なTであるために必要なものをリストします。 <！> quot; （キーワードは<！> quot; extends <！> quot;ですが、実際には<！> quot; extends or implements <！> quot;を意味します。）
インスタンス化では、TはStudentです。 TをStudentに置き換えた場合：
public class BinarySearchTree<Student extends Comparable<Student>>
それは本当の声明ですか？学生は本当にComparableを実装していますか？
その場合、StudentはTであるという要件に適合します。そのため、Studentを仮パラメータTの実際のパラメータとして使用できます。
そうでない場合は、見たコンパイラの苦情を受けます。
実際には、サブクラスのComparableの実装がスーパークラスによって行われるより複雑な状況をカバーするには、より一般的な形式は次のようになります。
public class BinarySearchTree<T extends Comparable<? super T > >
したがって、学生にComparable <！> lt;を実装させる必要があります。学生<！> gt;。
コンパイラがStudent.compareToを探しているとはしませんでしたことに注意してください。それはそこまで行かない。 T（あなたの場合、Student）がComparable <！> ltの実装として宣言されているかどうかを確認します。 T <！> gt; （あなたの場合、Comparable <！> lt; Student <！> gt;）。
Studentにimplements Comparable< Student >を追加すると、 コンパイラにより、Studentにpublic int compareToメソッドが存在することも確認されます。しかし、<！> quot; implements Comparable <！> quot;がない場合、コンパイラがメソッドcompareToを知っていても、Comparable.compareToが<=>であることはわかりません。
（言い換えると、正しい名前とシグネチャを持つメソッドがあるだけでなく、宣言された実装を探しています。）
他のヒント
クラスStudentはComparableを実装しますか？
しかし、どうすればいいのかよくわかりません compareToメソッドを実装します。
基本的には次のようなものです。順序がどのように機能するかを決定する必要があります。
class Student implements Comparable<Student> {
//...
int compareTo(Student other) {
// return some negative number if this object is less than other
// return 0 if this object is equal to other
// return some positive number if this object is greater than other
}
}
所属していません StackOverflow
