Java Generic Binary Search Tree Type 문제
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);
}
}
================================================================================
이제 다른 수업 학생이 있습니다 .... 학생 객체의 이진 검색 트리를 만들고 싶습니다 ..
BinarySearchTree<Student> tree = new BinarySearchTree<Student>();
그러나 그렇게하면 다음과 같은 오류가 발생합니다.
바운드 불일치 : 유형 학생은 유형 BinarySearchTree의 경계 매개 변수를 유효한 대체물이 아닙니다.
여기서 무슨 일이 일어나고 있는지 ... 나는 그것을 알아낼 수 없다.
해결책
public class BinarySearchTree<T extends Comparable<T>>
공식 제네릭 인수는 귀하의 경우 T에서 클래스가 유효한 T가되기 위해 필요한 내용을 나열합니다. 귀하는 "유효한 t이 되려면 클래스가 비슷한 구현"(키워드는 확장됩니다. "그러나 실제로는"확장 또는 구현 "을 의미합니다.)
인스턴스화에서 T는 학생입니다. 우리가 학생을 t로 대체한다면 :
public class BinarySearchTree<Student extends Comparable<Student>>
그게 진정한 진술인가요? 학생이 실제로 비슷한 구현입니까?
그렇다면, 학생은 T가 필요한 요구 사항에 적합하므로 공식 매개 변수 T의 실제 매개 변수로 학생을 사용할 수 있습니다.
그렇지 않다면, 당신은 당신이 본 컴파일러의 불만을 얻습니다.
실제로, 서브 클래스의 비슷한 구현이 슈퍼 클래스에 의해 수행되는보다 복잡한 상황을 다루기 위해서는보다 일반적인 형태는 다음과 같습니다.
public class BinarySearchTree<T extends Comparable<? super T > >
따라서 학생 구현을 비슷한 <tudent>로 만들어야합니다.
i 그렇지 않았다 컴파일러가 찾고 있다고 말합니다 Student.compareTo. 그것은 심지어 그렇게 멀지 않습니다. T (귀하의 경우 학생)가 비슷한 <t> (귀하의 경우 비슷한 <tudent>)를 구현하는 것으로 선언되는지 여부를 찾고 있습니다.
이제 추가 implements Comparable< Student > 학생에게 또한 컴파일러가 있는지 확인하십시오 public int compareTo 학생에 대한 방법. 그러나 "비슷한 구현"이 없으면 컴파일러가 메소드가 있음을 알고 있더라도 Student.compareTo, 그것은 그것을 모른다 compareTo 입니다 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
