Racket语言二叉树treemap高阶函数实现求助

Got it, let's build that treemap function properly. Since we're working with a recursive binary tree structure, Racket's pattern matching is the cleanest way to handle each case (Leaf and Node) recursively.

Here's the complete, working implementation using Racket's match form—this is the idiomatic approach for structural recursion like this:

(define (treemap f tree)
  (match tree
    [(Leaf n) (Leaf (f n))]  ; Transform the leaf value with f and wrap back in a Leaf
    [(Node left right)       ; Recurse on both subtrees and rebuild the Node
     (Node (treemap f left) (treemap f right))]))

Let's break down what's happening:

• Leaf case: When we hit a Leaf containing a number n, we apply the input function f to n, then create a new Leaf with the transformed value. This updates the leaf's content while keeping its structure intact.
• Node case: For a Node with left and right subtrees, we recursively run treemap on both subtrees (so all their leaves get transformed), then create a new Node using those updated subtrees. This preserves the original tree's structure exactly.

Now let's test it with your example. Using add1 to increment each leaf value by 1:

(treemap add1 (Node (Leaf 1) (Node (Leaf 2) (Leaf 3))))

This will return exactly what you expect: (Node (Leaf 2) (Node (Leaf 3) (Leaf 4))).

Quick note: Your test case uses tree-map (with a hyphen) but your initial code uses treemap (no hyphen). I stuck with treemap to match your original code, but you can rename it to tree-map if that's what you need—just make sure the function name is consistent everywhere.

This is a proper higher-order function because it accepts another function (f) as an argument and uses it to transform the leaf values, which is exactly what the problem requires.

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