OOP: ereditarietà con definizione della classe ricorsiva - java, class, oop, ereditarietà, ricorsione

Io ho (ricorsivamente) ha definito una classe per l'implementazione di un albero binario (in Java):

class BinaryTree {
protected int key;
protected BinaryTree left, right;

// some methods...
}

da cui voglio implementare un binario ricerca albero, come questo:

class BinarySearchTree extends BinaryTree {
// ...

public BinarySearchTree search(int x) {
if (x == key)
return this;
if (x < key)
if (left != null)
return left.search(x);  // (*)
else
if (right != null)
return right.search(x); // (*)
return null;
}
}

ma ovviamente le linee contrassegnate con // (*) non viene compilato perché left e right sono solo BinaryTrees, senza nessuno search() metodo.

Quindi mi chiedo se c'è un modo per definire BinarySearchTree dal BinaryTree superclasse ma con left e right essere effettivamente BinarySearchTreeS.

O forse esiste un modo migliore per implementare la relazione tra alberi binari e ricerca quelli: dovrei definire un separato Node classe? devo usare i modelli? dovrei assolutamente evitare definizioni ricorsive? ...

risposte:

5 per risposta № 1

Puoi usare generici ricorsivi.

Definire una variabile di tipo generico ricorsivo, ad esempio B:

class BinaryTree<B extends BinaryTree<B>> {

e rendi i tuoi campi di questo tipo:

protected B left, right;

Quindi definire:

class BinarySearchTree extends BinaryTree<BinarySearchTree> {

Adesso left e right sono di tipo BinarySearchTree anche, permettendoti di chiamare left.search e right.search.

---

1 per risposta № 2

io sento BinaryTreeNode dovrebbe essere creato come una classe interna diBinaryTree.java. BinaryTreeNode può avere int datae due riferimenti di tipo BinaryTreeNode per left e right nodo

BinaryTree.java dovrebbe avere un riferimento di tipo BinaryTreeNode che sarà la radice dell'albero.

Adesso BinarySearchTree extends BinaryTree sembra buono, puoi includere un metodo come sotto la firma.

BinaryTreeNode `search( int k, BinaryTreeNode root)`

Ora puoi definire il metodo ricorsivo.

Vedere il codice di esempio con lo scheletro di base.

BinaryTreeNode.java

public class BinaryTreeNode {

private int data;
private BinaryTreeNode left, right;

public BinaryTreeNode(int data) {
this.setData(data);
}

public BinaryTreeNode getLeft() {
return left;
}

public void setLeft(BinaryTreeNode left) {
this.left = left;
}

public BinaryTreeNode getRight() {
return right;
}

public void setRight(BinaryTreeNode right) {
this.right = right;
}

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}

}

BinaryTree.java

public class BinaryTree {
protected BinaryTreeNode root;

// other basic methods needed for creating the Binary tree.
}

BinarySearchTree.java

public class BinarySearchTree extends BinaryTree {
public BinaryTreeNode search(int k) {
return search(k, root);
}

private BinaryTreeNode search(int k, BinaryTreeNode root) {
if (root.getData() == k) {
return root;
}
if (root.getData() < k) {
return search(k, root.getRight());
} else {
return search(k, root.getLeft());
}
}
// add other methods needed for creating the Binary search tree.
// also override the methods which needs to be modified for their behavior
// for binary search tree
}

---