Lecture 8  Our Specification Of Binary Tree  Details
3.2. Our Specification Of Binary Tree  Details
Let us now look at the details of the specification of the abstract
type Binary Tree.
Structure
a binary tree is either empty, or it consists of a component
value, and optional left and right subtrees (binary).
Note:
a subtree exists only if it is not empty.
I use the phrases ``empty subtree'' and ``no subtree''
interchangeably, they mean exactly the same thing. I normally do not
draw empty subtrees when I draw a tree (likewise ``subtree is empty''
means exactly the same thing as ``subtree does not exist'').
Direction (related type)
A direction will be used to describe the relationship between
two trees or subtrees  Left and Right refer to the
subtrees of a tree, Up refers to a subtree's parent.
Core Operations
Notational Conventions:
T, T1, T2 are binary trees, V a component value, D a direction.
The basic creation operations are the usual ones  CREATE_EMPTY and
DESTROY  plus one new one: CREATE_SINGLETON which, as discussed
above, obviates the need for an INSERT operation.
IS_EMPTY is selfevident.
GET_ROOTVALUE does just what its name says; it is the counterpart
of the GET_VALUE operation we had for lists.
The counterpart of the list operations MOVE_FORWARD and
MOVE_BACKWARD is:
 GET_TREE

 Input: T1 and D.
 Output: T2.
 Preconditions: if D = up, T1 must be a subtree. If D =
left or right, the corresponding subtree must exist (i.e.
be nonempty).
 Postconditions: T2 is T1's left subtree, right subtree, or
parent tree, as specified by D.
This is the way we move around in a tree ... we move `down' (or
`forward') by getting successive subtrees and we move `up' by getting
parent trees. For example, suppose T1 was:
T2 = get_tree(
T1,Left)
would result in:
T2 is a subtree of T1. If we now did T2 =
get_tree(
T2,Left)
we'd get:
T2 = get_tree(
T2,Up)
would return us to the
previous picture.
Note:
The precondition that subtrees must exist... this means that
GET_TREE never ever returns an empty tree. To check this
precondition we use EXISTS.
 EXISTS

 Inputs: T and D.
 Outputs: true or false.
 Postconditions: true if there exists a tree in direction D.
 true if D is `up' and D is a subtree.
 true if D is `left' or `right' and T's subtree in
direction D exists (i.e. is not empty).
 false otherwise
In other words:
 D = left or right tests if T has a subtree in direction D.
 D = up tests is D is a subtree, i.e. part of a larger tree (as
opposed to being a whole tree).
This function should always returns false if T is empty. Why?
Answer: Because (1) empty trees have no subtrees, and (2)
an empty tree can never be a subtree because empty subtrees do not
exist  recall the preconditions for GET_TREE.
Example of these operations working together (traversal)
void in_order_traverse(binary_tree *t, void (*f) (element))
{
if (! is_empty(t)) {
if (exists(t,Left)) in_order_traverse(get_tree(t,Left),f);
f(get_rootvalue(t));
if (exists(t,Right)) in_order_traverse(get_tree(t,Right),f);
}
}
 WHICH_SIDE

 Input: T.
 Output: a direction (`left' or `right').
 Preconditions: T is a subtree
 Postconditions: returns `left' if T is a left subtree,
`right' if it is a right subtree.
Although this may seem a peculiar function, it is surprisingly useful.
It is absolutely essential for doing nonrecursive tree traversal, and
many other applications.
 JOIN

 Inputs: T1, T2, and D.
 Outputs: T1' and T2'.
 Preconditions: D is not `up', T2 is not a subtree, T2 is
not empty, and T1's subtree in direction D does not exist.
 Postconditions: if T1 is empty, T1' is unified with T2. If
T1 is nonempty, T1' has T2' as its subtree in direction D.
For example:
JOIN(T1,T2,Left) satisfies all the preconditions and produces:
The two preconditions that require explanation are:
 T2 is not a subtree: we require this in order to avoid creating
two trees that have a subtree in common.
 T2 is not empty: empty subtrees do not exist.
 PRUNE

 Input: T.
 Output: T'. The tree containing T is also changed.
 Preconditions: T is a subtree (and therefore not empty).
 Postconditions: T is unchanged, except it is no longer a
subtree, and there is no longer any subtree in its place.
This is the exact inverse of JOIN. If we continue with the above
example, and now do PRUNE(T2) the result is what we started with:
Note that the tree that T is a subtree of is not a parameter. We do
not have a DELETE operation: we can achieve the same effect as DELETE(T)
by the combination: PRUNE(T) and DESTROY(T).