Haskell二叉树值搜索实现求助：判断目标值是否存在

嘿，刚学Haskell的话，二叉树的搜索其实非常适合用递归的DFS（深度优先搜索）来实现，而且Haskell的特性刚好能帮你解决“找到值后如何返回”的问题——不用手动中断遍历，利用短路逻辑运算符就能自动提前终止！

先从最直观的DFS实现开始：

DFS实现（前序遍历） #

首先我们明确函数的类型签名，然后针对二叉树的两种构造器分别处理：

-- 你的二叉树结构定义
data Tree = Leaf Int | Node Tree Int Tree

-- 搜索函数：接收目标值和树，返回是否存在该值
search :: Int -> Tree -> Bool
-- 处理叶子节点：直接判断叶子的值是否等于目标
search target (Leaf x) = x == target
-- 处理内部节点：三种情况满足其一就返回True
search target (Node left x right) = 
  x == target          -- 当前节点就是目标值
  || search target left  -- 左子树里有目标值
  || search target right -- 右子树里有目标值

为什么这样能“找到后返回”？ #

这里的关键是Haskell的||运算符是短路求值的：只要左边的表达式为True，右边的表达式就不会被计算了。比如当我们找到当前节点的值就是目标时，后面的左右子树递归都不会执行，直接返回True——完美实现了“找到就停止遍历并返回结果”的需求！

BFS实现（层序遍历） #

如果你想用BFS（广度优先搜索），可以用列表模拟队列来实现，需要一个辅助函数维护待遍历的节点队列：

searchBFS :: Int -> Tree -> Bool
searchBFS target tree = helper [tree]
  where
    -- 辅助函数：接收节点队列，返回是否找到目标
    helper [] = False  -- 队列为空，说明整个树都遍历完了没找到
    -- 处理队列首的叶子节点
    helper (Leaf x : rest) = x == target || helper rest
    -- 处理队列首的内部节点：检查当前值，然后把左右子树加到队列末尾
    helper (Node left x right : rest) = 
      x == target 
      || helper (rest ++ [left, right])

同样，这里的||短路求值也会在找到目标时立刻停止遍历，不用处理后续队列。

测试示例 #

我们可以构造一个示例树来测试这两个函数：

-- 构造一棵示例树：
--       3
--      / \
--     1   5
--    / \
--   0   2
sampleTree :: Tree
sampleTree = Node (Node (Leaf 0) 1 (Leaf 2)) 3 (Leaf 5)

-- 测试结果：
-- search 5 sampleTree → True
-- search 4 sampleTree → False
-- searchBFS 0 sampleTree → True
-- searchBFS 6 sampleTree → False

小提示 #

对于Haskell的树结构来说，递归的DFS写法更简洁也更符合函数式编程的风格，因为树本身就是递归定义的。而BFS因为需要维护状态（队列），所以需要用辅助函数来封装状态。

内容的提问来源于stack exchange，提问作者Dipesh Desai