10.5 Traversing functions

Function: bbtree-traverse traverser ACCUM-BASE BBTREE

A general tree traversal procedure. Return the value of applying the traverser procedure to: the current node’s key, the current node’s value, a procedure to traverse the left subtree, a procedure to traverse the right subtree, and an accumulator value.

The traverser procedure must look like:

(define (traverser key value left-traverse right-traverse accum)
  ---)

and return the new accumulator value. The subtree traversal procedures are generated by bbtree-traverse; both take the current accumulator value as argument, return the new accumulator value, and call bbtree-traverse recursively on the appropriate subtree. traverser must call both left-traverse and right-traverse:

• If left-traverse is called first: the left subtree is visited first.
• If right-traverse is called first: the right subtree is visited first.

To perform a left–first preorder iteration:

(let ((bb (alist->bbtree (map (lambda (x) (cons x x))
                           '(0 1 2 3 4 5 6 7 8 9))
                         <)))
  (define (left-first key value left right accum)
    (right (left (cons key accum))))
  (bbtree-traverse left-first '() bb))
⇒ (9 8 6 7 4 5 2 0 1 3)

and to perform a right–first preorder iteration:

(let ((bb (alist->bbtree (map (lambda (x) (cons x x))
                           '(0 1 2 3 4 5 6 7 8 9))
                         <)))
  (define (right-first key value left right accum)
    (left (right (cons key accum))))
  (bbtree-traverse right-first '() bb))
⇒ (0 2 1 4 6 9 8 7 5 3)

This function 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 accum)
                     (right (left (cons* key value accum))))
                   accum
                   bbtree))

implements a left–to–right pre–order traversal variant of bbtree-fold.

Function: bbtree-fold COMBINE ACCUM-BASE BBTREE

Return the value obtained by iterating the COMBINE procedure over each node in the tree. The combine procedure takes 3 arguments: the key and value of the current node, and an accumulator value; its return value is used as the accumulator value for the next node. The initial accumulator value is provided by the ACCUM-BASE argument.

bbtree-fold performs a left–to–right in–order traversal or “minimum key to maximum key”.

(let ((bb (alist->bbtree (map (lambda (x) (cons x x))
                           '(0 1 2 3 4 5 6 7 8 9))
                         <)))
  ;;Later keys are pushed on the head.
  (bbtree-fold (lambda (key value accum)
                 (cons key accum))
               '()
               bb))
⇒ (9 8 7 6 5 4 3 2 1 0)

Function: bbtree-fold-right COMBINE ACCUM-BASE BBTREE

Like bbtree-fold, but it performs a right–to–left in–order traversal instead (i.e. maximum to minimum).

(let ((bb (alist->bbtree (map (lambda (x) (cons x x))
                           '(0 1 2 3 4 5 6 7 8 9))
                         <)))
  ;;Later keys are pushed on the head.
  (bbtree-fold-right (lambda (key value accum)
                       (cons key accum))
                     '()
                     bb))
⇒ (0 1 2 3 4 5 6 7 8 9)

Function: bbtree-map func BBTREE

Return a new bbtree obtained by updating the value of each node in BBTREE with the result of applying the procedure to its value. func must take a single argument, being the original value, and return a single value, being the new value.

(define bb
  (alist->bbtree '((#\a . foo)
                   (#\b . bar)
                   (#\c . baz)
                   (#\d . quux))
                 char<?))

(bbtree->alist (bbtree-map symbol->string bb))
⇒ ((#\a . "foo")
    (#\b . "bar")
    (#\c . "baz")
    (#\d . "quux"))

This document describes version 0.5.0-devel.1 of MMCK PFDS.