Task

Implement a binary tree where each node carries an integer,   and implement:

   pre-order,
   in-order, 
   post-order,     and 
   level-order   traversal. 


Use those traversals to output the following tree:

         1
        / \
       /   \
      /     \
     2       3
    / \     /
   4   5   6
  /       / \
 7       8   9

The correct output should look like this:

preorder:    1 2 4 7 5 3 6 8 9
inorder:     7 4 2 5 1 8 6 9 3
postorder:   7 4 5 2 8 9 6 3 1
level-order: 1 2 3 4 5 6 7 8 9



See also

   Wikipedia article:   Tree traversal.


#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] *)