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 returnsa list of all values associated with the key
assume you have proceduresempty?, key, value, nextwhere (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)))