Conses as Trees (ANSI and GNU Common Lisp Document)

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.