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只是BinaryTree S，无线网络没有任何search()方法。

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

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

Answer 1

您可以使用递归泛型。

定义递归泛型类型变量，说，B：

class BinaryTree<B extends BinaryTree<B>> { 

，使你这种类型的字段：

protected B left, right; 

然后定义：

class BinarySearchTree extends BinaryTree<BinarySearchTree> { 

现在left和right类型为也可以拨打left.search和right.search。

Answer 2

我觉得BinaryTreeNode应该被创建为BinaryTree.java的内部类。 BinaryTreeNode可以具有int data，以及用于left和right节点

BinaryTree.java应具有BinaryTreeNode类型的参考，这将是该树的根BinaryTreeNode类型的两个引用。

现在BinarySearchTree extends BinaryTree看起来不错，你可以在其中包含一个方法，如下签名。

BinaryTreeNode `search(int k, BinaryTreeNode root)` 

现在您可以定义递归方法。

请参阅带基本框架的示例代码。

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

} 

二叉树。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 
}