计划中的二叉树

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:期望类型对的参数; 给了叶子

这个错误信息是什么意思？我将叶子定义为列表.但出于某种原因,它没有看到,并给了我错误信息.

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))]))