我想我无限循环此BST

Question

这个代码，我得到的是从亚历山大巴提斯蒂有关如何从数据的列表中进行树：

let data = [4;3;8;7;10;1;9;6;5;0;2] 

type Tree<'a> = 
    | Node of Tree<'a> * 'a * Tree<'a> 
    | Leaf 

let rec insert tree element = 
    match element,tree with 
    | x,Leaf  -> Node(Leaf,x,Leaf) 
    | x,Node(l,y,r) when x <= y -> Node((insert l x),y,r) 
    | x,Node(l,y,r) when x > y -> Node(l,y,(insert r x)) 
    | _ -> Leaf 


let makeTree = List.fold insert Leaf data 

的话，我想实现这个代码，以我的二进制搜索树码

let rec BinarySearch tree element = 
    match element,tree with 
    | x,Leaf -> BinarySearch (Node(Leaf,x,Leaf)) x 
    | x,Node(l,y,r) when x<=y -> 
     BinarySearch l y 
    | x,Node(l,y,r) when x>y -> 
     BinarySearch r y 
    | x,Node(l,y,r) when x=y -> 
     true 
    | _ -> false 

然后我用我的搜索代码：

> BinarySearch makeTree 5;; 

，结果是没有的，因为它是LIK é我得到了无限循环 有人可以帮助我吗？如果我的代码错了，请帮我改正它，谢谢

Answer 1

尹的解决方案是我怎么写它。

不管怎么说，这是一个解决方案，是更接近你的版本，（希望）解释了什么问题：

let rec BinarySearch tree element = 
    match element,tree with 
    | x, Leaf -> 
    // You originally called 'BinarySearch' here, but that's wrong - if we reach 
    // the leaf of the tree (on the path from root to leaf) then we know that the 
    // element is not in the tree so we return false 
    false 
    | x, Node(l,y,r) when x<y ->// This needs to be 'x<y', otherwise the clause would be 
           // matched when 'x=y' and we wouldn't find the element! 
    BinarySearch l element // Your recursive call was 'BinarySearch l y' but 
           // that's wrong - you want to search for 'element' 
    | x, Node(l,y,r) when x>y -> 
     BinarySearch r element 
    | x,Node(l,y,r) ->   // You can simplify the code by omitting the 'when' 
     true     // clause (because this will only be reached when 
           // x=y. Then you can omit the last (unreachable) case 

Answer 2

let rec BinarySearch tree element = 
    match tree with 
    | Leaf -> false 
    | Node(l, v, r) -> 
     if v = element then 
      true 
     elif v < element then 
      BinarySearch r element 
     else 
      BinarySearch l element 


BinarySearch makeTree 5