Haskell中如何查找树的最左节点值？

To solve this problem, we need to recursively traverse the left subtree of each node until we can't go left anymore—this final node's value is our leftmost value. Here's how to implement it properly:

Approach #

The core idea is straightforward:

• For an empty tree (Leaf), return Nothing since there's no value to find.
• For a non-empty node (Node a left right):
  1. First, recursively check the left subtree. If it has a leftmost value (returns Just x), that's our answer.
  2. If the left subtree is empty (returns Nothing), the current node's value a is the leftmost one, so return Just a.

Complete Implementation #

Here's the full code, including your existing base case:

data Tree a = Leaf | Node a (Tree a) (Tree a) deriving (Show, Eq)

leftest :: Tree a -> Maybe a
leftest Leaf = Nothing
leftest (Node a left _) = case leftest left of
    Nothing -> Just a
    Just x -> Just x

Concise Alternative Using <|> #

Since Maybe implements the Alternative typeclass, we can use the <|> operator to simplify the recursive case. This operator tries the first option; if it's Nothing, it falls back to the second:

leftest :: Tree a -> Maybe a
leftest Leaf = Nothing
leftest (Node a left _) = leftest left <|> Just a

Testing the Example #

Let's verify with your sample input:

leftest (Node 1 (Node 2 (Node 3 Leaf Leaf) Leaf) Leaf)

• We first traverse left from Node 1 to Node 2, then to Node 3.
• Node 3's left child is Leaf, so leftest Leaf returns Nothing.
• This triggers the fallback to Just 3, which is our correct result.

Another test case: if the root has no left child, like leftest (Node 1 Leaf (Node 3 Leaf Leaf)), it returns Just 1—which is correct, since we can't go left from the root.

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