2017-11-26 25 views
1

私は以下のクラスを持っています。ユーザに、整数でBSTを作成するか、文字列でBSTを作成するかを選択させたいと思います。ユーザーが5を選択したときに整数からBSTを作成するか、ユーザーが6を押すときに文字列からBSTを作成するにはどうすればよいですか?また、誰かが私のジェネリック薬に間違ったことを見つけた場合は、私に知らせてください!私はに文字列(ユーザー入力)を処理するメソッドを追加しますバイナリ検索ツリーの汎用

:これは私の提案

どうもありがとう、あなたのコード内のジェネリック医薬品のほとんどを得るために

public class BSTNode <T extends Comparable<T>> 
{ 
     T value; 
     BSTNode<T> left; 
     BSTNode<T> right; 

     public BSTNode(T value, BSTNode<T> l,BSTNode<T> r) 
     { 
      this.value = value; 
      left = l; 
      right = r; 
     } 

     public BSTNode(T value) 
     { 
      this(value,null,null); 
     } 

     public T getValue() 
     { 
      return value; 
     } 

     public void setValue(T value) 
     { 
      this.value = value; 
     } 

     public BSTNode<T> getLeftChild() 
     { 
      return left; 
     } 

     public BSTNode<T> getRightChild() 
     { 
      return right; 
     } 

     public void setLeftChild(BSTNode<T> node) 
     { 
      left = node; 
     } 

     public void setRightChild(BSTNode<T> node) 
     { 
      right = node; 
     } 

     public boolean search(T value) 
     { 
      if (value.equals(this.value)) 
        return true; 
      else if (value.compareTo(this.value) < 0) 
      { 
        if (left == null) 
         return false; 
        else 
         return left.search(value); 
      } else if (value.compareTo(this.value) > 0) 
      { 
        if (right == null) 
         return false; 
        else 
         return right.search(value); 
      } 
      return false; 
     } 

     public boolean add(T value) 
     { 
      if (value.compareTo(this.value)==0) 
        return false; 
      else if (value.compareTo(this.value) < 0) 
      { 
        if (left == null) 
        { 
         left = new BSTNode<T>(value); 
         return true; 
        } else 
         return left.add(value); 
      } 
      else if (value.compareTo(this.value) > 0) 
      { 
        if (right == null) 
        { 
         right = new BSTNode<T>(value); 
         return true; 
        } 
        else 
         return right.add(value); 
      } 
      return false; 
     } 



    public boolean remove(T value2, BSTNode<T> parent) 
     { 
     if (value2.compareTo(this.value)<0) 
     { 
      if (left != null) 
       return left.remove(value2, this); 
      else 
       return false; 
     } 
     else if (value2.compareTo(this.value)>0) 
     { 
      if (right != null) 
       return right.remove(value2, this); 
      else 
       return false; 
     } 
     else 
     { 
      if (left != null && right != null) 
      { 
       this.value = right.minValue(); 
       right.remove(this.value, this); 
      } 
      else if (parent.left == this) 
      { 
       parent.left = (left != null) ? left : right; 
      } 
      else if (parent.right == this) 
      { 
       parent.right = (left != null) ? left : right; 
      } 
      return true; 
     } 
    } 

    public T minValue() 
    { 
     if (left == null) 
      return value; 
     else 
      return left.minValue(); 
    } 

} 

    public class BinarySearchTree <T extends Comparable<T>> 
{ 
     private BSTNode<T> root; 

     public BinarySearchTree(T value) 
     { 
      root = new BSTNode<T>(value); 
     } 


     public BSTNode getRoot() 
     { 
      return root; 
     } 

     public boolean search(T value) 
     { 
      if (root.equals(null)) 
       return false; 
     else 
       return root.search(value); 
    } 

     public boolean add(T value) 
     { 
      if (root == null) { 
       root = new BSTNode(value); 
       return true; 
     } else 
       return root.add(value); 
     } 

     public boolean remove(T value) { 
      if (root == null) 
       return false; 
      else { 
       if (root.getValue() == value) { 
        BSTNode auxRoot = new BSTNode(null); 
        auxRoot.setLeftChild(root); 
        boolean result = root.remove(value, auxRoot); 
        root = auxRoot.getLeftChild(); 
        return result; 
       } else { 
        return root.remove(value, null); 
       } 
      } 
      } 

    public static void displayInorder(BSTNode T) 
     { 
      if (T!=null) 
      { 
       if (T.getLeftChild()!=null) 
       {    
        displayInorder(T.getLeftChild());    
       } 
       System.out.print(T.getValue() + " "); 
       if(T.getRightChild()!=null) 
       { 
        displayInorder(T.getRightChild()); 
       } 
      } 

     } 
    } 

import java.util.Scanner; 

public class main { 
    public static void main(String[] args) { 
     BinarySearchTree b = new BinarySearchTree(null); 
     boolean flag = true; 
     while (flag) { 
     Scanner scan = new Scanner(System.in); 
      System.out.println("Select 1 to add values in to BST\n" 
       + "Select 2 to delete values from the BST \n" 
       + "Select 3 to search for a value\n" 
       + "Select 4 to display te values held in the BST\n" 
       + "Select 5 to create a BST of strings\n" 
       + "Select 6 to create a BST of integers\n" 
       + "Select 7 to exit"); 
      int opt = scan.nextInt(); 

    switch (opt) { 
    case 1: System.out.println("Insert the value of your choice: "); 
      String str = scan.next(); 
      b.add(str); 
      break; 
    case 2: System.out.println("Insert the value of your choice: "); 
       str = scan.next(); 
       b.remove(str); 
      break; 
    case 3: 
     System.out.println("Insert the value of your choice: "); 
      str = scan.next(); 
      b.search(str); 
     break; 
    case 4: 
     BinarySearchTree.displayInorder(b.getRoot()); 
     break; 
    case 5: 

    case 7: 
     flag=false; 
     break; 
    } 
    } 
} 
} 

答えて

0

ですツリーのクラスの適切なタイプ:

... 
import java.util.function.Function; 
... 

public class BinarySearchTree <T extends Comparable<T>> 
{ 
     private BSTNode<T> root; 
     private Function<String,T> valueDecoder 

     public BinarySearchTree(final Function<String,T> valueDecoder) 
     { 
      this.valueDecoder = valueDecoder; 
      root = new BSTNode<T>(null); 
     } 

     ... 
     public boolean decodeAndAdd(final String encodedValue) { 
      return add(valueDecoder.apply(encodedValue)); 
     } 

     public boolean decodeAndRemove(final String encodedValue) { 
      return remove(valueDecoder.apply(encodedValue)); 
     } 
} 

`` `

次に、あなたでしょう実際にユーザーが指定したツリーの種類が得られるまでb変数を未定義/ nullのままにします。それがここにStringまたはIntegerが含まれる場合がありますので、その制約の一部であるとして、あなただけおそらく​​、型パラメータとして?を使用することができます... ?は、この場合に罰金です:

BinarySearchTree<?> b = null

今、ユーザーは、あなたが実際の要素の値にスキャン文字列を転送するための適切なラムダを提供する必要がStringまたはInteger木を求めるとき:

case 5: 
    b = new BinarySearchTree<>(scanStr -> scanStr); 
    break; 
case 6: 
    b = new BinarySearchTree<>(scanStr -> Integer.parseInt(scanStr)); 
    break; 

今すぐ追加および削除些細です:

case 1: 
    b.decodeAndAdd(scan.next()); 
    break; 

case 2: 
    b.decodeAndRemove(scan.next()); 
    break; 

ツリーがIntegerツリーのときに無効な整数文字列値を指定すると、NumberFormatExceptionとなり、プログラムが停止します。おそらくエラーメッセージを表示して、ユーザーが別の演算子を実行できるようにします。そのために:

case 6: 
    b = new BinarySearchTree<>(scanStr -> { 
     try { 
      return Integer.parseInt(scanStr); 
     } catch (NumberFormatException ex) { 
      throw new IllegalArgumentException("you must provide a valid integer value: '" + scanStr + "'"); 
     } 
    }); 
    break; 
... 

case 1: 
    try { 
     b.decodeAndAdd(scan.next()); 
    } catch (final IllegalArgumentException ex) { 
     System.err.println("ERROR: " + ex.getMessage()); 
    } 
    break; 

case 2: 
    try { 
     b.decodeAndRemove(scan.next()); 
    } catch (final IllegalArgumentException ex) { 
     System.err.println("ERROR: " + ex.getMessage()); 
    } 
    break; 

はおそらく、あなたはBSTは、問題の説明ユーザコマンドラインコンテキスト外で使用されるかもしれないとして、もう少しモジュラーものを維持したい場合は、あなたのBinarySearchTreeクラスにdecodeAndAddとdecodeAndRemoveを追加することが理想的ではありません。

この場合、BSTへの参照と型パラメータを使用して同じ要素タイプがバインドされたデコードラムダを含む参照を含む汎用の「構造体」クラスを定義できます。

class CommandLineBST<T> { 

    public final BST<T> tree; 
    public final Function<String, T> valueDecoder; 

    public CommandLineBST(final BST<T> tree, final Function<String, T> decoder) { 
     this.tree = tree; 
     this.valueDecoder = decoder; 
    } 

    public boolean add(final String scanStr) { 
    return tree.add(valueDecoder.apply(scanStr)); 
    } 

    public boolean remove(final String scanStr) { 
    return tree.remove(valueDecoder.apply(scanStr)); 
    } 

} 

または

class CommandLineBST<T> extends BST<T> { 
    private Function<String, T> valueDecoder; 

    public CommandLineBST(final Function<String, T> valueDecoder) { 
     super(null); 
     this.valueDecoder = valueDecoder; 
    } 

    public boolean decodeAndAdd(final String scanStr) { ... } 
    public boolean decodeAndRemove(final String scanStr) { ... } 
} 
:あなたはまた、この機能を追加他のユーザー・インタフェース専門BSTでBSTクラスを拡張することができ
関連する問題