OOP：私は（<em>再帰的に</em>）は再帰的なクラス定義

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 beacauseコンパイルされませんとrightはちょうどBinaryTreeのある、WI：このような任意のsearch()メソッドがあります。

leftとrightが実際にBinarySearchTreeのものでBinaryTreeスーパーからBinarySearchTreeが、を定義する方法がtheresのであれば、私は疑問に思って。

または、検索のものとの関係を実現するには、より良い方法があります。別の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があり、ツリーのルートとなるタイプBinaryTreeNodeの参照を持つべきであるleftとrightノード

BinaryTree.javaの型BinaryTreeNodeの2つの参照ができます。

今度は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; 
    } 

} 

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 
}