traversal for bbtrees

traverse.scm

;; bbtree-traverse : (any any (any -> any) (any -> any) any) any bbtree -> any
;; A general tree traversal procedure. Returns the value of applying
;; the traverser procedure to the current node's key, value, a
;; procedure to traverse the left subtree, a procedure to traverse the
;; right subtree, and a base value. The subtree traversal procedures
;; both take a base argument, and call bbtree-traverse recursively on
;; the appropriate subtree. It is mostly useful for implementing
;; other, more specific tree traversal procedures. For example,
;;   (define (l-to-r-pre-order cons base bbtree)
;;     (bbtree-traverse (lambda (key value left right base)
;;                        (r (l (cons key value base))))
;;                      base
;;                      bbtree))
;; implements a left-to-right pre-order traversal variant of
;; bbtree-fold

(define (traverse traverser base tree)
  (define (left base)
    (traverse traverser base (node-left tree)))
  (define (right base)
    (traverse traverser base (node-right tree)))
  (if (empty? tree)
      base
      (traverser (node-key tree)
                 (node-value tree)
                 left
                 right
                 base)))

(define (bbtree-traverse traverser base bbtree)
  (assert (bbtree? bbtree))
  (traverse traverser base (bbtree-tree bbtree)))