NEXT ·  UP ·  PREVIOUS ·  CONTENTS ·  INDEX

The tree datatype

We will introduce a few important definitions for trees as defined by the parameterised tree datatype which was given earlier [*]. To recap, it is this:

datatype 'a tree = empty | node of 'a * 'a tree * 'a tree;

Definition (Nodes)

The nodes of an 'a tree are the values of type 'a which it contains. We can easily define a function which counts the number of nodes in a tree.

fun nodes (empty) = 0
  | nodes (node (_, t1, t2)) = 1 + nodes t1 + nodes t2;

Definition (Path)

A path (from tree t1 to its subtree tk) is the list t1, t2, ... tk of trees where, for all 0 < i < k, either ti = node (n, ti+1, t') or ti = node (n, t', ti+1).

Definition (Leaf)

A tree t is a leaf if it has the form node (n, empty, empty).

Definition (Depth)

We will now describe two Standard ML functions which calculate the depth of a tree. They both have type 'a tree -> int.

fun maxdepth (empty) = 0
  | maxdepth (node (_, t1, t2)) =
    1 + Int.max (maxdepth t1, maxdepth t2);

Above, Int.max is the integer maximum function. The mindepth function just uses Int.min instead of Int.max.

Definition (Perfectly balanced)

A tree t is perfectly balanced if its maximum and minimum depths are equal.

NEXT ·  UP ·  PREVIOUS ·  CONTENTS ·  INDEX