haskell - 在二叉树haskell中搜索一个值

Question

我刚开始学习 Haskell，我正在尝试编写代码来在二叉树中搜索特定值，如果存在则返回 true 否则返回 false这就是我的树结构的样子

data Tree = Leaf Int | Node Tree Int Tree

我不确定如何继续遍历树并返回值的函数。我确实尝试了 BFS 和 DFS，但我不确定一旦我得到了我的值(value)如何返回。

我的函数应该是什么样子的例子

Search 5 (Node (Node (Leaf 1) 3 (Leaf 4)) 5 (Node (Leaf 6) 7 (Leaf 9))) 

Answer 1

二分查找可以写成如下形式。该类型可以更通用，因为我们只需要可排序的项目即可在二叉树中存储/搜索。

我们访问每个节点并返回 true，或在其中一个子节点中搜索。

示例节点

   5
 /   \
3     7

让我们搜索 7。

我们首先访问根。因为 5 != 7，我们测试一个子节点。由于7 > 5，我们在右节点搜索，因为7不可能出现在左 child 中(所有值保证在左 child 上小于5)

如果我们到达一片叶子，我们只检查它是否包含搜索词。

search :: Ord a => a -> BinaryTree a -> Bool
search a (Leaf b) = compare a b == EQ
search a (Node left b right) 
  case compare a b of 
    EQ -> True
    LT -> search a left
    GT -> search a right