3. Tree Specification
Recall that we had 3 different styles of specification for
Specifications for trees can be viewed as generalizations of list
specifications - a list is a degenerate kind of tree - so it is no
surprise that tree specifications also fall into these three
- the classical (list = collection of nodes),
- the recursive (list = EMPTY or 2 parts: head and tail (which is
- ours, which featured operations on whole lists rather
than on individual elements (SPLIT and JOIN).
In fact, we have already seen the first two:
- a tree is a collection of nodes in which each node has exactly 1
predecessor (except the root, which has none) and any
number of successors (at most N, in the case of an N-ary tree).
- a binary tree is either empty or it has 3 parts: a value, a left
subtree, and a right subtree.