scheme - Scheme 中的二叉树

Question

考虑以下定义数字树的 BNF。请注意，树可以是叶子、具有一个子树的节点 1 或节点 2有两个子树。

tree ::= (’leaf number)
| (’node-1 tree)
| (’node-2 tree tree)

一个。为这些树上的递归过程编写一个模板。

定义返回的过程(叶计数 t)t中的叶子数

> (leaf-count ’(leaf 5))

1

> (leaf-count ’(node-2 (leaf 25) (leaf 17)))

2

> (leaf-count ’(node-1
(node-2 (leaf 4)
(node-2 (leaf 2) (leaf 3)))))

3

这是我目前所拥有的:

;define what a leaf, node-1, and node-2 is
(define leaf list)
(define node-1 list)
(define node-2 list)

;procedure to decide if a list is a leaf or a node
(define (leaf? tree) (number? (car tree)))
(define (node? tree) (pair? (car tree)))

(define (leaf-count tree)
 (cond ((null? tree) 0)
        ((number? tree) 0)
        ((leaf? tree) 1)
        (else (+ (leaf-count (car tree))
                 (leaf-count (cdr tree))))))

看起来它应该运行得很好，但是当我尝试使用像这样的简单测试用例运行它时

(leaf-count '(leaf 5))

我收到以下错误消息:

car: expects argument of type pair; given leaf

此错误消息是什么意思？我将叶子定义为列表。但出于某种原因，它没有看到并给我该错误消息。

Answer 1

确实，解决别人的作业很有趣。

(define leaf-count
  (match-lambda 
   [(list 'leaf x)     1]
   [(list 'node-1 t)   (leaf-count t)]
   [(list 'node-2 l r) (+ (leaf-count l) (leaf-count r))]))