Previous: Templates Up: Contents Next: Queues

Arc: Tree operations

One of the datatypes Arc supports is binary trees, built out of cons cells. A standard technique in Lisp is to build a binary tree with data at the leaves and cons cells as the interior nodes.

For example, the above balanced tree is expressed as ((1 . 2) . (3 . 4)), which is normally displayed as ((1 . 2) 3 . 4).

The tree does not need to be balanced, for instance, the above tree is (((1 . 2) . 3) . 4).

Arc provides a few operations on binary trees. However, Arc provides no explicit support for generating binary trees. The primitive cons can be used to join two nodes or subtrees into a tree. The primitives car and cdr will return the left and right subtrees (or nodes) respectively.

arc> (= mytree (cons (cons 1 2) (cons 3 4)))
((1 . 2) 3 . 4)
arc> (car mytree)
(1 . 2)
arc> (cdr mytree)
(3 . 4)
arc> (cadr mytree)
3

For more information on cons-cell binary trees, see Wikipedia.

Tree operations

Procedure treewise join base tree
Recursively traverses a binary tree. The base function (of one argument) is applied to each leaf, and then the join function (of two arguments) is recursively called on each pair of branches to join together the results into the final result. treewise was called trav prior to arc2.

>(treewise + sqrt '(1 . (4 . 9))) 6

>(treewise + string '(1 . (4 . 9))) "149"

Procedure tree-subst old new tree
Generates a new, modified tree. Node(s) with the value old are replaced with new in the tree.

>(tree-subst 1 9 '((1 . 2) . (3 . 4))) ((9 . 2) 3 . 4)

ontree f tree
Function f is recursively applied to the tree in prefix order, that is first the node, then the left subtree, then the right subtree. Subtrees as well as nodes are passed to f.

>(ontree prn '((1 . 2) . (3 . 4))) ((1 . 2) 3 . 4) (1 . 2) 1 2 (3 . 4) 3 4 nil