George George - 3 months ago 7
Java Question

OOP: inheritance with recursive class definition

I have (recursively) defined a class for implementing a binary tree (in Java):

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

// some methods...
}


from which I want to implement a binary search tree, like this:

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;
}
}


but of course the lines marked with
// (*)
won't compile beacause
left
and
right
are just
BinaryTree
s, without any
search()
method.

So I am wondering if theres is a way to define
BinarySearchTree
from the
BinaryTree
superclass but with
left
and
right
being actually
BinarySearchTree
s.

Or maybe there is a better way of implementing the relationship between binary trees and the search ones: should I define a separate
Node
class? should I use templates? should I avoid recursive definitions at all? ...

Answer

You can use recursive generics.

Define a recursive generic type variable, say, B:

class BinaryTree<B extends BinaryTree<B>> {

and make your fields of this type:

protected B left, right;

Then define:

class BinarySearchTree extends BinaryTree<BinarySearchTree> {

Now left and right are of type BinarySearchTree too, allowing you to call left.search and right.search.

Comments