99 lines
1.6 KiB
Plaintext
99 lines
1.6 KiB
Plaintext
#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] *)
|