Binary Trees in Scheme
- by Javier
Consider the following BNF defining trees of numbers.
Notice that a tree can either be a leaf, a node-1 with one subtrees, or a node-2
with two subtrees.
tree ::= (’leaf number)
| (’node-1 tree)
| (’node-2 tree tree)
a. Write a template for recursive procedures on these trees.
b. Define the procedure (leaf-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's what I have so far:
;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 looks like it should run just fine, but when I try to run it using a simple test case like
(leaf-count '(leaf 5))
I get the following error message:
car: expects argument of type pair; given leaf
What does this error message mean? I am defining a leaf as a list. But for some reason, it's not seeing that and gives me that error message.
