tree0.html

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.
<p>
<img src="tree1.gif">
<br>
For example, the above balanced tree is expressed as
<code>((1 . 2) . (3 . 4))</code>, which is normally displayed as
<code>((1 . 2) 3 . 4)</code>.
<p>
<img src="tree2.gif">
<br>
The tree does not need to be balanced, for instance, the above tree is
<code>(((1 . 2) . 3) . 4)</code>.
<p>
Arc provides a few operations on binary trees.  However, Arc provides no explicit support for generating binary trees.  The primitive <code>cons</code> can be used to join two nodes or subtrees into a tree.  The primitives <code>car</code> and <code>cdr</code> will return the left and right subtrees (or nodes) respectively.
<pre class="repl">
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
</pre>
For more information on cons-cell binary trees, see <a href='http://en.wikipedia.org/wiki/Cons#Trees'>Wikipedia</a>.