二分探索in sml

Question

datatype 'a tree= Leaf of 'a | Node of 'a tree * 'a * 'a tree 

fun binSearch (Node(left,n,right)) x = 
    if x > n then false 
    else if x=n then true 
    else binSearch (Node(left,n,right)) x = binSearch (right) x andalso binSearch (left) x; 

私は無力です。そのコードの何が間違っていますか？ はところでそれがために働く：

binSearch (Node (Node (Leaf 1, 2, Leaf 3), 4, Leaf 7)) 7; 

とでは動作しません：最初の条件で

binSearch (Node (Node (Leaf 1, 2, Leaf 3), 4, Leaf 7)) 2; 

Answer 1

、あなたはxより小さい何の要素がどのツリーに存在しないことを言っています。また、あなたの最後のelse、

binSearch (Node(left,n,right)) x = binSearch (right) x andalso binSearch (left) x 

を

binSearch (Leaf n) x = n = x 

：あなたは価値が間違いなく検出されないかどうかを知る唯一のケースである空の木、のためのケースを書くのを忘れ

は、binSearch (Node(left,n,right)) xがbinSearch right x andalso binSearch left xと同じ結果をもたらすかどうかの比較です。
つまり、ツリー全体でとの両方のサブツリーにあるか、まったく見つからない場合は、xがツリー内に見つかります。

再帰はxは、ノードの値nであれば、我々はそれを見つけた

• を行く必要があります。
  x > n、右部分木に再帰

実装は、練習として残した場合はそれ以外の場合は、

• x < nの場合は、
• 、左部分木に再帰。

Answer 2

2つの要素でツリーを構築できないなど、バイナリツリーの定義は理想的ではありません。より柔軟で一般的に単純な定義はLeafはない要素をもつツリーである

datatype 'a tree = Leaf | Node of 'a tree * 'a * 'a tree 

あります。これはあなたが非常に簡単なベースケースを書き込むことができます：

Nodeケースでは

fun binSearch t x = 
    case t of 
    Leaf => false 
    | Node (left, n, right) => ... 

、あなたは現在の値nに希望の値xを比較する三つの可能性に応じて、あなたのコードを構築することが役に立つかもしれません。

fun binSearch t x = 
    case t of 
    Leaf => false 
    | Node (left, n, right) => 
     case Int.compare (x, n) of 
     LESS => ... 
     | EQUAL => true 
     | GREATER => ... 

私はあなたに残ります。