sample problem: tree search
- problem
a tree consists of a key, a value and a list of subtrees
write a search procedure that takes a tree and a key and returns a list of all values associated with the key
assume you have procedures empty?, key, value, next where (next t) returns the subtrees of t
- code
(define (search t k) (define (dfs trees) (if (null? trees)
nil (let ((t1 (car trees))) (if (eq? (key t1) k) (cons (val t1) (dfs (append (next t1) (cdr trees)))) (dfs (append (next t1) (cdr trees)))))))
(dfs (list t)))