93 lines
2.4 KiB
Text
93 lines
2.4 KiB
Text
:- module tree_traversal.
|
|
:- interface.
|
|
|
|
:- import_module io.
|
|
|
|
:- pred main(io::di, io::uo) is det.
|
|
|
|
:- implementation.
|
|
|
|
:- import_module list.
|
|
|
|
:- type tree(V)
|
|
---> empty
|
|
; node(V, tree(V), tree(V)).
|
|
|
|
:- pred preorder(pred(V, A, A), tree(V), A, A).
|
|
:- mode preorder(pred(in, di, uo) is det, in, di, uo) is det.
|
|
|
|
preorder(_, empty, !Acc).
|
|
preorder(P, node(Value, Left, Right), !Acc) :-
|
|
P(Value, !Acc),
|
|
preorder(P, Left, !Acc),
|
|
preorder(P, Right, !Acc).
|
|
|
|
:- pred inorder(pred(V, A, A), tree(V), A, A).
|
|
:- mode inorder(pred(in, di, uo) is det, in, di, uo) is det.
|
|
|
|
inorder(_, empty, !Acc).
|
|
inorder(P, node(Value, Left, Right), !Acc) :-
|
|
inorder(P, Left, !Acc),
|
|
P(Value, !Acc),
|
|
inorder(P, Right, !Acc).
|
|
|
|
:- pred postorder(pred(V, A, A), tree(V), A, A).
|
|
:- mode postorder(pred(in, di, uo) is det, in, di, uo) is det.
|
|
|
|
postorder(_, empty, !Acc).
|
|
postorder(P, node(Value, Left, Right), !Acc) :-
|
|
postorder(P, Left, !Acc),
|
|
postorder(P, Right, !Acc),
|
|
P(Value, !Acc).
|
|
|
|
:- pred levelorder(pred(V, A, A), tree(V), A, A).
|
|
:- mode levelorder(pred(in, di, uo) is det, in, di, uo) is det.
|
|
|
|
levelorder(P, Tree, !Acc) :-
|
|
do_levelorder(P, [Tree], !Acc).
|
|
|
|
:- pred do_levelorder(pred(V, A, A), list(tree(V)), A, A).
|
|
:- mode do_levelorder(pred(in, di, uo) is det, in, di, uo) is det.
|
|
|
|
do_levelorder(_, [], !Acc).
|
|
do_levelorder(P, [empty | Xs], !Acc) :-
|
|
do_levelorder(P, Xs, !Acc).
|
|
do_levelorder(P, [node(Value, Left, Right) | Xs], !Acc) :-
|
|
P(Value, !Acc),
|
|
do_levelorder(P, Xs ++ [Left, Right], !Acc).
|
|
|
|
:- func tree = tree(int).
|
|
|
|
tree =
|
|
node(1,
|
|
node(2,
|
|
node(4,
|
|
node(7, empty, empty),
|
|
empty
|
|
),
|
|
node(5, empty, empty)
|
|
),
|
|
node(3,
|
|
node(6,
|
|
node(8, empty, empty),
|
|
node(9, empty, empty)
|
|
),
|
|
empty
|
|
)
|
|
).
|
|
|
|
main(!IO) :-
|
|
io.write_string("preorder: " ,!IO),
|
|
preorder(print_value, tree, !IO), io.nl(!IO),
|
|
io.write_string("inorder: " ,!IO),
|
|
inorder(print_value, tree, !IO), io.nl(!IO),
|
|
io.write_string("postorder: " ,!IO),
|
|
postorder(print_value, tree, !IO), io.nl(!IO),
|
|
io.write_string("levelorder: " ,!IO),
|
|
levelorder(print_value, tree, !IO), io.nl(!IO).
|
|
|
|
:- pred print_value(V::in, io::di, io::uo) is det.
|
|
|
|
print_value(V, !IO) :-
|
|
io.print(V, !IO),
|
|
io.write_string(" ", !IO).
|