OOP:使用递归类定义继承

Question

我(递归地)定义了一个用于实现二叉树的类(在Java中):

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

    // some methods...
}

我想从中实现二进制搜索树,如下所示:

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

但当然标记的行// (*)不会编译left而right只是BinaryTrees,没有任何search()方法.

所以我想知道如果那里有一种方法可以定义BinarySearchTree从BinaryTree超类,但用left和right是实际BinarySearchTree秒.

或者可能有更好的方法来实现二叉树和搜索树之间的关系:我应该定义一个单独的Node类吗？我应该使用模板吗？我应该避免递归定义吗？...

Answer 1

您可以使用递归泛型.

定义一个递归泛型类型变量,比如说B:

class BinaryTree<B extends BinaryTree<B>> {

并使您的类型的字段:

protected B left, right;

然后定义:

class BinarySearchTree extends BinaryTree<BinarySearchTree> {

现在,left和right有型的BinarySearchTree太多,让你打电话left.search和right.search.