#include
"share/atspre_staload.hats"
//
(* ****** ****** *)
//
datatype
tree (a:t@ype) =
  | tnil of ()
  | tcons of (tree a, a, tree a)
//
(* ****** ****** *)

symintr ++
infixr (+) ++
overload ++ with list_append

(* ****** ****** *)

#define sing list_sing

(* ****** ****** *)

fun{
a:t@ype
} preorder
  (t0: tree a): List0 a =
  case t0 of
  | tnil () => nil ()
  | tcons (tl, x, tr) => sing(x) ++ preorder(tl) ++ preorder(tr)

(* ****** ****** *)

fun{
a:t@ype
} inorder
  (t0: tree a): List0 a =
  case t0 of
  | tnil () => nil ()
  | tcons (tl, x, tr) => inorder(tl) ++ sing(x) ++ inorder(tr)

(* ****** ****** *)

fun{
a:t@ype
} postorder
  (t0: tree a): List0 a =
  case t0 of
  | tnil () => nil ()
  | tcons (tl, x, tr) => postorder(tl) ++ postorder(tr) ++ sing(x)

(* ****** ****** *)

fun{
a:t@ype
} levelorder
  (t0: tree a): List0 a = let
//
fun auxlst
  (ts: List (tree(a))): List0 a =
  case ts of
  | list_nil () => list_nil ()
  | list_cons (t, ts) =>
    (
      case+ t of
      | tnil () => auxlst (ts)
      | tcons (tl, x, tr) => cons (x, auxlst (ts ++ $list{tree(a)}(tl, tr)))
    )
//
in
  auxlst (sing(t0))
end // end of [levelorder]

(* ****** ****** *)

macdef
tsing(x) = tcons (tnil, ,(x), tnil)

(* ****** ****** *)

implement
main0 () = let
//
val t0 =
tcons{int}
(
 tcons (tcons (tsing (7), 4, tnil ()), 2, tsing (5))
,
1
,
 tcons (tcons (tsing (8), 6, tsing (9)), 3, tnil ())
)
//
in
  println! ("preorder:\t", preorder(t0));
  println! ("inorder:\t", inorder(t0));
  println! ("postorder:\t", postorder(t0));
  println! ("level-order:\t", levelorder(t0));
end (* end of [main0] *)