14.1.1 Conses as Trees

A tree is a binary recursive data structure made up of conses and atoms: the conses are themselves also trees (sometimes called ``subtrees'' or ``branches''), and the atoms are terminal nodes (sometimes called leaves). Typically, the leaves represent data while the branches establish some relationship among that data.

caaaar  caddar  cdar       nsubst         
caaadr  cadddr  cddaar     nsubst-if      
caaar   caddr   cddadr     nsubst-if-not  
caadar  cadr    cddar      nthcdr         
caaddr  cdaaar  cdddar     sublis         
caadr   cdaadr  cddddr     subst          
caar    cdaar   cdddr      subst-if       
cadaar  cdadar  cddr       subst-if-not   
cadadr  cdaddr  copy-tree  tree-equal     
cadar   cdadr   nsublis                   

Figure 14-2. Some defined names relating to trees.

14.1.1.1 General Restrictions on Parameters that must be Trees