Binary trees in the scheme

Question

Consider the following BNFs defining number trees. Note that a tree can be either a leaf, or node -1 with one subtree, or node -2 with two subtrees.

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

and. Write a template for recursive procedures on these trees.

b. Define a procedure (count-count t) that returns the number of leaves in 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

Here is what I still have:

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

It seems like it should work fine, but when I try to run it using a simple test case like

(leaf-count '(leaf 5))

The following error message appears:

car: expects an argument of a pair of types; this sheet

What does this error message mean? I define the sheet as a list. But for some reason he does not see this and gives me this error message.

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

Answer 2

, (leaf-count '(leaf 5)), , , . , , . , node BNF.

: ’(node-1 (node-2 (leaf 4) (node-2 (leaf 2) (leaf 3)))). : node-1, node-2 leaf . leaf? node?, , . , true:

(define a-tree ’(node-1 (node-2 (leaf 4) (node-2 (leaf 2) (leaf 3)))))
(node? a-tree)
(node? (car (cdr a-tree)))
(leaf? (car (cdr (car (cdr a-tree)))))
(node? (car (cdr (cdr (car (cdr a-tree))))))
(leaf? (car (cdr (car (cdr (cdr (car (cdr a-tree))))))))

, ( , , ).

Answer 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? (cadr tree)))
(define (node? tree) (pair? (cadr tree)))

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

I got it to work with a minor tweak: change the conditions to check the list frame, as this is what contains the information. The list car in this case is just a data label (leaf, node, etc.). Not really. I got it to work in the simplest test cases, but not for more complex ones like

(leaf-count '(node-2 (leaf 25) (leaf 17)))