(*

Title:   Binary Trees ADT
Author:  William M. Farmer
Revised: 13-NOV-2002

Interface:

INTERFACE Trees;
  TYPE Tree;
  PROCEDURE MakeLeaf(i: INTEGER): Tree;
  PROCEDURE MakePair(s,t: Tree): Tree;
  PROCEDURE IsLeaf(t: Tree): BOOLEAN;
  PROCEDURE GetInteger(t: Tree): INTEGER;
  PROCEDURE GetLeft(t: Tree): Tree;
  PROCEDURE GetRight(t: Tree): Tree;
  PROCEDURE Height(t: Tree): INTEGER;
  PROCEDURE Sum(t: Tree): INTEGER;
END Trees.

*)

MODULE Trees;

IMPORT Out;

(* Types *)

TYPE

  Tree* = POINTER TO TreeRec;

  TreeRec = 
    RECORD
      leaf:   BOOLEAN;   (* True if leaf; false if pair *)
      int:    INTEGER;
      left:   Tree;
      right:  Tree;
    END;

(* Exceptions: *)

PROCEDURE IntegerOfPairException();
BEGIN
  Out.String("Trees.IntegerOfPairException: A pair has no integer.");
  HALT(1)  (* Abort program *)
END IntegerOfPairException;

PROCEDURE SubtreeOfLeafException();
BEGIN
  Out.String("Trees.SubtreeOfLeafException: A leaf has not subtrees.");
  HALT(1)  (* Abort program *)
END SubtreeOfLeafException;

(* Constructors: *)

PROCEDURE MakeLeaf*(i: INTEGER): Tree;
  VAR t: Tree;
BEGIN
  NEW(t);
  t^.leaf := TRUE;
  t^.int := i;
  t^.left := NIL;
  t^.right := NIL;
  RETURN t
END MakeLeaf;

PROCEDURE MakePair*(t1,t2: Tree): Tree;
  VAR t: Tree;
BEGIN
  NEW(t);
  t^.leaf := FALSE;
  t^.int := 0;      (* This value will never be used *)
  t^.left := t1;
  t^.right := t2;
  RETURN t
END MakePair;

(* Selectors: *)

PROCEDURE IsLeaf*(t: Tree): BOOLEAN;
BEGIN
  RETURN t^.leaf
END IsLeaf;

PROCEDURE GetInteger*(t: Tree): INTEGER;
BEGIN
  IF IsLeaf(t) THEN
    RETURN t^.int
  ELSE
    IntegerOfPairException()
  END
END GetInteger;

PROCEDURE GetLeft*(t: Tree): Tree;
BEGIN
  IF IsLeaf(t) THEN
    SubtreeOfLeafException()
  ELSE
    RETURN t^.left
  END
END GetLeft;

PROCEDURE GetRight*(t: Tree): Tree;
BEGIN
  IF IsLeaf(t) THEN
    SubtreeOfLeafException()
  ELSE
    RETURN t^.right
  END
END GetRight;

PROCEDURE Height*(t: Tree): INTEGER;
  VAR h1,h2: INTEGER;
BEGIN
  IF IsLeaf(t) THEN
    RETURN 1
  ELSE
    h1:= Height(GetLeft(t));
    h2:= Height(GetRight(t));
    IF h1 > h2 THEN
      RETURN 1 + h1
    ELSE
      RETURN 1 + h2
    END
  END
END Height;

PROCEDURE Sum*(t: Tree): INTEGER;
BEGIN
  IF IsLeaf(t) THEN
    RETURN GetInteger(t)
  ELSE
    RETURN Sum(GetLeft(t)) + Sum(GetRight(t))
  END
END Sum;

END Trees.
