Design Pattern: Binary Tree Recursion

The design pattern for binary tree recursion is similar to that for lists, except that the function is called twice recursively for interior nodes.

(define (myfun tree)
         (if (pair? tree)
                 (combine (myfun (car tree))
                         (myfun (cdr tree)))
                 (baseanswer tree) ))

Example: Count the symbols in a tree structure:


(define (nsymbols tree)
  (if (pair? tree)
      (+ (nsymbols (car tree))
         (nsymbols (cdr tree)))
      (if (symbol? tree) 1 0) ) )

> (nsymbols '(+ a (* b c))) 5

Contents    Page-10    Prev    Next    Page+10    Index