جافا عام ثنائي البحث شجرة مسألة نوع
-
03-07-2019 - |
سؤال
وأنا أعمل على هذا المنزلية وهذا النوع من يحيرني ...
وأنا قدمت مع الطبقة 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 > >
ولذا تحتاج إلى جعل الطلاب تنفيذ المقارن <الطلبة>.
وعلما بأنني <م> لا م> القول إن البرمجي تبحث عن Student.compareTo
. بل لا تصل لهذا الحد. انها تبحث لمعرفة ما إذا كان T (في قضيتك، طالبة) كما اعلن هو تنفيذ للمقارنة
والآن مضيفا implements Comparable< Student >
إلى الطلاب سوف <م> أيضا م> جعل مترجم ضمان أن هناك طريقة public int compareTo
على الطلاب. ولكن من دون "تنفذ المقارن"، حتى لو كان المترجم يعرف هناك Student.compareTo
الأسلوب، فإنه لا يعرف أن هذا compareTo
هو Comparable.compareTo
.
(وبعبارة أخرى، نحن نبحث عن تنفيذ المعلنة، وليس فقط أن يحدث أن تكون وسيلة مع الاسم الصحيح والتوقيع هناك).
نصائح أخرى
هل تنفذ طالب الصف للمقارنة؟
ولكن لست متأكدا تماما من كيفية تنفيذ أسلوب 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
}
}