Next: , Up: Cons Concepts


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

Except as explicitly stated otherwise, for any standardized function that takes a parameter that is required to be a tree, the consequences are undefined if that tree is circular.