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 
}