Tree traversal: Difference between revisions
Content deleted Content added
Add Mercury. |
|||
Line 3,029:
{1, 2, 3, 4, 5, 6, 7, 8, 9}</pre>
=={{header|Mercury}}==
<lang mercury>:- 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).</lang>
Output:
<pre>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
levelorder: 1 2 3 4 5 6 7 8 9 </pre>
=={{header|Nim}}==
| |||